如何计算一个非常大的整数的第n个根 [英] How to compute the nth root of a very big integer

问题描述

我需要一种方法来计算Python中长整数的第n个根.

I need a way to compute the nth root of a long integer in Python.

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

I tried pow(m, 1.0/n), but it doesn't work:

OverflowError:long int太大，无法转换为浮点数

OverflowError: long int too large to convert to float

有什么想法吗?

通过长整数，我的意思是真正的长整数，例如:

By long integer I mean REALLY long integers like:

11968003966030964356885611480383408833172346450467339251 196093144141045683463085291115677488411620264826942334897996389 485046262847265769280883237649461122479734279424416861834396522 819159219215308460065265520143082728303864638821979329804885526 557893649662037092457130509980883789368448042961108108809809620626 059287437887495827369189189818588006905358793385574832590121472 680866521970802708379837148646191567765584039175249171110593159 305029014037881475265618958103073425958633163441030267478942720 703134493880117805010891574606323700178176718412858948243785754 898788359757528163558061136758276299059029113119763557411729353 915848889261125855717014320045292143759177464380434854573300054 940683350937992500211758727939459249163046465047204851616590276 724564411037216844005877918224201569391107769029955591465502737 961776799311859881060956465198859727495735498887960494256488488224 613682478900505821893815926193600121890632

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

推荐答案

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

You can make it run slightly faster by avoiding the while loops in favor of setting low to 10 ** (len(str(x)) / n) and high to low * 10. Probably better is to replace the len(str(x)) with the bitwise length and using a bit shift. Based on my tests, I estimate a 5% speedup from the first and a 25% speedup from the second. If the ints are big enough, this might matter (and the speedups may vary). Don't trust my code without testing it carefully. I did some basic testing but may have missed an edge case. Also, these speedups vary with the number chosen.

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

If the actual data you're using is much bigger than what you posted here, this change may be worthwhile.

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

Norm 0.626754999161

Alt 0.566340923309

Alt 0.566340923309

这篇关于如何计算一个非常大的整数的第n个根的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！