Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8150513

Improve speed of BigInteger.toString()

XMLWordPrintable

    • generic
    • generic

      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.

            bpb Brian Burkhalter
            webbuggrp Webbug Group
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated: