快速计算类似于a^b的函数

Question

快速计算类似于a^b的函数

javaperformancefunctionpow

3

这有点晦涩，但我需要一个函数，它可以非常快地计算，并且类似于a^b，其中a介于0和1之间，而b非常大。它将逐个a计算许多b。理想情况下，结果应在0.4％以内。提前致谢。

- Fractaly

“b” 是整数吗？或者，“b” 是否足够大，可以四舍五入为整数？ - Mysticial

是的，b足够大以四舍五入为整数。 - Fractaly

3

好的，请查看二进制指数算法。通过正确的优化，它可能比Math.pow()更快。 - Mysticial

谢谢。我应该递归地做，还是那样会变得非常缓慢并容易出现堆栈溢出？ - Fractaly

它不会深到导致堆栈溢出。但我建议使用迭代实现而不是递归实现。 - Mysticial

b之前发生了1000000个堆栈溢出。 - Fractaly

3个回答

2

对于您具体的情况（“为许多b一个接一个地计算一次a”），我建议采用以下方法：

准备表格数据以在特定计算中使用：

确定 N，使得对于每个可能的 b，2^N 小于 b。
计算表 t：对于每个小于 N 的 n，t[n]=a^(2^n)。这实际上是通过 t[k+1]=t[k]*t[k] 来完成的。

计算 a^b：

使用二进制表示的 b，将 a^b 计算为 t[i1]t[i2]...*t[ik]，其中 i1..ik 是 b 的二进制表示中非零位的位置。

这个想法是为不同的 b 重复使用 a^(2^n) 的值。

- Alexei Kaigorodov

0

Apache FastMath 提供了 double pow(double d, int e) 函数，用于指数为整数的情况。

其实现基于 Veltkamp 的 TwoProduct 算法。使用方式与标准的 Math.pow 函数类似：

import org.apache.commons.math3.util.FastMath;
// ...
FastMath.pow(3.1417, 2);

- Tombart

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mysticial · Accepted Answer

将我的评论转化为答案：

既然您提到 b 足够大以被舍入为整数，那么一种方法是使用二进制幂算法进行平方运算。 Math.pow()很慢，因为它需要处理非整数次幂。因此，在您的情况下，可能可以更好地利用整数幂算法。

像往常一样，对您的实现进行基准测试，以查看它是否比Math.pow()更快。

以下是OP发现的实现：

public static double pow(double a, int b) {
    double result = 1;
    while(b > 0) {
        if (b % 2 != 0) {
            result *= a;
            b--;
        } 
        a *= a;
        b /= 2;
    }

    return result;

}

这是我的快速而不精细（未经优化）实现代码：

public static double intPow(double base,int pow){
    int c = Integer.numberOfLeadingZeros(pow);

    pow <<= c;

    double value = 1;
    for (; c < 32; c++){
        value *= value;
        if (pow < 0)
            value *= base;
        pow <<= 1;
    }

    return value;
}

这应该适用于所有正的pow。但我还没有与Math.pow()进行基准测试。