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

Question

我需要一种方法来计算 Python 中长整数的 n 次方根。

我尝试 pow(m, 1.0/n) ，但它不起作用：

OverflowError：long int 太大而无法转换为 float

有任何想法吗？

对于长整数，我的意思是真正的长整数，例如：

11968003966030964356885611480383408833172346450467339251 196093144141045683463085291115677488411620264826942334897996389 485046262847265769280883237649461122479734279424416861834396522 819159219215308460065265520143082728303864638821979329804885526 557893649662037092457130509980883789368448042961108430809620626 059287437887495827369474189818588006905358793385574832590121472 680866521970802708379837148646191567765584039175249171110593159 305029014037881475265618958103073425958633163441030267478942720 703134493880117805010891574606323700178176718412858948243785754 898788359757528163558061136758276299059029113119763557411729353 915848889261125855717014320045292143759177464380434854573300054 940683350937992500211758727939459249163046465047204851616590276 724564411037216844005877918224201569391107769029955591465502737 961776799311859881060956465198859727495735498887960494256488224 613682478900505821893815926193600121890632

原文由 PiX 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以通过避免 while 循环而将 low 设置为 10 ** (len(str(x)) / n) 并将 high 设置为 low * 10 来使其运行得稍微快一些。可能更好的方法是替换 len(str(x )) 按位长度并使用位移。根据我的测试，我估计比第一个提速 5%，比第二个提速 25%。如果整数足够大，这可能很重要（并且加速可能会有所不同）。未经仔细测试，不要相信我的代码。我做了一些基本测试，但可能错过了一个边缘案例。此外，这些加速因所选数量而异。

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

 from timeit import Timer

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

def 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 + 1

x = 237734537465873465
n = 5
tests = 10000

print "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

备用 0.566340923309

原文由 Brian 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

如果它是一个非常大的数字。您可以使用二进制搜索。

 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

例如：

 >>> x = 237734537465873465
>>> n = 5
>>> y = find_invpow(x,n)
>>> y
2986
>>> y**n <= x <= (y+1)**n
True
>>>
>>> x = 119680039660309643568856114803834088331723464504673392511960931441>
>>> n = 45
>>> y = find_invpow(x,n)
>>> y
227661383982863143360L
>>> y**n <= x < (y+1)**n
True
>>> find_invpow(y**n,n) == y
True
>>>

原文由 Markus Jarderot 发布，翻译遵循 CC BY-SA 3.0 许可协议