• Post Reply Bookmark Topic Watch Topic
  • New Topic

Big Integer  RSS feed

 
Ranch Hand
Posts: 1906
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
I am currently wirinting a method involving BigInteger. Method accepts BigInteger and increases its value by 1 in a loop till some criteria is met. For adding one to Big Integer, I am using BigInteger.add() method. Big Integer is immutable object as per API.So add() method returns new Big Integer.
Problem is if number is too big and criteria is not met for a while, program hangs. For e.g. numbers above 1000000 ,program hangs.Any idea how to avoid this?
 
Sheriff
Posts: 14691
16
Eclipse IDE Ubuntu VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Where does it hang ? Incrementing the value doesn't make it hang. Did you try to debug ?
 
Arjun Shastry
Ranch Hand
Posts: 1906
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Code is like something like this:

I believe temp.add() returns new Big Integer every time, it gets called. So for bi=10000000, in worst case it will be called bi times.
 
Java Cowboy
Sheriff
Posts: 16060
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Surely you meant BigInteger.valueOf(...) in those examples instead of String.valueOf(...)?

Note that class BigInteger has a few constants, which would make it slightly more efficient:

But why are you using BigInteger for this, could the search in the while loop really take more iterations than would fit in a long (2^63 - 1 = 9,223,372,036,854,775,807 iterations?!) or even in an int (2^31 - 1 = 2,147,483,647 iterations)? Use a long or int instead of a BigDecimal.
 
Arjun Shastry
Ranch Hand
Posts: 1906
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks.Input bi might be very big-10^100 too.So long can not be used.Hence I am using String.valueOf() instead BigInteger.valueOf() which uses long.
 
Marshal
Posts: 56607
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your program does not appear to hang at all. It appears to take a very long time to complete its loop. Assuming 10 nanoseconds for one iteration of the loop, then going from 9.99999999999999999999 × 10^99 to 10^100 requires 10^80 iterations which will take 10^72 seconds which is approx 3.17 × 10^64 years.

Don't hold your breath!
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16060
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Do you really expect to iterate a loop a googol times in a reasonable amount of time? Computers are not infinitely fast!

Even if you would let it run to the limit of the long data type, and one iteration would take 10 ns, it would take almost 3,000 years before the loop is finished!

 
author
Bartender
Posts: 4093
21
Eclipse IDE Flex Google Web Toolkit
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is a good example of why searching algorithms are non-trivial. Also a good example where a binary search, O(log(n)), makes a big difference to a polynomial search, O(n). Granted, I have no idea if a binary search (or any other intelligent searching algorithm) can be applied here but unless you have near infinite time, I'd suggest finding one.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!