Java中的快速sqrt以牺牲精度为代价

Question

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

有任何想法吗？谢谢!

Answer 1

我不相信(没有基准来证明这是错误的)纯Java实现可能比我快得多Math.sqrt().无论是甲骨文JRE实现和OpenJDK的实施是本地实现.

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