类似于^ b的快速函数 [英] Fast Function resembling a^b

问题描述

这是一种模糊，但我需要一个可以非常快速计算的函数，并且类似于a ^ b，其中a在0和1之间，b非常大。它将为许多b计算一个a。理想情况下，结果将在0.4％以内。

解决方案

将我的意见转换为答案：

由于您提到 b 足够大，可以四舍五入为整数，所以一种方法是使用 Binary Exponentiation algorithm by squaring。

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; 
} 
 
返回结果; 
 
 
 
 
 $ hr 
 $ b 
这里是我的快速和肮脏的（未优化的）实现：
 
 pre preublic 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; 
} 
 
返回值; 
} 
  

这应该适用于所有肯定的 pow 。但我还没有将它与 Math.pow（）进行比较。

This is kind of obscure, but I need a function that can be computed very quickly and resembles a^b where a is between 0 and 1 and b is very large. It will be calculated for one a at a time for many b's. Ideally, the result would be within 0.4%. Thanks in advance.

解决方案

Pulling my comments into an answer:

Since you mention that b is large enough to be rounded to an integer, then one approach is to use the Binary Exponentiation algorithm by squaring.

Math.pow() is slow because it needs to handle non-integral powers. So might be possible to do better in your case because you can utilize the integer powering algorithms.

---

As always, benchmark your implementation to see if it actually is faster than Math.pow().

---

Here's an implementation that the OP found:

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;

}

---

Here's my quick-and-dirty (unoptimized) implementation:

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;
}

This should work on all positive pow. But I haven't benchmarked it against Math.pow().

这篇关于类似于^ b的快速函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！