Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Code Puzzler Response - Find the Integer Square Root of a Positive Integer

DZone's Guide to

Code Puzzler Response - Find the Integer Square Root of a Positive Integer

· Java Zone
Free Resource

Microservices! They are everywhere, or at least, the term is. When should you use a microservice architecture? What factors should be considered when making that decision? Do the benefits outweigh the costs? Why is everyone so excited about them, anyway?  Brought to you in partnership with IBM.

This Code Puzzler comes from the community contributor - Erik Colban
Thanks, Eric for today's extra brain-teaser!

Write a function that calculates the integer square root of any positive integer, but only uses add, subtract, left and right shifts, but no division or multiplication. The algorithm must run in O(log n) time. By integer square root I mean the largest integer whose square is less than or equal to a given number.

A similar problem was given before, and all submitted solutions were based on the iteration: x_n+1 = (x_n + x/x_n) / 2. That formula is great for finding good rational approximations of the square root of a number, but it's trivial once you know the formula. This problem is a little more challenging.

Below is an answer. The first while loop finds the largest power of 4 that is less than or equal to value. The next while loop has the following invariants:

  1. q * root * root + remainder == value
  2. 0 <= remainder < q * (2 * root + 1)
  3. d == q * root

It's relatively easy to verify these invariants. When exiting the while loop, q == 1, and the invariants can be used to show that:

  1. root * root <= value && value < (root + 1) * (root + 1)


    public static int intSqrt(int value) {
    		int q = 1;
    		while (q <= value) {
    			q <<= 2;
    		}
    		q >>= 2;
    		int d = q;
    		int remainder = value - q;
    		int root = 1;
    		while (q > 1) {
    			root <<= 1;
    			q >>= 2;
    			int s = q + d;
    			d >>= 1;
    			if (s <= remainder) {
    				remainder -= s;
    				root++;
    				d += q;
    			}
    		}
    		return root;
    	}

    Are there any other answers you have that don't use  x_n+1 = (x_n + x/x_n) / 2?


Discover how the Watson team is further developing SDKs in Java, Node.js, Python, iOS, and Android to access these services and make programming easy. Brought to you in partnership with IBM.

Topics:

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}