java - Java中的快速sqrt以牺牲准确性为代价

Question

我正在为 [0, 2*10^12] 的输入范围内的双精度值寻找 Java 中的快速平方根实现。对于此范围内的任何值，精度应为小数点后 5 位。换言之，结果可能与Math.sqrt()小数点后 5 位的方法不同。但是，这种方法需要比Math.sqrt().

有任何想法吗？谢谢！

Answer 1

我不相信（没有基准来证明这是错误的）纯 Java 实现可以比. Oracle JRE 实现和OpenJDK 实现Math.sqrt()都是本机实现。

Answer 2

一旦你给代码时间预热。Math.sqrt() 可以非常快

static double[] values = new double[500 * 1000];

public static void main(String... args) {
    for (int i = 0; i < values.length; i++) values[i] = i;

    for (int j = 0; j < 5; j++) {
        long start = System.nanoTime();

        for (int i = 1; i < values.length; i++) {
            values[i] = Math.sqrt(values[i]);
        }
        long time = System.nanoTime() - start;

        System.out.printf("Took %d ns to Math.sqrt on average%n", time / values.length);
    }
}

印刷

Took 20 ns to Math.sqrt on average
Took 22 ns to Math.sqrt on average
Took 9 ns to Math.sqrt on average
Took 9 ns to Math.sqrt on average
Took 9 ns to Math.sqrt on average

Answer 3

试试这个

double d = 289358932.0;
double sqrt = Double.longBitsToDouble( ( ( Double.doubleToLongBits( d )-(1l<<52) )>>1 ) + ( 1l<<61 ) );

我没有对它进行基准测试，但我希望它会更快。准确性不是很好，但请尝试一下，看看它是否满足您的需求。我认为您可以在表达式的末尾添加一个额外的偏差项a以使其更准确。

编辑：您可以通过一两轮牛顿法来大幅提高准确性

double better = (sqrt + d/sqrt)/2.0;
double evenbetter = (better + d/better)/2.0;

第二遍为您提供几乎精确的平方根值。

sqrt            17022.533813476562
better          17010.557763511835
evenbetter      17010.553547724947
Math.sqrt()     17010.553547724423