python - 仅使用数学库计算非常大的数的立方根

Question

我想在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

Answer 1

您的问题是您没有严格遵守整数。 Python 的整数是动态调整大小的，因此它们可以适合您想要的任何大小的值，而不会丢失任何精度。但 float 的精度本质上是有限的。

当您执行low = high/2时，您将获得浮点计算，即使您无意这样做。由于 low 是一个 float ，mid 最终也为 1，当您测试 mid 的立方体时， float 最终会溢出，并且您获得异常(exception)。

如果您将 low 的第一个计算更改为使用 // 而不是 /，您将在整个计算过程中坚持使用整数，并且您不会遇到溢出异常。只需进行一次更改，我就能够运行您的代码并获得您期望的结果:

>>> find_invpow(num, 3)
408280486712458018941011423246208684000839238529670746836313590220206147266723174123590947072617862777039701335841276608156219318663582175921048087813907313165314488199897222817084206