How do I quickly calculate a large positive, or negative, power of 2 in Java?

Question

I want to calculate powers of two larger than 2⁶², so I must store the result in a double and can't use the (1L << exp) trick. I also want to store fractions representing negative powers of two.

Answer 1

Java provides java.lang.Math.scalb(float f, int scaleFactor) for this. It multiplies f by 2^scaleFactor.

Answer 2

Since the IEEE 754 standard specifies a hidden bit, you can simply leave the 52-bit significand portion as 0 and only need to change the exponent portion, which is a biased unsigned integer, for powers in the normal range.

private static double pow2(int x) {
    return Double.longBitsToDouble((x + (long) sun.misc.DoubleConsts.EXP_BIAS) << (sun.misc.DoubleConsts.SIGNIFICAND_WIDTH - 1));
}

In order to also implement gradual underflow for subnormal powers, i.e. when the exponent is less than -1022, you have to specify an exponent of -1023 and shift a 1 bit into the significand.

private static double pow2(int x) {
    if (x < 1 - sun.misc.DoubleConsts.EXP_BIAS)
        return Double.longBitsToDouble(1L << (sun.misc.DoubleConsts.SIGNIFICAND_WIDTH - 1 + x + sun.misc.DoubleConsts.EXP_BIAS - 1));
    return Double.longBitsToDouble((x + (long) sun.misc.DoubleConsts.EXP_BIAS) << (sun.misc.DoubleConsts.SIGNIFICAND_WIDTH - 1));
}

You also should make sure that powers overflow to infinity when the exponent is greater than 1023, and underflow to 0 when the exponent is less than -1074.

private static double pow2(int x) {
    if (x < 2 - sun.misc.DoubleConsts.EXP_BIAS - sun.misc.DoubleConsts.SIGNIFICAND_WIDTH)
        return 0;
    if (x > sun.misc.DoubleConsts.EXP_BIAS)
        return Double.POSITIVE_INFINITY;
    if (x < 1 - sun.misc.DoubleConsts.EXP_BIAS)
        return Double.longBitsToDouble(1L << (sun.misc.DoubleConsts.SIGNIFICAND_WIDTH - 1 + x + sun.misc.DoubleConsts.EXP_BIAS - 1));
    return Double.longBitsToDouble((x + (long) sun.misc.DoubleConsts.EXP_BIAS) << (sun.misc.DoubleConsts.SIGNIFICAND_WIDTH - 1));
}

Finally, you can also remove the dependency on the internal sun.misc package by hardcoding the constants.

private static double pow2(int x) {
    final int EXP_BIAS = 1023;
    final int SIGNIFICAND_WIDTH = 53;
    //boolean isSubnormal = x < 1 - EXP_BIAS;

    if (x < 2 - EXP_BIAS - SIGNIFICAND_WIDTH) return 0;
    //if (x > EXP_BIAS) return Double.POSITIVE_INFINITY;
    x = Math.min(x, EXP_BIAS + 1);
    //long exp = isSubnormal ? 1 : (x + EXP_BIAS);
    long exp = Math.max(1, x + EXP_BIAS);
    //int shift = SIGNIFICAND_WIDTH - 1 + (isSubnormal ? (x + EXP_BIAS - 1) : 0);
    int shift = SIGNIFICAND_WIDTH - 1 + Math.min(0, x + EXP_BIAS - 1);
    return Double.longBitsToDouble(exp << shift);
}

To verify the correctness of this implementation, you can add a unit test that checks the underflow and overflow behavior and compares every representable power of 2 to Math.pow(2, x).

for (int i = -1075; i <= 1024; i++)
    Assert.assertTrue(pow2(i) == Math.pow(2, i));

On my machine, the pow2(i) microbenchmark takes between 50-100ms while the pow(2, i) microbenchmark takes between 2000-2500ms.

long start, end;

start = System.currentTimeMillis();
for (int iter = 0; iter < 10000; iter++)
    for (int i = -1075; i <= 1024; i++)
        pow2(i);
end = System.currentTimeMillis();
System.out.println(end - start);

start = System.currentTimeMillis();
for (int iter = 0; iter < 10000; iter++)
    for (int i = -1075; i <= 1024; i++)
        Math.pow(2, i);
end = System.currentTimeMillis();
System.out.println(end - start);