如何在 Java 中快速计算 2 的大正幂或负幂？

Question

我想计算大于 2⁶² 的两个的幂，所以我必须将结果存储在 double 中，不能使用 (1L << exp) 诡计。我还想存储代表两个负幂的分数。

Answer 1

由于IEEE 754标准指定了一个隐藏位，您可以简单地将52位有效数字部分保留为0，只需要更改指数部分，这是一个有偏差的无符号整数，以获得正常范围内的幂。

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

为了也实现次正规幂的逐渐下溢，即当指数小于 -1022 时，您必须指定 -1023 的指数并将 1 位移入尾数。

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));
}

你还应该确保当指数大于 1023 时幂上溢到无穷大，当指数小于 -1074 时下溢到 0。

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));
}

最后，您还可以通过对常量进行硬编码来移除对内部 sun.misc 包的依赖。

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);
}

要验证此实现的正确性，您可以添加一个单元测试来检查下溢和上溢行为并将 2 的每个可表示的幂与 Math.pow(2, x) 进行比较。

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

在我的机器上，pow2(i) 微基准测试需要 50-100 毫秒，而 pow(2, i) 微基准测试需要 2000-2500 毫秒。

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);

Answer 2

Java 为此提供了 java.lang.Math.scalb(float f, int scaleFactor)。它将 f 乘以 2^scaleFactor.

如何在 Java 中快速计算 2 的大正幂或负幂？

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

java

floating-point

precision

ieee-754

exponent