src/share/classes/java/math/BigDecimal.java

rev 7462 : 4837946: Faster multiplication and exponentiation of large integers
4646474: BigInteger.pow() algorithm slow in 1.4.0
Summary: Implement Karatsuba and 3-way Toom-Cook multiplication as well as exponentiation using Karatsuba and Toom-Cook squaring.
Reviewed-by: alanb, bpb, martin
Contributed-by: Alan Eliasen <eliasen@mindspring.com>

*** 1,7 ****
  /*
!  * Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
--- 1,7 ----
  /*
!  * Copyright (c) 1996, 2013, Oracle and/or its affiliates. All rights reserved.
   * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   *
   * This code is free software; you can redistribute it and/or modify it
   * under the terms of the GNU General Public License version 2 only, as
   * published by the Free Software Foundation.  Oracle designates this
*** 3536,3563 ****
                  return pows[n];
              else
                  return expandBigIntegerTenPowers(n);
          }
  
!         if (n < 1024*524288) {
!             // BigInteger.pow is slow, so make 10**n by constructing a
!             // BigInteger from a character string (still not very fast)
!             // which occupies no more than 1GB (!) of memory.
!             char tenpow[] = new char[n + 1];
!             tenpow[0] = '1';
!             for (int i = 1; i <= n; i++) {
!                 tenpow[i] = '0';
!             }
!             return new BigInteger(tenpow, 1, tenpow.length);
!         }
! 
!         if ((n & 0x1) == 0x1) {
!             return BigInteger.TEN.multiply(bigTenToThe(n - 1));
!         } else {
!             BigInteger tmp = bigTenToThe(n/2);
!             return tmp.multiply(tmp);
!         }
      }
  
      /**
       * Expand the BIG_TEN_POWERS_TABLE array to contain at least 10**n.
       *
--- 3536,3546 ----
                  return pows[n];
              else
                  return expandBigIntegerTenPowers(n);
          }
  
!         return BigInteger.TEN.pow(n);
      }
  
      /**
       * Expand the BIG_TEN_POWERS_TABLE array to contain at least 10**n.
       *