29

Python で長整数の n 乗根を計算する方法が必要です。

試しpow(m, 1.0/n)ましたが、うまくいきません:

OverflowError: long int が大きすぎて float に変換できません

何か案は？

長整数とは、次のような本当に長い整数を意味します。

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 乗根です。通常の Python int である m は、ルートが正確 (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

標準的なものを探している場合は、高精度で高速に記述できます。10 進数を使用し、精度 (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 is the cubic number of 22873918786185635329056863961725521583023133411 451452349318109627653540670761962215971994403670045614485973722724603798 107719978813658857014190047742680490088532895666963698551709978502745901 704433723567548799463129652706705873694274209728785041817619032774248488 2965377218610139128882473918261696612098418

于 2009-03-12T04:04:59.007 に答える
7

low を 10 ** (len(str(x)) / n) に設定し、high を low * 10 に設定することにより、while ループを回避することで、わずかに高速に実行できます。おそらく、len(str(x) を置き換えることをお勧めします。 )) ビット単位の長さとビット シフトを使用します。私のテストに基づいて、1 回目から 5% のスピードアップ、2 回目から 25% のスピードアップを見積もっています。int が十分に大きい場合、これは問題になる可能性があります (スピードアップは異なる場合があります)。慎重にテストせずに私のコードを信用しないでください。いくつかの基本的なテストを行いましたが、エッジ ケースを見逃している可能性があります。また、これらのスピードアップは、選択した数によって異なります。

使用している実際のデータがここに投稿したものよりもはるかに大きい場合、この変更は価値があるかもしれません.

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

Alt 0.566340923309

于 2008-12-11T00:44:34.683 に答える
3

ああ、これほど大きな数値の場合は、decimal モジュールを使用します。

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

これは、大きな数の n 乗根を実際に見つけるために Maple が使用する手法である可能性があります。

という事実を提起し、x^n - 11968003.... = 0 mod pそこから...

于 2008-12-10T23:42:49.893 に答える
0

古いバージョンの Python では、1/30 に等しくなります。Python 3.0 では、1/30.33333333333 に等しくなります (そして1//30 に等しくなります)。

したがって、使用するコードを変更するか1/3.0、 Python 3.0 に切り替えてください。

于 2008-12-10T13:57:42.993 に答える
-1

Python の / のデフォルトの動作は整数除算であるため、指数を浮動小数点数に変換してみてください。

n**(1/float(3))

于 2008-12-10T13:54:39.240 に答える
-3

精度を特に気にしないのであれば、それを文字列に変換し、いくつかの桁を切り捨て、指数関数を使用して、切り捨てた量の根を結果に掛けることができます。

たとえば、32123 は 32 * 1000 にほぼ等しく、立方根は 32 の立方根 * 1000 の立方根にほぼ等しくなります。後者は、0 の数を 3 で割ることによって計算できます。

これにより、拡張モジュールを使用する必要がなくなります。

于 2008-12-10T14:23:20.227 に答える