如何计算一个非常大的整数的第n个根

如何计算一个非常大的整数的第n个根

通过避免将while循环设置为从低到10 *（len（str（x））/ n）和从高到低 10，可以使其运行速度稍快一些。最好是替换len（str（x
）），按位长度并使用位移。根据我的测试，我估计第一个加速了5％，第二个加速了25％。如果int足够大，则这可能很重要（并且加速可能会有所不同）。如果不仔细测试，请不要相信我的代码。我做了一些基本的测试，但是可能错过了一个极端的案例。而且，这些加速会随所选的数量而变化。

如果您使用的实际数据远大于您在此处发布的数据，则此更改可能是值得的。

from timeit import Timerdef 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 + 1def find_invpowAlt(x,n):    """Finds the integer component of the n'th root of x,    an integer such that y ** n <= x < (y + 1) ** n.    """    low = 10 ** (len(str(x)) / n)    high = low * 10    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 + 1x = 237734537465873465n = 5tests = 10000print "Norm", Timer('find_invpow(x,n)', 'from __main__ import find_invpow, x,n').timeit(number=tests)print "Alt", Timer('find_invpowAlt(x,n)', 'from __main__ import find_invpowAlt, x,n').timeit(number=tests)

规范0.626754999161

Alt 0.566340923309