如何高效地将整数提升为分数幂？

Question

我在Python中实现了一个二分查找的功能。现在我想检查一个元素 math.floor(n ^ (1/p)) 是否在我的二分查找中。但是，p是一个非常非常大的数字。我使用了 fractions module 来编写代码：

binary_search.search(list,int (n**fractions.Fraction('1'+'/'+str(p))))

但是我遇到了一个错误 OverflowError: integer division result too large for a float。我该如何快速地计算n的一个分数次方呢？

Answer 1

这个公式的意思是，当你有一个数字n和一个很大的p时，n的1/p次方可以用另外一种方式来表示，就是用指数和对数的形式。具体来说，就是用这个公式：n^(1/p)=exp(ln(n)/p) ~~ 1+ln(n)/p。

在这里，你可以把p和n的自然对数（也就是ln(n)）进行比较。如果p和ln(n)的比值p/ln(n)远远大于1，也就是说p比ln(n)大得多，那么你就可以用上面的近似公式来计算，这个近似值会接近1。

Answer 2

除非你的 n 值也非常大，否则当 p 的值变得“非常非常大”时，floor(n^(1/p)) 的结果会趋近于 1。因为你只关心整数部分，所以你可以用一个简单的循环来测试 1^p、2^p、3^p 等等是否大于 n。

如果你不需要精确的值，就不要浪费时间去找它们。