3

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

4

3 回答 3

2

对于您的特定情况（“一次计算一个 a 的多个 b”），我建议采用以下方法：

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

  • 确定 N 使得 2^N 对于每个可能的 b 都小于 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) 的值。

于 2012-09-22T07:11:29.713 回答
2

将我的评论纳入答案：

既然您提到它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().

于 2012-09-22T06:48:00.980 回答
0

Apache FastMathdouble pow(double d, int e)为指数为整数的情况提供函数。

该实现基于 Veltkamp 的 TwoProduct 算法。用法类似于标准Math.pow函数：

import org.apache.commons.math3.util.FastMath;
// ...
FastMath.pow(3.1417, 2);
于 2018-04-30T12:51:34.970 回答