RFR 4641897: Faster string conversion of large integers

Alan Eliasen eliasen at mindspring.com
Tue Jun 25 19:09:42 UTC 2013

On 06/25/2013 12:13 PM, Peter Levart wrote:
>             else { // resizing
>                 // increase by factor of 1.5 (like ArrayList)
>                 int newLength = oldLength + (oldLength >> 1);

   We probably don't ever want to extend any row of this cache any more
than we need to.  The entries in each row of the cache, say for base 10,
are 10^(2^n) which obviously grows super-exponentially with n.  (And the
time to perform each squaring to get successive terms will grow
quadratically or at least subquadratically on top of that, along with
memory usage which squares with each additional term.)  So we should
never resize to more entries in that table than we need, and we should
try to avoid recalculating entries in that table in multiple threads, as
the cost to calculate them can be high.

   As I noted years ago, the caching behavior is certainly going to be
one of the most controversial parts of BigInteger improvements.  :)

  Alan Eliasen
  eliasen at mindspring.com

More information about the core-libs-dev mailing list