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
10 réponses
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
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
>>>
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.