为什么Math.pow（int，int）比我的天真执行慢？

昨天我看到一个问题，为什么Math.pow(int,int)这么慢，但这个问题措辞不佳，没有显示研究工作，所以很快就关闭了。为什么Math.pow（int，int）比我的天真执行慢？

我做了一些自己的测试，发现Math.pow方法实际上运行速度相对于我自己的天真实现（甚至不是一个特别高效的实现）在处理整数参数时运行得非常慢。下面是我跑测试这个代码：

class PowerTest { 

    public static double myPow(int base, int exponent) { 
     if(base == 0) return 0; 
     if(exponent == 0) return 1; 
     int absExponent = (exponent < 0)? exponent * -1 : exponent; 
     double result = base; 
     for(int i = 1; i < absExponent; i++) { 
      result *= base; 
     } 
     if(exponent < 1) result = 1/result; 
     return result; 
    } 

    public static void main(String args[]) { 
     long startTime, endTime; 

     startTime = System.nanoTime(); 
     for(int i = 0; i < 5000000; i++) { 
      Math.pow(2,2); 
     } 
     endTime = System.nanoTime(); 
     System.out.printf("Math.pow took %d milliseconds.\n", (endTime - startTime)/1000000); 

     startTime = System.nanoTime(); 
     for(int i = 0; i < 5000000; i++) { 
      myPow(2,2); 
     } 
     endTime = System.nanoTime(); 
     System.out.printf("myPow took %d milliseconds.\n", (endTime - startTime)/1000000); 
    } 

}

在我的电脑（在Intel CPU x86_64的Linux）的，输出几乎总是报道，Math.pow了10毫秒，而myPow了2ms的。这偶尔会在这里或那里出现一毫秒的波动，但Math.pow的运行速度大约是，比平均速度慢了5倍。

我做了一些研究，并根据grepcode，Math.pow只提供与(double, double)类型签名的方法，它是推迟到StrictMath.pow方法，它是一个本地方法调用。

Math库只提供处理双打的pow函数的事实似乎表示可能的回答此问题。显然，一个必须处理double类型的基类或指数的可能性的幂运算法则比我的只处理整数的算法需要更长的时间来执行。但最终归结为依赖于体系结构的本机代码（它几乎总是比JVM字节代码运行得更快，在我的情况下可能是C或汇编）。 似乎在这个级别上，如果可能的话，将优化检查数据类型并运行更简单的算法。

鉴于此信息，为什么本机Math.pow方法的运行速度比给定整数参数时未优化和天真的myPow方法慢得多？

来源

2016-01-06 Woodrow Barlow

我对此评论： int absExponent =（exponent <0）？指数* -1：指数; 你不需要'*'： int absExponent =（exponent <0）？ - 指数：指数; –

这甚至不是最优（整数）功率算法 - 有效的算法是if（absExponent＆1 == 0）{result * = result; absExponent >> = 1}' - 即它运行在'O（log n）'而不是'O（n）'时间。 – Alnitak

由于你的实现在指数上使用循环，所以计算正方形是一个非常偏颇的基准。你为什么不在2⁸中尝试这两种方法:)（当然，你可以用一种不那么幼稚的算法做得更好，但即使如此，2 15也可能会给你一个不同的结果。） – rici

正如其他人所说，你不能忽略使用double，因为浮点运算几乎肯定会变慢。然而，这不是唯一的原因 - 如果你改变你的实现来使用它，它仍然更快。

这是因为两件事情：第一是2^2（指数，而不是XOR）是一个非常快速的计算进行，那么你的算法是蛮好用的为 - 尝试使用从Random#nextInt（或nextDouble）两个值你会发现Math#pow实际上更快。

另一个原因是调用本机方法会产生开销，这在这里实际上是有意义的，因为2^2计算起来非常快，而且您多次调用Math#pow。有关详细信息，请参见What makes JNI calls slow?。

来源

2016-01-06 16:50:34 Toby

啊哈！我用'nextInt（1000）'调用替换了所有的参数，现在'Math.pow'方法比我的实现运行速度快得多。所以事实证明这是一个糟糕的测试案例。 –

没有pow(int,int)函数。您正在比较苹果和橘子，并假设您可以忽略浮点数。

来源

2016-01-06 16:43:06 erickson

，但它会传递给本地代码。当然优化会在本地进行？ –

@WoodrowBarlow传递给本地代码的值是'double'。你是否建议如果本地代码检测不到小数部分，应该使用备用路径？参数被转换为整型并用积分算子操作的路径？ – erickson

好吧，当然。有没有理由为什么这是一个坏主意？如果这是一个坏主意，为什么不用一个整型变量重载pow方法？对我来说，这似乎是一个高价值的优化，但我明白，有可能是我失踪的东西。 –

Math.pow速度很慢，因为它涉及一般意义上的等式，使用分数幂将它提升到给定的幂。这是计算时需要经历的查找，需要更多时间。

简单地将数字相乘通常会更快，因为Java中的本地调用效率更高。

编辑：也可能值得注意的是，数学函数使用双精度，这比使用整数还需要更长的时间。

来源

2016-01-06 16:46:59

Math.pow(x, y)是可能是实现为exp(y log x)。这允许分数指数，并且非常快。

但是，如果您只需要小的积极积分参数，您就可以通过编写自己的版本来打败这种表现。

可以说Java可以为你做这个检查，但是对于那些内置版本更快的大整数来说可能会有一点意义。它也必须定义一个适当的整体回报类型和溢出的风险是显而易见的。定义围绕分支区域的行为将会非常棘手。

顺便说一下，你的整型版本可能会更快。通过平方对指数进行一些研究。

来源

2016-01-06 16:53:39 Bathsheba

为什么Math.pow（int，int）比我的天真执行慢？

回答

相关问题