我想在Python3中计算一个非常大的数的立方根。
我尝试了下面的函数以及 Python 语法 x ** (1/n)
,但它们都会产生错误:
OverflowError: (34, 'Numerical result out of range')
我确实需要计算立方根来解决密码学问题。除了数学之外,我无法使用任何模块。
二分查找:
def find_invpow(x,n):
"""Finds the integer component of the n'th root of x,
an integer such that y ** n <= x < (y + 1) ** n.
"""
high = 1
while high ** n < x:
high *= 2
low = high/2
while low < high:
mid = (low + high) // 2
if low < mid and mid**n < x:
low = mid
elif high > mid and mid**n > x:
high = mid
else:
return mid
return mid + 1
导致错误的示例数字是:
num = 68057481137876648248241485864416419482650225630788641878663638907856305801266787545152598107424503316701887749720220603415974959561242770647206405075854693761748645436474693912889174270087450524201874301881144063774246565393171209785613106940896565658550145896382997905000280819929717554126192912435958881333015570058980589421883357999956417864406416064784421639624577881872069579492555550080496871742644626220376297153908107132546228975057498201139955163867578898758090850986317974370013630474749530052454762925065538161450906977368449669946613816
结果应该是这样的(这是 gmpy2 找到的并且它是正确的 - 我已经验证过):
408280486712458018941011423246208684000839238529670746836313590220206147266723174123590947072617862777039701335841276608156219318663582175921048087813907313165314488199897222817084206
最佳答案
您的问题是您没有严格遵守整数。 Python 的整数是动态调整大小的,因此它们可以适合您想要的任何大小的值,而不会丢失任何精度。但 float 的精度本质上是有限的。
当您执行low = high/2
时,您将获得浮点计算,即使您无意这样做。由于 low
是一个 float ,mid
最终也为 1,当您测试 mid
的立方体时, float 最终会溢出,并且您获得异常(exception)。
如果您将 low
的第一个计算更改为使用 //
而不是 /
,您将在整个计算过程中坚持使用整数,并且您不会遇到溢出异常。只需进行一次更改,我就能够运行您的代码并获得您期望的结果:
>>> find_invpow(num, 3)
408280486712458018941011423246208684000839238529670746836313590220206147266723174123590947072617862777039701335841276608156219318663582175921048087813907313165314488199897222817084206
关于python - 仅使用数学库计算非常大的数的立方根,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55436001/