I have a function which attempts to evaluate whether a number is a perfect square or not.

It runs a unidirectional binary search and falls back to binary search when the product exceeds the input.

It works and runs O(logn) for numbers up to 2^30 (1,073,741,824).
For numbers equal or greater than 2^31 it throws exception as expected.

However, for numbers in between 2^30 and 2^31-1 it just stalls. no error. Anyone know why?

public class PerfectSquare{ public static void main(String[] args){ System.out.println(isPerfectSquare(Integer.parseInt(args[0]))); // MAX int value: 2147483647 = 2^31-1 // But, the maximum value I am able to work with is 2^30, larger numbers below MAX do not throw error but stall. } public static boolean isPerfectSquare(int input){ for(int i = 1; i < input; i*=2){ int product = i*i; if (product == input){ System.out.println("power of 2: "+i); return true; }else if(product > input){ int lowerBound = i/2; int upperBound = i; return binarySearch(lowerBound, upperBound, input); } } return false; } public static boolean binarySearch(int low, int high, int input){ int mid, product, ans = 0; while (low <= high) { mid = (low + high) / 2; System.out.println("low: "+low+", high:" +high+", middle: "+mid); product = mid*mid; if(product == input){ System.out.println("other square: "+mid); ans = 1; break; } else if (product > input) { high = mid - 1; } else { low = mid + 1; } } return ans == 1 ? true : false; }}

public class PerfectSquare{ public static void main(String[] args){ System.out.println(isPerfectSquare(Integer.parseInt(args[0]))); // MAX int value: 2147483647 = 2^31-1 // But, the maximum value I am able to work with is 2^30, larger numbers below MAX do not throw error but stall. } public static boolean isPerfectSquare(long input){ for(long i = 1; i < input; i*=2){ long product = i*i; if (product == input){ System.out.println("power of 2: "+i/4); return true; }else if(product > input){ long lowerBound = i/2; long upperBound = i; return binarySearch(lowerBound, upperBound, input); } } return false; } public static boolean binarySearch(long low, long high, long input){ long mid, product, ans = 0; while (low <= high) { mid = (low + high) / 2; System.out.println("low: "+low/4+", high:" +high/4+", middle: "+mid/4); product = mid*mid; if(product == input){ System.out.println("other square: "+mid/4); ans = 1; break; } else if (product > input) { high = mid - 1; } else { low = mid + 1; } } return ans == 1 ? true : false; }}

great, that works, but I was hoping for an explanation :)

I don't understand why long works and int doesn't. long is 32bit, and int is 64bit, so it seems the opposite should be true. clearly, I'm missing something.

why did you divide everything by four in the logging? what clue did that provide?

If input is greater than 2^30, your loop variable i is going to try to go from 2^30 to 2^31. Since an int can't hold that value, it does indeed overflow and wrap around to become a negative number. If you print out the value of i at the start of that loop on line 8, you'll see what's going on.

That however brings up a new question. In isPerfectSquare(), I don't expect "i" to ever get past log(input). It's supposed to go to the binarySearch after that - (which when I put in a log, it does.)

the loop is supposed to exit when i*i is greater than input. that's where it goes wrong. When i=2^15, then i*i is still less than 2^31, but when i = (2^15)*2, then i*i > 2^32

Thanks. But would have been nice to give CPColin some points, because he was forensic about the overflow. And as I said, I fluffed my chance at the full answer. ;)

goddam points. I meant to split them evenly, because both of you helped me figure out what was going on. grr. I really appreciate the help, I really do.

CPColin, sorry mate, can I go back and re-assign points?

The problem with the original code is that whenever you do multiplications on an integer value, if that multiplied result overflows the capacity of an "int" you'll get 0 or a negative number.

You had this problem in at least 2 places in the original code:
int product = i*i; // i*i can overflow

...
product = mid*mid ; // can overlow

If you simply switch to longs then the method works fine for me:

public static boolean isPerfectSquare(int input){ for(int i = 1; i < input; i*=2){ long product = (long)i*i; System.out.println("Product " + product); if (product == input){ System.out.println("power of 2: "+i); return true; }else if(product > (long)input){ int lowerBound = i/2; int upperBound = i; return binarySearch(lowerBound, upperBound, input); } } return false; } public static boolean binarySearch(long low, long high, long input){ long mid, product, ans = 0; while (low <= high) { mid = (low + high) / 2; System.out.println("low: "+low+", high:" +high+", middle: "+mid); product = mid*mid; if(product == input){ System.out.println("other square: "+mid); ans = 1; break; } else if (product > input) { high = mid - 1; } else { low = mid + 1; } } return ans == 1 ? true : false; }

class inttest{static int i=0;public static void main(String[] args){System.out.println(Integer.parseInt(args[0]));i=Integer.parseInt(args[0])+1;System.out.println(i);}}

well, then if I use long, and put in a max long value, I'll run into the same problem.

and in fact my "pseudo" fix, is no good either, as the function will return false for inputs between 2^30 and 2^31-1 that are possible perfect squares (in the case if INT, that is, and larger values for long)

class inttest{static int i=0;static long l =0;public static void main(String[] args){if (Integer.parseInt(args[0])<2147483647) {args[0]="2147483647";}System.out.println(Integer.parseInt(args[0]));i=Integer.parseInt(args[0])+1;System.out.println(i);l= (long)i;try{while (l<Long.MAX_VALUE&&l>Long.MIN_VALUE){l *= 2;System.out.println(l);}}catch(Exception e){}}}

If I haven't upset Doug, he might help further, but my money says that whatever type you use, it's finite and will overrun sometime.

Yeah that's a pretty sound statement :) (And I'm pretty hard to upset - I saw the 'long' at the top, just wasn't sure what was still unsolved here so I collapsed it together).

Although if you really want to handle arbitrary sized numbers for this algorithm you could use a BigInteger instead of primitive types (int, long etc.)

To state the problem that you're running into with the overflow more generally, it's that you are computing values that are larger than the upper bound for the size of value that you're using.

E.g. If you are passing in an 'int', the algorithm checks for "product > input". If input is Integer.MAX_VALUE then it should be pretty easy to see that product will never exceed it *unless* product is stored in a larger type (like long).

This will be true for any fixed size for input.

So your options are:
a) Use BigInteger
b) Use a larger primitive type internally than the type of input (e.g. longs with int input)
c) Rewrite those tests so they are more aware of the upper bound they may exceed.
i.e. before you do:
product = i * i ;
you could check:

// Make sure product won't overflow
if (i > Math.sqrt(Integer.MAX_VALUE))
return false ; // If we his this limit there will be no divisor, so we're done

int product = i * i ;

Similarly for the product inside binarySearch() method.

biginteger sounds like fun. what happens when you run out of memory? how do they calculate big things like distances between stars and Universes? sigh... clusters of computers and other stuff I'm totally clueless about ?? .... I'm sooo not even scratching the surface... sigh again, baby steps, baby steps....

CPColin, sorry mate, can I go back and re-assign points?

If you want, you can use the "Request Attention" button below the body of this question to request help from the moderators. I'm not too worried about it, though.

Maybe you’ve fully adopted the cloud since the beginning. Or maybe you started with on-prem resources but are pursuing a “cloud and mobile first” strategy. Getting to that end state has its challenges. Discover how to build out a 100% cloud and mobile IT strategy in this webinar.

Iteration:
Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…

Viewers will learn about if statements in Java and their use
The if statement:
The condition required to create an if statement:
Variations of if statements:
An example using if statements:

Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program.
Download Eclipse installation zip file:
Extract files from zip file:
Download and install JDK 8:
Open Eclipse and …