Comment calculer la racine nième d'un très grand entier

j'ai besoin d'un moyen de calculer la racine nième d'un entier long en Python.

j'ai essayé pow(m, 1.0/n), mais ça ne fonctionne pas:

OverflowError: long int trop grand pour convertir float

des idées?

Par long entier je veux dire vraiment de longs entiers comme:

11968003966030964356885611480383408833172346450467339251 196093144141045683463085291115677488411620264826942334897996389 48504626284726576969280883237649461122479734279424416861834396522 819159219315308460065265520143082728303864638821979329804885526 557893649662037092457130509980883789368448042961108430809620626 059287437887495827369474189818588006905358793385574832590121472 68086652197080270837983714864619156776558403917524917111110593159 305029014037881475265618958103073425958633163441030267478942720 7031344493880117805010891574606323700178176718412858948243785754 898788359757528163558061136758276299059029113119763557411729353 915848889261125855717014320045292143759177464380434854573300054 9406833509379925002117587279394959249163046465047204851616590276 724564411037216844005877918224201569391107769029955591465502737 961776799311859881060956465198859727495735498887960494256488224 613682478900505821893815926193600121890632

24
demandé sur Colonel Panic 2008-12-10 16:49:19
la source

10 ответов

Vous pouvez le faire courir un peu plus vite en évitant les boucles while en faveur du réglage bas à 10 ** (Len(str(x)) / n) et haut à bas * 10. Il est probablement préférable de remplacer le len(str(x)) par le bitwise length et en utilisant un bit shift. D'après mes tests, j'estime une accélération de 5% à partir de la première et de 25% à partir de la seconde. Si les boites sont assez grandes, cela peut avoir de l'importance (et les vitesses peuvent varier). Ne faites pas confiance à mon code sans le tester soigneusement. J'ai fait quelques tests de base mais Mai d'avoir raté un cas limite. De plus, ces vitesses varient selon le nombre choisi.

si les données réelles que vous utilisez sont beaucoup plus grandes que ce que vous avez posté ici, ce changement peut être utile.

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)

Norme 0.626754999161

Alt 0.566340923309

5
répondu Brian 2008-12-11 03:44:34
la source

si c'est un très grand nombre. Vous pouvez utiliser une recherche binaire.

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

Par exemple:

>>> 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
>>>
21
répondu Markus Jarderot 2016-05-12 10:30:50
la source

Gmpy est un module d'extension Python codé en C qui enveloppe la bibliothèque GMP pour fournir au code Python de l'arithmétique de multiprecision rapide (entier, rationnel et flottant), la génération de nombres aléatoires, des fonctions avancées de théorie des nombres, et plus encore.

Si vous cherchez quelque chose de standard, rapide à écrire avec une grande précision. J'utiliserais la décimale et ajusterais la précision (getcontext().prec) au moins à la longueur de X.

Code (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)

Réponse

x est le nombre de cubes 22873918786185635329056863961725521583023133411 45145234931810962765354067076196221597199440367004561448597373722724603798 107719978813658857014190047742680490088532895666963698551709978502745901 7044337235675487994631296527067058737694274209728785041817619032774248488 2965377218610139128882473918261696612098418

6
répondu Mahmoud Kassem 2009-03-12 07:04:59
la source

Oh, pour les nombres big, vous utiliseriez le module décimal.

ns: votre numéro comme chaîne de caractères

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

TZ a fait remarquer que ce n'est pas exact... et il a raison. Voici mon test.

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()

il est éteint d'environ 10* * 891

3
répondu Jim Carroll 2008-12-10 20:24:34
la source

dans les versions plus anciennes de Python,1/3 est égal à 0. En Python 3.0,1/3 est égal à 0,333333333333 (et 1//3 est égal à 0).

alors, changez votre code pour utiliser 1/3.0 ou passer à Python 3.0 .

2
répondu Brian 2008-12-10 16:57:42
la source

peut-être par curiosité:

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

C'est peut-être la technique que Maple utiliserait pour trouver la nième racine des grands nombres.

poser le fait que x^n - 11968003.... = 0 mod p, et à partir de là...

2
répondu Calyth 2008-12-11 02:42:49
la source

j'ai trouvé ma propre réponse, qui prend l'idée de @Mahmoud Kassem, simplifie le code, et le rend plus réutilisable:

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

je l'ai testé en Python 3.5.1 et Python 2.7.8, et il semblait bien fonctionner.

Le résultat aura autant de chiffres que spécifié par la virgule contexte de l'exécution de la fonction, qui par défaut est de 28 décimales. Selon la documentation pour le power fonction dans le decimal module,"le résultat est bien défini mais "presque toujours correctement arrondies".". Si vous avez besoin d'un résultat plus précis, il peut être fait comme suit:

with decimal.localcontext() as context:
    context.prec = 50
    print(cube_root(42))
0
répondu Elias Zamaria 2016-05-11 21:55:54
la source

essayez de convertir l'exposant en un nombre flottant, car le comportement par défaut de / en Python est une division entière

n**(1 / float (3))

-1
répondu Manuel Ferreria 2008-12-10 16:54:39
la source

Eh bien, si vous n'êtes pas particulièrement préoccupé par la précision, vous pouvez le convertir en dard, couper quelques chiffres, utiliser la fonction exposant, puis multiplier le résultat par la racine de combien vous avez coupé.

ceci évite l'utilisation de modules d'extension.

-2
répondu Brian 2008-12-10 17:23:20
la source

Autres questions sur