Solved

java binary search max int value

Posted on 2014-02-09
35
797 Views
Last Modified: 2014-02-13
Hi,

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;
	}
}

Open in new window

0
Comment
Question by:Kyle Hamilton
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 16
  • 13
  • 3
  • +1
35 Comments
 
LVL 16

Accepted Solution

by:
krakatoa earned 250 total points
ID: 39845787
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;
	}
}

Open in new window

0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845825
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?

thanks.
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845848
I don't understand why long works and int doesn't. long is 32bit, and int is 64bit,

I thought it was the other way 'round, myself.
0
What Is Transaction Monitoring and who needs it?

Synthetic Transaction Monitoring that you need for the day to day, which ensures your business website keeps running optimally, and that there is no downtime to impact your customer experience.

 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845852
You're totally right. I've been staring at it for too long.

sorry
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845858
but the question does remain though. if INT is supposed to be able to handle up to 2^31-1, then why does it freak out at n > 2^30 ??

something to do with overflow??
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845868
If you do " product = i * i"  - on product being an int - it isn't going to last very long when you input int MAXVALUE as a start value.
0
 
LVL 14

Assisted Solution

by:CPColin
CPColin earned 250 total points
ID: 39845877
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.
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845886
Hmmm.

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.)
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845891
i never gets that big. here's i logged out at the start of the loop as suggested for input ~2^30

i: 1
i: 2
i: 4
i: 8
i: 16
i: 32
i: 64
i: 128
i: 256
i: 512
i: 1024
i: 2048
i: 4096
i: 8192
i: 16384
i: 32768
low: 16384, high:32768, middle: 24576
low: 24577, high:32768, middle: 28672
low: 28673, high:32768, middle: 30720
low: 30721, high:32768, middle: 31744
low: 31745, high:32768, middle: 32256
low: 32257, high:32768, middle: 32512
low: 32257, high:32511, middle: 32384
low: 32257, high:32383, middle: 32320
low: 32321, high:32383, middle: 32352
low: 32353, high:32383, middle: 32368
low: 32353, high:32367, middle: 32360
low: 32361, high:32367, middle: 32364
low: 32365, high:32367, middle: 32366
low: 32365, high:32365, middle: 32365
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845903
But you are already trying to hold "input" as an int, when passed from the command line.
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845924
ok, nvm.

when I use 2^31-1, it overflows. here's a snippet:

i: 33554432
i: 67108864
i: 134217728
i: 268435456
i: 536870912
i: 1073741824
i: -2147483648
i: 0
i: 0
i: 0
i: 0
i: 0
i: 0
i: 0


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 guys. really appreciate it.
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845932
thank you. :)
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845935
then i*i > 2^32

Yeah . . . I put that in my comment, then swapped it out for 'product'. Lol. Oops. ;)
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845938
conclusion: my algorithm is crappy, since it doesn't error out and worse yet goes into infinite loop :O

suggestions are most welcome.. if you're so inlclined.
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845941
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. ;)
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845944
for what it's worth, this fixes it:

for(int i = 1; i < input && i > 0; i*=2){
}
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845947
conclusion: my algorithm is crappy,

probably recognising things like that is indicative of being able to take it all further - heuristics is the best way.
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845948
See - you beat me to it. QED. ;)
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845950
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?
0
 
LVL 27

Expert Comment

by:dpearson
ID: 39845951
Yes "i" should never get very large.

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;
		}

Open in new window


Then given:

            int input = 32769 * 32769 ;  // More than 2^30
            boolean isPerfect = PerfectSquare.isPerfectSquare(input) ;

returns true (as it should) and does it in O(log n) time (as it should).

Is there any other problem that still needs to be solved?

Doug
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845967
If you simply switch to longs then the method works fine for me:

Doug - there is a funny echo in the room  somehow.

We said that at the top. ;)
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845975
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);

}


}

Open in new window

0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845977
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)
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845978
actually, long does something different doesn't it? it loops around itself when it overflows...
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845985
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.
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39845989
yeah, bottom line is, this is a bad approach, and i will have nightmares trying to figure out a better one, but that is the price of learning.

I'm pretty sure this problem has been solved before, haha.

cheers.
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39845997
For what it's worth :

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){}

}


}

Open in new window


ciao.
0
 
LVL 27

Expert Comment

by:dpearson
ID: 39846065
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.

Doug
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39846201
thanks Doug. I like option b which doesn't require any additional logic.

cheers.
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39846218
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....

goodnight.
0
 
LVL 27

Expert Comment

by:dpearson
ID: 39846268
Number of atoms in universe ~= 10^82 or in binary call it ~= 2^86

So to record the number of atoms in the universe you need about 86 bits in your number or about 11 bytes.

So how big of a number could you store in say 11GB instead of 11 bytes?  Probably big enough :)

Doug
0
 
LVL 14

Expert Comment

by:CPColin
ID: 39852277
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.
0
 
LVL 25

Author Closing Comment

by:Kyle Hamilton
ID: 39857529
thanks again. i'll be back for more punishment :)
0
 
LVL 16

Expert Comment

by:krakatoa
ID: 39857813
Spare the rod, spoil the child.

;)
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction Java can be integrated with native programs using an interface called JNI(Java Native Interface). Native programs are programs which can directly run on the processor. JNI is simply a naming and calling convention so that the JVM (Java…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.

724 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question