A DESCRIPTION OF THE REQUEST :
You may be interested to learn that using the theta(lg(n)) algorithm for computing Fibonacci numbers given in Wikipedia it is possible to compute Fn(1_000_000_000) in 701.743164355 seconds using the BigInteger data type. The resulting number is 208,987,640 digits, allegedly 694,241,913 bits, long and looks something like this: 79523178745546834678293851961971481892555421852<< 208,987,546 >>96198982902073319952559425703172326981560546875. However, it takes over 9.666 GB of memory and 2,282.247324311 seconds to make BigInteger return the result as a string using the toString() method, but only a few microseconds to chop the resulting string into the form shown above. Could the memory consumption and speed of the BigInteger.toString() be made more practical?
JUSTIFICATION :
One works for a couple of days to fashion a practical algorithm for computing the Fibonacci number for large arguments, only to have to wait almost three-quarters of an hour to check the result.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
BigInteger.toString() should require only a few seconds regardless of the size of the number.
ACTUAL -
See above.
---------- BEGIN SOURCE ----------
public class TestFib {
private static final Logger log = Logger.getAnonymousLogger();
private static final HashMap<Long, BigInteger> memoizer = new HashMap<>();
public static final BigInteger evenQ(long n){
return( ((n & 1) == 0) ? ONE : ONE.negate() );
}
public static final boolean oddQ(long n){
return( ((n & 1) == 1) );
}
public static final BigInteger fibonacci(long n){
if( n < 0 )
return evenQ(n+1).multiply(fibonacci(-n));
if(!memoizer.containsKey(n)){
if( n == 0 )
memoizer.put(n, ZERO);
else if( n == 1 || n == 2 )
memoizer.put(n, ONE);
else if( oddQ(n) ){
if( !memoizer.containsKey((n+1)/2) )
memoizer.put((n+1)/2, fibonacci((n+1)/2));
if( !memoizer.containsKey( (n-1)/2 ) )
memoizer.put(((n-1)/2), fibonacci((n-1)/2));
memoizer.put(n, memoizer.get((n+1)/2).pow(2).add(memoizer.get((n-1)/2).pow(2)));
}else{
if( !memoizer.containsKey(n/2) )
memoizer.put(n/2, fibonacci(n/2));
if( !memoizer.containsKey(n/2-1) )
memoizer.put(n/2-1, fibonacci(n/2-1));
memoizer.put(n, memoizer.get(n/2-1).shiftLeft(1).add(memoizer.get(n/2)).multiply(memoizer.get(n/2)));
}
}
return( memoizer.get(n) );
}
public static final String Short(long n){
long stop, start = System.nanoTime();
BigInteger result = fibonacci(n);
log.info(String.format("Computed result in %,.9f seconds%n",
(System.nanoTime()-start)/1E9));
StringBuilder sb = new StringBuilder(256);
sb.append(String.format("memoizer has %,d keys:%n Key Bit Length%n", memoizer.size()));
TreeSet<Long> ts = new TreeSet(memoizer.keySet());
Iterator<Long> iter = ts.iterator();
while( iter.hasNext() ){
long i = iter.next();
sb.append(String.format("%,14d %-,32d%n", i, memoizer.get(i).bitLength()));
}
log.info(sb.toString());
sb.delete(0, sb.length());
start = System.nanoTime();
String tmp = result.toString();
log.info(String.format("Result converted to String in %,.9f seconds", (System.nanoTime()-start)/1E9));
start = System.nanoTime();
int len = tmp.length();
log.info(String.format("Length of String found in %,.9f seconds", (System.nanoTime()-start)/1E9));
if( len <= 69 )
return tmp;
start = System.nanoTime();
sb.append(tmp.substring(0, 47))
.append(String.format("<< %,d >>", len-47-47))
.append(tmp.substring(len - 47));
log.info(String.format("Short String found in %,.9f seconds", (System.nanoTime()-start)/1E9));
return sb.toString();
}
public static void main(String[] args) {
log.info(String.format("Fibonacci(10) = %s", Short(10)));
log.info(String.format("Fibonacci(1,000,000,000) = %s", Short(1_000_000_000)));
}
}
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
Learn to love coffee and washing dishes.
You may be interested to learn that using the theta(lg(n)) algorithm for computing Fibonacci numbers given in Wikipedia it is possible to compute Fn(1_000_000_000) in 701.743164355 seconds using the BigInteger data type. The resulting number is 208,987,640 digits, allegedly 694,241,913 bits, long and looks something like this: 79523178745546834678293851961971481892555421852<< 208,987,546 >>96198982902073319952559425703172326981560546875. However, it takes over 9.666 GB of memory and 2,282.247324311 seconds to make BigInteger return the result as a string using the toString() method, but only a few microseconds to chop the resulting string into the form shown above. Could the memory consumption and speed of the BigInteger.toString() be made more practical?
JUSTIFICATION :
One works for a couple of days to fashion a practical algorithm for computing the Fibonacci number for large arguments, only to have to wait almost three-quarters of an hour to check the result.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
BigInteger.toString() should require only a few seconds regardless of the size of the number.
ACTUAL -
See above.
---------- BEGIN SOURCE ----------
public class TestFib {
private static final Logger log = Logger.getAnonymousLogger();
private static final HashMap<Long, BigInteger> memoizer = new HashMap<>();
public static final BigInteger evenQ(long n){
return( ((n & 1) == 0) ? ONE : ONE.negate() );
}
public static final boolean oddQ(long n){
return( ((n & 1) == 1) );
}
public static final BigInteger fibonacci(long n){
if( n < 0 )
return evenQ(n+1).multiply(fibonacci(-n));
if(!memoizer.containsKey(n)){
if( n == 0 )
memoizer.put(n, ZERO);
else if( n == 1 || n == 2 )
memoizer.put(n, ONE);
else if( oddQ(n) ){
if( !memoizer.containsKey((n+1)/2) )
memoizer.put((n+1)/2, fibonacci((n+1)/2));
if( !memoizer.containsKey( (n-1)/2 ) )
memoizer.put(((n-1)/2), fibonacci((n-1)/2));
memoizer.put(n, memoizer.get((n+1)/2).pow(2).add(memoizer.get((n-1)/2).pow(2)));
}else{
if( !memoizer.containsKey(n/2) )
memoizer.put(n/2, fibonacci(n/2));
if( !memoizer.containsKey(n/2-1) )
memoizer.put(n/2-1, fibonacci(n/2-1));
memoizer.put(n, memoizer.get(n/2-1).shiftLeft(1).add(memoizer.get(n/2)).multiply(memoizer.get(n/2)));
}
}
return( memoizer.get(n) );
}
public static final String Short(long n){
long stop, start = System.nanoTime();
BigInteger result = fibonacci(n);
log.info(String.format("Computed result in %,.9f seconds%n",
(System.nanoTime()-start)/1E9));
StringBuilder sb = new StringBuilder(256);
sb.append(String.format("memoizer has %,d keys:%n Key Bit Length%n", memoizer.size()));
TreeSet<Long> ts = new TreeSet(memoizer.keySet());
Iterator<Long> iter = ts.iterator();
while( iter.hasNext() ){
long i = iter.next();
sb.append(String.format("%,14d %-,32d%n", i, memoizer.get(i).bitLength()));
}
log.info(sb.toString());
sb.delete(0, sb.length());
start = System.nanoTime();
String tmp = result.toString();
log.info(String.format("Result converted to String in %,.9f seconds", (System.nanoTime()-start)/1E9));
start = System.nanoTime();
int len = tmp.length();
log.info(String.format("Length of String found in %,.9f seconds", (System.nanoTime()-start)/1E9));
if( len <= 69 )
return tmp;
start = System.nanoTime();
sb.append(tmp.substring(0, 47))
.append(String.format("<< %,d >>", len-47-47))
.append(tmp.substring(len - 47));
log.info(String.format("Short String found in %,.9f seconds", (System.nanoTime()-start)/1E9));
return sb.toString();
}
public static void main(String[] args) {
log.info(String.format("Fibonacci(10) = %s", Short(10)));
log.info(String.format("Fibonacci(1,000,000,000) = %s", Short(1_000_000_000)));
}
}
---------- END SOURCE ----------
CUSTOMER SUBMITTED WORKAROUND :
Learn to love coffee and washing dishes.
- relates to
-
JDK-8229845 Decrease memory consumption of BigInteger.toString()
- Resolved