java. math. BigInteger pow (exponential) problem

I did some tests on the pow (index) method Unfortunately, my math skills are not enough to solve the following problems

I am using this Code:

BigInteger.valueOf(2).pow(var);

result:

>Var | time in milliseconds > 2000000 | 11450 > 2500000 | 12471 > 3000000 | 22379 > 3500000 | 32147 > 4000000 | 46270 > 4500000 | 31459 > 5000000 | 49922

See? The 2500000 index is calculated almost as fast as 2000000 The calculation speed of 4000 is much faster than 4000

Why?

To help you, this is BigInteger The original implementation of pow (exponent):

public BigInteger pow(int exponent) {
    if (exponent < 0)
        throw new ArithmeticException("Negative exponent");
    if (signum==0)
        return (exponent==0 ? ONE : this);

    // Perform exponentiation using repeated squaring trick
        int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
    int[] baseToPow2 = this.mag;
        int[] result = {1};

    while (exponent != 0) {
        if ((exponent & 1)==1) {
        result = multiplyToLen(result,result.length,baseToPow2,baseToPow2.length,null);
        result = trustedStripLeadingZeroInts(result);
        }
        if ((exponent >>>= 1) != 0) {
                baseToPow2 = squareToLen(baseToPow2,null);
        baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
        }
    }
    return new BigInteger(result,newSign);
    }

Solution

The algorithm uses square to len and multiply to len The running time of these operations depends on the size of the numbers involved At the end of the calculation, the multiplication of large numbers is much larger than at the beginning

Multiplication is only completed when this condition is true: ((exponent & 1) = = 1) The number of square operations depends on the number of bits in the number (excluding leading zeros), but only bits set to 1 need multiplication By viewing the binary file, you can more easily see the number of operation representatives required:

2000000: 0000111101000010010000000
2500000: 0001001100010010110100000
3000000: 0001011011100011011000000
3500000: 0001101010110011111100000
4000000: 0001111010000100100000000
4500000: 0010001001010101000100000
5000000: 0010011000100101101000000

Note that 2.5m and 4.5m are lucky because they set fewer high bits than the surrounding numbers The next time this happens is 8.5m:

8000000: 0011110100001001000000000
8500000: 0100000011011001100100000
9000000: 0100010010101010001000000

Sweet spot is the precise power of 2

1048575: 0001111111111111111111111 // 16408 ms
1048576: 0010000000000000000000000 //  6209 ms