29

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

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

溢出错误：long int 太大而无法转换为浮点数

有任何想法吗？

长整数是指真正的长整数，例如：

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

4

10 回答 10

28

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

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
>>>
于 2008-12-10T14:22:21.443 回答
16

Gmpy是一个 C 编码的 Python 扩展模块，它包装了 GMP 库，为 Python 代码提供快速多精度算术（整数、有理数和浮点数）、随机数生成、高级数论函数等。

包括一个root功能：

x.root(n)：返回一个 2 元素元组 (y,m)，使得 y 是 x 的（可能被截断的）第 n 个根；m，一个普通的 Python int，如果根是精确的 (x==y**n)，则为 1，否则为 0。n 必须是一个普通的 Python int，>=0。

例如，第 20 个根：

>>> import gmpy
>>> i0=11968003966030964356885611480383408833172346450467339251 
>>> m0=gmpy.mpz(i0)
>>> m0
mpz(11968003966030964356885611480383408833172346450467339251L)
>>> m0.root(20)
(mpz(567), 0)
于 2008-12-10T14:17:08.303 回答
7

您可以通过避免使用 while 循环来使其运行速度稍快一些，而支持将低设置为 10 ** (len(str(x)) / n) 并将高设置为低 * 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

于 2008-12-11T00:44:34.683 回答
7

如果您正在寻找标准的东西，请快速以高精度编写。我会使用十进制并将精度（getcontext（）.prec）调整到至少x的长度。

代码（Python 3.0）

from decimal import *

x =   '11968003966030964356885611480383408833172346450467339251\
196093144141045683463085291115677488411620264826942334897996389\
485046262847265769280883237649461122479734279424416861834396522\
819159219215308460065265520143082728303864638821979329804885526\
557893649662037092457130509980883789368448042961108430809620626\
059287437887495827369474189818588006905358793385574832590121472\
680866521970802708379837148646191567765584039175249171110593159\
305029014037881475265618958103073425958633163441030267478942720\
703134493880117805010891574606323700178176718412858948243785754\
898788359757528163558061136758276299059029113119763557411729353\
915848889261125855717014320045292143759177464380434854573300054\
940683350937992500211758727939459249163046465047204851616590276\
724564411037216844005877918224201569391107769029955591465502737\
961776799311859881060956465198859727495735498887960494256488224\
613682478900505821893815926193600121890632'

minprec = 27
if len(x) > minprec: getcontext().prec = len(x)
else:                getcontext().prec = minprec

x = Decimal(x)
power = Decimal(1)/Decimal(3)

answer = x**power
ranswer = answer.quantize(Decimal('1.'), rounding=ROUND_UP)

diff = x - ranswer**Decimal(3)
if diff == Decimal(0):
    print("x is the cubic number of", ranswer)
else:
    print("x has a cubic root of ", answer)

回答

x是22873918786185635329056863961725521583023133411 451452349318109627653540670761962215971994403670045614485973722724603798 107719978813658857014190047742680490088532895666963698551709978502745901 704433723567548799463129652706705873694274209728785041817619032774248488 2965377218610139128882473918261696612098418立方数

于 2009-03-12T04:04:59.007 回答
3

哦，对于那么大的数字，您将使用十进制模块。

ns: 你的数字作为一个字符串

ns = "11968003966030964356885611480383408833172346450467339251196093144141045683463085291115677488411620264826942334897996389485046262847265769280883237649461122479734279424416861834396522819159219215308460065265520143082728303864638821979329804885526557893649662037092457130509980883789368448042961108430809620626059287437887495827369474189818588006905358793385574832590121472680866521970802708379837148646191567765584039175249171110593159305029014037881475265618958103073425958633163441030267478942720703134493880117805010891574606323700178176718412858948243785754898788359757528163558061136758276299059029113119763557411729353915848889261125855717014320045292143759177464380434854573300054940683350937992500211758727939459249163046465047204851616590276724564411037216844005877918224201569391107769029955591465502737961776799311859881060956465198859727495735498887960494256488224613682478900505821893815926193600121890632"
from decimal import Decimal
d = Decimal(ns)
one_third = Decimal("0.3333333333333333")
print d ** one_third

答案是：2.287391878618402702753613056E+305

TZ 指出这不准确……他是对的。这是我的测试。

from decimal import Decimal

def nth_root(num_decimal, n_integer):
    exponent = Decimal("1.0") / Decimal(n_integer)
    return num_decimal ** exponent

def test():
    ns = "11968003966030964356885611480383408833172346450467339251196093144141045683463085291115677488411620264826942334897996389485046262847265769280883237649461122479734279424416861834396522819159219215308460065265520143082728303864638821979329804885526557893649662037092457130509980883789368448042961108430809620626059287437887495827369474189818588006905358793385574832590121472680866521970802708379837148646191567765584039175249171110593159305029014037881475265618958103073425958633163441030267478942720703134493880117805010891574606323700178176718412858948243785754898788359757528163558061136758276299059029113119763557411729353915848889261125855717014320045292143759177464380434854573300054940683350937992500211758727939459249163046465047204851616590276724564411037216844005877918224201569391107769029955591465502737961776799311859881060956465198859727495735498887960494256488224613682478900505821893815926193600121890632"
    nd = Decimal(ns)
    cube_root = nth_root(nd, 3)
    print (cube_root ** Decimal("3.0")) - nd

if __name__ == "__main__":
    test()

大约关闭 10**891

于 2008-12-10T14:29:36.250 回答
2

可能出于你的好奇心：

http://en.wikipedia.org/wiki/Hensel_Lifting

这可能是 Maple 用来实际找到大数的第 n 个根的技术。

摆出事实x^n - 11968003.... = 0 mod p，然后从那里开始......

于 2008-12-10T23:42:49.893 回答
1

我想出了自己的答案，它采用了@Mahmoud Kassem 的想法，简化了代码，并使其更可重用：

def cube_root(x):
    return decimal.Decimal(x) ** (decimal.Decimal(1) / decimal.Decimal(3))

我在 Python 3.5.1 和 Python 2.7.8 中对其进行了测试，似乎运行良好。

结果将具有与运行函数的十进制上下文指定的位数相同的位数，默认情况下为 28 位小数。根据模块中power函数的文档，“结果定义明确，但只是“几乎总是正确舍入”。 “。如果您需要更准确的结果，可以按以下方式完成：decimal

with decimal.localcontext() as context:
    context.prec = 50
    print(cube_root(42))
于 2016-05-11T18:55:54.423 回答
0

在旧版本的 Python 中，1/3等于 0。在 Python 3.0 中，1/3等于 0.33333333333（并且1//3等于 0）。

因此，要么更改您的代码以使用1/3.0或切换到 Python 3.0。

于 2008-12-10T13:57:42.993 回答
-1

尝试将指数转换为浮点数，因为 / 在 Python 中的默认行为是整数除法

n**(1/浮点数(3))

于 2008-12-10T13:54:39.240 回答
-3

好吧，如果你不是特别担心精度，你可以把它转换成一个字符串，去掉一些数字，使用指数函数，然后将结果乘以你切掉的根数。

例如 32123 约等于 32 * 1000，立方根约等于 32 * 1000 的立方根。后者可以通过将 0 的个数除以 3 来计算。

这避免了使用扩展模块的需要。

于 2008-12-10T14:23:20.227 回答