我正在寻找一种算法，可以有效地计算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我们的目标是“分子/分母较小的接近理性”。为此，我们开始计算连分数。这给出了一个快速收敛到目标实数的有理数序列。如果我们很快切断序列，我们可以快速找到一个在目标实数的任何所需距离内的有理数，同时保持相对较小的分子和分母。
让我们从第三个任期倒过来。
我们想要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达到我们想要的精度。
然后将它们相乘，我们就有了答案。（如果您选择“更严格的错误，更好的答案”，那么现在您将对该答案进行连续分数以选择更好的理性回归。）