两个分数的幂的最近倍数

Question

是否有一种优化的、高效的方法来将双精度四舍五入为最接近给定的二分法幂的倍数的精确值？

换句话说，将 .44 舍入到最接近的 1/16（换句话说，可以表示为 n/16 的值，其中 n 是整数）是 .4375。注意：这是相关的，因为两个分数的幂可以在没有舍入误差的情况下存储，例如

public class PowerOfTwo {
  public static void main(String... args) {
    double inexact = .44;
    double exact = .4375;

    System.out.println(inexact + ":   " + Long.toBinaryString(Double.doubleToLongBits(inexact)));
    System.out.println(exact + ": " + Long.toBinaryString(Double.doubleToLongBits(exact)));
  }
}

输出：

0.44:   11111111011100001010001111010111000010100011110101110000101001
0.4375: 11111111011100000000000000000000000000000000000000000000000000

Answer 1

如果问题是关于将任何数字四舍五入到预定的二进制精度，你需要做的是：

使用 'Double.doubleToLongBits()`

long

检查指数：如果它太大（exponent+required precision>51，有效位数中的位数），您将无法进行任何舍入，但您不必这样做：数字已经满足您的标准。
如果另一方面exponent+required precision<0，四舍五入的结果总是0。
在任何其他情况下，查看有效数字并抹去第 exponent+required precision 个有效位以下的所有位。
使用 Double.longBitsToDouble()

Answer 2

这是我第一次尝试解决方案，它没有处理@biziclop 回答中的所有情况，可能 "floor" 而不是 "round"

public static double round(double d, int precision) {
  double longPart = Math.rint(d);
  double decimalOnly = d - longPart;
  long bits = Double.doubleToLongBits(decimalOnly);

  long mask = -1l << (54 - precision);

  return Double.longBitsToDouble(bits & mask) + longPart;
}

Answer 3

如果你要四舍五入到 2 的任意幂，你将需要一些魔法。

您需要检查指数：

int exponent = Math.getExponent(inexact);

然后知道尾数有53位就可以找到需要舍入的位

或者直接做：

Math.round(inexact* (1l<<exponent))/(1l<<exponent)

我使用 Math.round 因为我希望它最适合任务，而不是尝试自己实施它。

Answer 4

如果你想选择2的幂，最简单的方法就是乘以例如16，舍入到最接近的整数，然后除以 16。请注意，如果结果是正常数，则除以 2 的幂是准确的。它可能会导致次正规数的舍入误差。

下面是一个使用这种技术的示例程序：

public class Test {
  public static void main(String[] args) {
    System.out.println(roundToPowerOfTwo(0.44, 2));
    System.out.println(roundToPowerOfTwo(0.44, 3));
    System.out.println(roundToPowerOfTwo(0.44, 4));
    System.out.println(roundToPowerOfTwo(0.44, 5));
    System.out.println(roundToPowerOfTwo(0.44, 6));
    System.out.println(roundToPowerOfTwo(0.44, 7));
    System.out.println(roundToPowerOfTwo(0.44, 8));
  }

  public static double roundToPowerOfTwo(double in, int power) {
    double multiplier = 1 << power;
    return Math.rint(in * multiplier) / multiplier;
  }
}

输出：

Answer 5

在所有极端情况下都做到这一点有点棘手。如果我必须解决这样的任务，我通常会从一个我可以非常确定是正确的天真的实现开始，然后才开始实现一个优化版本。在这样做的同时，我总是可以与天真的方法进行比较来验证我的结果。

天真的方法是从 1 开始，将它乘以/除以 2，直到我们将输入的绝对值括起来。然后，我们将输出较近的边界。它实际上有点复杂：如果值是 NaN 或无穷大，则需要特殊处理。

代码如下：

public static double getClosestPowerOf2Loop(final double x) {
    final double absx = Math.abs(x);
    double prev = 1.0;
    double next = 1.0;
    if (Double.isInfinite(x) || Double.isNaN(x)) {
        return x;
    } else if (absx < 1.0) {
        do {
            prev = next;
            next /= 2.0;
        } while (next > absx);
    } else if (absx > 1.0) {
        do {
            prev = next;
            next *= 2.0;
        } while (next < absx);
    }
    if (x < 0.0) {
        prev = -prev;
        next = -next;
    }
    return (Math.abs(next - x) < Math.abs(prev - x)) ? next : prev;
}

我希望代码没有进一步解释就清楚了。自 Java 8 起，您可以使用 !Double.isFinite(x) 代替 Double.isInfinite(x) || Double.isNaN(x)。

让我们看看优化版本。正如其他答案已经建议的那样，我们可能应该看看位表示。 Java 要求使用 IEE 754 表示浮点值。在该格式中，double（64 位）精度的数字表示为

1 位符号，
11 位指数和
52 位尾数。

我们将再次对 NaN 和无穷大（由特殊位模式表示）进行特殊处理。然而，还有另一个例外：尾数的最高有效位是隐式 1 并且在位模式中找不到 - 除了非常小的数字，其中所谓的 subnormal 我们在最高有效数字不是尾数最高有效位的情况下使用的表示。因此，对于普通数，我们只需将尾数的位设置为全 0，但对于次正规数，我们将其转换为 none 但保留最高有效位 1 的数字。这个过程总是向零舍入，所以为了得到另一个边界，我们简单地乘以 2。

让我们看看这一切是如何协同工作的：

public static double getClosestPowerOf2Bits(final double x) {
    if (Double.isInfinite(x) || Double.isNaN(x)) {
        return x;
    } else {
        final long bits = Double.doubleToLongBits(x);
        final long signexp = bits  & 0xfff0000000000000L;
        final long mantissa = bits & 0x000fffffffffffffL;
        final long mantissaPrev = Math.abs(x) < Double.MIN_NORMAL
            ? Long.highestOneBit(mantissa)
            : 0x0000000000000000L;
        final double prev = Double.longBitsToDouble(signexp | mantissaPrev);
        final double next = 2.0 * prev;
        return (Math.abs(next - x) < Math.abs(prev - x)) ? next : prev;
    }
}

我完全确定我已经涵盖了所有极端情况，但以下测试确实运行:

public static void main(final String[] args) {
    final double[] values = {
        5.0, 4.1, 3.9, 1.0, 0.0, -0.1, -8.0, -8.1, -7.9,
        0.9 * Double.MIN_NORMAL, -0.9 * Double.MIN_NORMAL,
        Double.NaN, Double.MAX_VALUE, Double.MIN_VALUE,
        Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY,
    };
    for (final double value : values) {
        final double powerL = getClosestPowerOf2Loop(value);
        final double powerB = getClosestPowerOf2Bits(value);
        System.out.printf("%17.10g  -->  %17.10g  %17.10g%n",
                          value, powerL, powerB);
        assert Double.doubleToLongBits(powerL) == Double.doubleToLongBits(powerB);
    }
}

输出：

      5.000000000  -->        4.000000000        4.000000000
      4.100000000  -->        4.000000000        4.000000000
      3.900000000  -->        4.000000000        4.000000000
      1.000000000  -->        1.000000000        1.000000000
      0.000000000  -->        0.000000000        0.000000000
    -0.1000000000  -->      -0.1250000000      -0.1250000000
     -8.000000000  -->       -8.000000000       -8.000000000
     -8.100000000  -->       -8.000000000       -8.000000000
     -7.900000000  -->       -8.000000000       -8.000000000
 2.002566473e-308  -->   2.225073859e-308   2.225073859e-308
-2.002566473e-308  -->  -2.225073859e-308  -2.225073859e-308
              NaN  -->                NaN                NaN
 1.797693135e+308  -->   8.988465674e+307   8.988465674e+307
 4.900000000e-324  -->   4.900000000e-324   4.900000000e-324
        -Infinity  -->          -Infinity          -Infinity
         Infinity  -->           Infinity           Infinity

性能如何？

我有运行以下基准

public static void main(final String[] args) {
    final Random rand = new Random();
    for (int i = 0; i < 1000000; ++i) {
        final double value = Double.longBitsToDouble(rand.nextLong());
        final double power = getClosestPowerOf2(value);
    }
}

其中 getClosestPowerOf2 将替换为 getClosestPowerOf2Loop 或 getClosestPowerOf2Bits。在我的笔记本电脑上，我得到以下结果：

getClosestPowerOf2Loop：2.35 秒
getClosestPowerOf2Bits：1.80 秒

这样做真的值得吗？

Answer 6

我遇到这个 post 试图解决一个相关的问题：如何有效地找到两个包含任何给定常规实值的两个幂。由于我的程序处理双打以外的许多类型，因此我需要一个通用的解决方案。想要四舍五入到最接近的 2 的幂的人可以获得括号值并选择最接近的值。在我的例子中，通用解决方案需要 BigDecimals。这是我使用的技巧。

对于大于 1 的数字：

            int exponent = myBigDecimal.toBigInteger.bitLength() - 1;
            BigDecimal lowerBound = TWO.pow(exponent);
            BigDecimal upperBound = TWO.pow(exponent+1);

对于大于 0 且小于 1 的数字：

            int exponent = -(BigDecimal.ONE.divide(myBigDecimal, myContext).toBigInteger().bitLength()-1); 
            BigDecimal lowerBound = TWO.pow(exponent-1);
            BigDecimal upperBound = TWO.pow(exponent);

我只列出了正面案例。您通常取一个数字，并在其绝对值上使用此算法。然后，如果在原始问题中数字为负，则将算法的结果乘以 -1。最后，原始的 num == 0 或 num == 1 在这个算法之外处理是微不足道的。这涵盖了整个实数线，除了您在调用此算法之前处理的 infinties 和 nans。

两个分数的幂的最近倍数

Nearest multiple of a power of two fraction

java

double

rounding