algorithm - 如何计算任意功率/根？

Question

我有一个应用程序需要将数字提高到分数幂。目标平台是 FPGA，我可以估计它的 FPU 大小，但我需要一种算法来将数字提升到分数幂，仅用于可行性研究。我假设浮点是最坏的情况，我希望在实践中我们能够使用捷径，但现在我想证明我们可以实现最坏的情况。

以为我会在这里问，看看是否有任何我可以结帐的常用方法。我知道有这样做的软件方法，我只想要一个相当有效的算法开始。我会担心 FPGA 的实现。

Answer 1

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

在任何一种情况下，x ^m = exp(m log x)，所以如果您可以创建函数来评估 exp(x) 和 log(x) 并进行乘法运算，那么您可能已经准备就绪。

你必须弄清楚你想如何处理 x 的非正值。

（对 log(x) 的提示：如果这是IEEE-754 浮点数，则在必要时移动有效位，直到对于某个值 K，最终得到介于 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(mf(x)) 其中 f(x) = log ₂ x 和 g(x) = 2 ^x ，这些数字可能会更好。）

Answer 2

As Jason S said, this is done using the identity x^m = exp(m log x). In practice though, you will have to deal with truncation errors. I think that the way this is usually done is

1. Use this identity: x^m = (2ⁿ * x / 2ⁿ)^m = 2^nm * (x/2ⁿ)^m and find an integer n such that 1 <= x/2ⁿ < 2.
2. Calculate t = log2(x / 2ⁿ). This can be done either using a sufficiently high degree Taylor expansion, or with good ol' Newton-Raphson. You have to make sure that the maximum error over the interval [1, 2[ is not too large for you.
3. Calculate u = nm + tm.
4. Our goal is now to calculate 2^u. Use the fact that 2^u = 2^v * 2^u-v and find an integer v such that 0 <= u-v < 1.
5. Calculate w = 2^u-v, again using our friend Taylor or Newton-Raphson. The interval of interest is 0 <= u-v < 1.
6. Your answer is now 2^v * w.