我正在寻找一种可以有效计算 b^e 的算法其中 b和 e是有理数，确保近似误差不会超过给定的 err (也是理性的)。明确地说，我正在寻找一个函数:
rational exp(rational base, rational exp, rational err)
这将保护法律 |exp(b, e, err) - b^e| < err
有理数表示为成对的大整数。让我们假设所有保持合理性的操作(如加法、乘法等)都已定义。
我已经找到了几种方法，但它们都不能让我足够清楚地控制错误。在这个问题中，我不关心整数溢出。实现这一目标的最佳方法是什么？
最佳答案
这个很复杂，所以我将概述我将采用的方法。我不保证没有错误，您还有很多工作要做。
我会把你说的变量改成exp(x, y, err)成为x^y错误内err .如果y不在 0 <= y < 1 范围内, 然后我们可以很容易地乘以适当的 x^k与 k一个整数，使之成为现实。所以我们只需要担心小数 `y
如果所有的分子和分母都很小，那么解决这个问题就很容易了，方法是先取整数次幂，然后使用牛顿法求根。但是当你试图估计类似 (1000001/1000000)^(2000001/1000000) 的东西时，这个天真的想法会痛苦地崩溃。 .因此，挑战在于防止它在您身上爆炸。
我建议看看计算 x^y 的问题作为x^y = (x0^y0) * (x0^(y-y0)) * (x/x0)^y = (x0^y0) * e^((y-y0) * log(x0)) * e^(y * log(x/x0)) .而我们会选择x0和 y0这样计算更容易并且误差有限。
为了限制错误，我们可以先想出一个朴素的上限 b在 x0^y0 - 类似于“下一个高于 x 的下一个最高整数的幂 y ”。我们会选择x0和 y0足够接近x和 y后面的条款在 2 下.然后我们只需要将这三个项估计在 err/12 内, err/(6*b)和 err/(6*b) . (您可能希望将这些错误缩小一半，然后使最终答案接近有理数。)
现在当我们选择 x0和 y0我们的目标是“用小分子/分母接近有理数”。为此，我们开始计算 continued fraction .这给出了一个快速收敛到目标实数的有理数序列。如果我们很快切断序列，我们可以快速找到一个有理数，它在目标实数的任何所需距离内，同时保持相对较小的分子和分母。
让我们从第三个学期开始倒推。
我们想要y * log(x/x0) < log(2) .但是来自泰勒级数如果x/2 < x0 < 2x然后log(x/x0) < x/x0 - 1 .所以我们可以在连分数中搜索合适的 x0 .
一旦我们找到它，我们就可以使用泰勒级数来计算log(1+z)。计算log(x/x0)在err/(12*y*b)内.然后是 e^z 的泰勒级数计算我们期望误差的项。
第二项更复杂。我们需要估算log(x0) .我们要做的是找到一个合适的整数 k这样 1.1^k <= x0 < 1.1^(k+1) .然后我们可以估计两个k * log(1.1)和 log(x0 / 1.1^k)相当准确。找到 log 的朴素上限并用它来找到足够接近的 y0使第二项在2以内。然后用泰勒级数估计e^((y-y0) * log(x0))达到我们想要的精度。
对于第一项，我们使用提高 x0 的朴素方法到一个整数，然后用牛顿法求根，得到 x0^y0达到我们想要的精度。
然后将它们相乘，我们就有了答案。 (如果您选择“更严格的错误，更好的答案”，那么现在您将对该答案进行连分数以选择一个更好的理性返回。)
关于algorithm - 具有误差控制的有理幂根的有理逼近，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55656498/