如何计算任意幂/根？

Question

我有一个应用程序需要将一个数提高到分数幂。目标平台是FPGA，我可以得到它的FPU大小估计，但我需要一个提高数字到分数幂的算法，只是为了进行可行性研究。我假设最坏情况下使用浮点数，但实际上我们可能能够使用快捷方式，但现在我想展示最坏情况可以在我们这边实现。

我想在这里问问是否有任何常见的方法，我可以查看一下。我知道有软件方法可以做到这一点，但我想先从一个相当有效的算法开始。 FPGA实现的问题以后再考虑。

- NoMoreZealots

Answer 1

你的输入范围是任意的还是在某个范围内已知？

无论哪种情况，x^m = exp(m log x)，因此如果您可以创建函数来评估exp(x)和log(x)，并且有一个乘法运算，那么您可能已经准备好了。

您将不得不确定如何处理x的非正值。

(log(x)的提示：如果这是IEEE-754浮点数，则根据需要移动有效数字，直到您最终获得一系列介于2^k和2^k+1之间的数字。这使您能够处理2:1范围，该范围不太难用多项式近似。然后您只需处理少量的指数和移位数即可。

exp(x)的相应提示：编写x = k+b，其中0 <= b < 1且k为整数。然后exp(x) = exp(k)*exp(b); b具有有限的范围，而k具有有限数量的离散可能性。)

（提示2：对于x ^m = g（m f（x）），其中f（x）= log ₂ x和g（x）= 2 ^x ，数字可能更好地工作。）

- Jason S

---

我现在假设是任意的，我需要阅读更多有关我们正在执行的计算背后的系统理论。现在我们只是试图向客户提出一个解决方案。我只想分析性地证明它可以在我们的系统上完成。 - NoMoreZealots

我之前曾经参与过一个奇怪的运行时项目，它缺乏完整的函数式编程库，但是提供了 frexp/ldexp 例程来分离和重新组合指数和尾数；由此，构建标准的函数式编程函数变得相当简单直接。 - Jeffrey Hantin

实际上，对于特定的一个案例，指数看起来将会大于1。我不确定这对所有情况都适用。 - NoMoreZealots

Answer 2

正如Jason S所说，这是通过公式x^m = exp(m log x)得出的。但在实践中，你必须处理截断误差。

1. 使用这个公式：x^m = (2ⁿ * x / 2ⁿ)^m = 2^nm * (x/2ⁿ)^m，并找到一个整数n使得1 <= x/2ⁿ < 2。
2. 计算t = log2(x / 2ⁿ)。这可以用足够高阶的泰勒级数或牛顿-拉弗森方法来完成。你必须确保在区间[1,2[上的最大误差对于您来说不太大。
3. 计算u = nm + tm。
4. 我们现在的目标是计算2^u。利用2^u = 2^v * 2^u-v的事实，找到一个整数v使得0 <= u-v < 1。
5. 再次使用我们的好朋友Taylor或Newton-Raphson计算w = 2^u-v。感兴趣的区间是0 <= u-v < 1。
6. 你的答案现在是2^v * w。

- erikkallen

---

你如何使用牛顿-拉弗森方法来计算对数函数？我可以找到使用它的除法算法，但是在谷歌上有太多“噪音”，以至于无法找到如何使用它来计算对数。 - NoMoreZealots

我想我记得从我的计算理论中，这是可能的，但我可能错了。我不是数学家。 - erikkallen

你可以用它来计算任何函数 - 它基本上是一个数值求解器，用于 f(x) = 0，给定一对起始点 x1、x2 和保证解在两者之间。 - qdot