Java中快速计算n次方根

Question

在我的Java程序中，我经常需要计算a^b，其中a ≥ 0且0 ≤ b < 1。我对Math.pow(a, b)的速度不满意。是否有任何算法可能比Math.pow更快（以某种精度代价）？

- Ričards Marcinkevičs

---

也许泰勒级数的较短部分（http://stackoverflow.com/questions/4453421/implement-generic-power-function-without-using-math-pow-in-java）会更有用？根据应用程序，缓存结果可能是有用的。 - J Fabian Meier

如果可用，使用exp(b*log(a))或其基数2变体可能会得到更快的结果。这在某些情况下会产生明显的浮点错误，但避免了更专业版本的pow包含的减少这些错误的开销。 - Lutz Lehmann

你有关于这些a和b分布的更多信息吗？你可以预先计算表格吗？难道没有解决方法来避免需要计算这些幂次吗？更多上下文会很有用。 - user1196549

你可以尝试以下方法： y = a^b = (m * 2^e)^b = m ^b * 2^(eb) = m^b * 2^(eb - E) * 2^E 这里，E = 最接近的整数(eb)，且 |eb-E| < 1/2 可以通过多项式计算 m^b 和 2^(e*b-E) 根据所需精度选择多项式的次数即可。我使用 Sollya 来查找多项式 链接。 - kanna

Answer 1

你需要精确的结果还是只需要一个近似值？

如果需要精确的结果：那很困难。

如果你只需要一个近似值：可以尝试使用N次根算法进行不动点迭代，在维基百科上有描述。

然后，你可以根据你的应用程序需要使用尽可能多的时钟周期来进行第N次根的近似值计算。但我猜想，Math.pow已经为你实现了这些功能。如果你想要更快地运行它，你需要投入一些严肃的努力。即使在C语言中（我比Java更擅长），编写一个真正快速的版本也不是一件容易的事情（如果我一直在做n次根计算，并且它们是绝对的瓶颈，我会采用多线程和如果可能的话，使用SIMD/AVX指令进行大量的工作，甚至使用OpenCL/CUDA）。

- ArchimedesMP

---

我也喜欢@uzr提出的问题。该问题本身及其被接受的答案涉及整数指数，实际上在您的情况下并不是那么有用。但是用户“sbi”关于“突破性加速”的观点非常好，并且在任何程序优化案例中都非常适用 - 这可能值得您考虑。 - ArchimedesMP

提到OpenCL和CUDA是一个很好的想法，这也是我要建议的。 - Michael

Answer 2

我相信在Java标准数学库中很难找到比它更优化的数学库。也许你应该考虑其他优化，例如缓存频繁使用的值，以便可以重复使用而不是重新计算，从而减少所做的计算次数。

如果查找第n个根非常关键，也许您应该考虑另一种语言，可能比Java具有更快的执行时间，或者可以更有效地执行幂运算。

即使实验是在C中进行的，这也可能很有趣什么更有效？使用pow平方还是只是将其乘以自己？。

- uzr