Question about Java's BigInteger's toString

femto 0
Viewed 108

Java's BigInteger's toString use recursive algorithm,

toString(BigInteger u, StringBuilder sb,
                                 int radix, int digits)

it divides u into ranges of radix,radix^2,radix^4,radix^8(basically radix^2^n),

int b = u.bitLength();
        int n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
                                 LOG_TWO - 1.0);

then decides u falls into which range and use divideAndRemainder to concatnate the result (it's a recursive algorithm)

BigInteger v = getRadixConversionCache(radix, n);
        BigInteger[] results;
        results = u.divideAndRemainder(v);

        int expectedDigits = 1 << n;

        // Now recursively build the two halves of each number.
        toString(results[0], sb, radix, digits - expectedDigits);
        toString(results[1], sb, radix, expectedDigits);

the confusing part to me is, why it uses

Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
                                 LOG_TWO - 1.0)

I think it should use floor, and without - 1.0

Math.floor(Math.log(b * LOG_TWO / logCache[radix]) /
                                 LOG_TWO)

to find the proper radix^2^n to divide, also I take from 2 to 1024 for a test(2^1 to 2^10)

[2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

if using

Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
                                 LOG_TWO - 1.0)

then it becomes

[-3, -2, -1, -1, 0, 0, 0, 0, 0, 1]

which seems wrong, but using

Math.floor(Math.log(b * LOG_TWO / logCache[radix]) /
                                 LOG_TWO)

the result is

[-2, -1, -1, 0, 0, 0, 1, 1, 1, 1]

which seemed correct

biginteger java algorithm
1 Answers

What is the purpose of that code?

The purpose is to find a BigInteger v that has the form radix^x that divides the BigInteger u into two parts that have a string representation of roughly the same length. The "perfect" value for that would probably be 10^x where u.sqrt() is between 0.5 * 10^x and 5 * 10^x (for radix 10). However such a calculation would be highly inefficient.

(Maybe the factors 0.5 and 5 are not ideal - maybe they should be 0.316 and 3.16 so that 100 is choosen for values from 1000 to 100000 - but as this approach is not used the exact values don't matter.)

Instead the code approximates that "perfect" value by using a value from the sequence radix^1, radix^2, radix^4 because these radix^(2^x) values are easy to calculate and still give good enough results.

Lets see how that calculation works for a BigInteger with a bitlength of 1024 (which has a string representation of length 308 to 309 characters).

The expression (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0) is two calculations wrapped into one expression:

  • b * LOG_TWO / logCache[radix] calculates the approximate number of digits to represent the BigInteger value as string in radix radix

    Note that logCache[radix] is initialized with Math.log(radix) and LOG_TWO is Math.log(2), so the full expression is b * Math.log(2) / Math.log(radix)

    For a bitlength of 1024 this calculation gives 308.2547 (rounded to 4 digits).

    Lets name this intermediate result num_digits

  • The second calculation is then (int) Math.round(Math.log(num_digits) / Math.log(2) - 1.0). For num_digits of 308.2547 this gives 7.

    Therefore in our example the code will pick 10^(2^7) (which is 10^128) as divisor to split the original number.

Why does it use Math.round(x-1) instead of Math.floor(x)?

Note that this example uses a very small bitlength just to prove the point. Effectively this calculation is never done with so small values

It gives a better value for n.

Take for example a bitlength of 14 (the BigInteger value is between 8192 and 16383).

Using Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0) gives n=1, which means the code will choose 10^(2^1) (which is 100) to split the BigInteger.

Using Math.floor(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO) gives n =2, which would mean that the code would choose 10^(2^2) (which is 10000) to split the BigInteger - but for a BigInteger value of 8192 that would mean it would not split it at all.

Using Math.floor() breaks down at several places:

  • for the values 64 - 127 (bitlength = 7) using Math.floor() results in n=1 and u=100 and therefore cannot split values 64-99
  • for the values 8'192 - 16'383 (bitlength = 14) using Math.floor() results in in=2 and u=10'000 and therefore cannot split values 8'192 - 9'999
  • for the values 67'108'864 - 134'217'727 (bitlength = 27) using Math.floor() results in in=3 and u=100'000'000 and therefore cannot split values 67'108'864 - 99'999'999
  • for the values 9'007'199'254'740'992 - 18'014'398'509'481'983 (bitlength = 54) using Math.floor() results in in=3 and u=10'000'000'000'000'000 and therefore cannot split values 9'007'199'254'740'992 - 9'999'999'999'999'999

For those ranges (and there exist other ranges at larger bitlength values) you would need special handling after the split: if the upper part is BigInteger.ZERO then do some special handling. But any kind of special handling makes the algorithm more complex, more error prone and slower.

For other ranges using Math.floor() doesn't really give better results than using Math.round():

  • for the values 16'384 - 99'999 (bitlengths from 15 to 17) using Math.floor() results in in=2 and u=10'000 and therefore the values are split into 1 digit and 4 digits.

    Using Math.round() for these values results in n=1 and u=100 and therefore the values are split into 3 digits and 2 digits which to me seems more equally split.

  • for the values 100'000 - 262'143 (bitlengths from 17 to 18) using Math.floor() results in in=2 and u=10'000 and therefore the values are split into 2 digits and 4 digits. Using Math.round() for these values results in n=1 and u=100 and therefore the values are split into 4 digits and 2 digits.

    For this range both approaches are on an equal level - either way you have a 4 digit number that you need to split further.

Why is that special case handling such a problem

Lets try to convert the number 659'876 into a decimal string.

Both approaches (using Math.floor() and using Math.round()) agree that we should use n=2 and u=10'000 in the first step.

Using the calculation with Math.floor():

  • in the first step 659'876 is split into 65 and 9'876
    • recursion 1: 65 - is a special case, needs additional work to split it into 6 and 5
    • recursion 2: 9'876 - is a special case, needs additional work to split it into 98 and 76
      • recursion 2.1: 98 - is a special case, needs additional work to split it into 9 and 7
      • recursion 2.2: 76 - is a special case, needs additional work to split it into 7 and 6

(the last recursive step that appends the single digit values to the StringBuilder has been left out).

Using the calculation with Math.round():

  • in the first step 659'876 is split into 65 and 9'876
    • recursion 1: 65 is split into 6 and 5
    • recursion 2: 9'876 is split into 98 and 76
      • recursion 2.1: 98 is split into 9 and 7
      • recursion 2.2: 76 is split into 7 and 6

Example using 16'383

One of your comments claims that 16'383 cannot be handled using Math.round(), so lets take this as additional example.

Using the calculation with Math.floor():

  • in the first step 16'383 is split into 1 and 6'383
    • recursion 1: 1 is appended to the StringBuilder
    • recursion 2: 6'383 is split into 63 and 84
      • recursion 2.1: 63 is split into 6 and 3
      • recursion 2.2: 83 - is a special case, needs additional work to split it into 8 and 3

(the last recursive step that appends the single digit values to the StringBuilder has been mostly left out).

Using the calculation with Math.round():

  • in the first step 16'383 is split into 163 and 83
    • recursion 1: 163 is split into 16 and 3
      • recursion 1.1: 16 is split into 1 and 6
    • recursion 2: 83 is split into 8 and 3

As you can see even when using Math.round() its no problem to convert 16'384 into a decimal string.

Conclusion

Using Math.floor() doesn't work for all cases (i.e. requires additional logic to detect those cases and then needs to do additional work). IMHO this observation is enough to reject that approach.

Note that you could "fix" the algorithm using Math.floor() by subtracting a small value from the num_digits intermediate result. But then, Math.floor(xx-0.5) gives for most values of xx the same result as Math.round(xx-1.0).

Hooray, we found a way that we could use Math.floor() without needing a special case handling! :)

Additional note

This calculation doesn't work for very small values of bitlength.

In the case of radix 10 it doesn't work for bitlength less than 4 - but bitlength values from 1 to 3 mean that the actual value in the BigInteger is in the range from 1 to 7 - and for so small values the algorithm doesn't make sense (because the result is confined to a single digit).

Thomas Kläger0
Related