如何有效地提高整数到分数次幂？

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^(1/p)=exp(ln(n)/p) ~~ 1+ln(n)/p对于大p值

所以你可以比较p和n的自然对数，如果p/ln（n）>1（大得多），那么你可以使用上面的近似值（趋于1）

Answer 2

除非你的n的值也非常大，floor(n^(1/p))对于p的“非常非常大”的值将趋向于1。因为你只对整数部分感兴趣，你可以通过一个简单的循环来测试1^p，2^p，3^p等等是否大于n

如果不需要，请不要浪费时间寻找精确的值。在