python - usar - raiz en jupyter

Cómo calcular la enésima raíz de un entero muy grande

Question

Necesito una forma de calcular la enésima raíz de un entero largo en Python.

Intenté pow(m, 1.0/n) , pero no funciona:

OverflowError: long int demasiado grande para convertir a flotación

¿Algunas ideas?

Por entero largo me refiero a enteros realmente largos como:

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

Answer 1

Bueno, si no está particularmente preocupado por la precisión, podría convertirlo en una picadura, cortar algunos dígitos, usar la función de exponente y luego multiplicar el resultado por la raíz de la cantidad que cortó.

Por ejemplo, 32123 es aproximadamente igual a 32 * 1000, la raíz cúbica es aproximadamente igual a la raíz cúbica de 32 * raíz cúbica de 1000. Este último se puede calcular dividiendo el número de 0 por 3.

Esto evita la necesidad del uso de módulos de extensión.

Answer 2

En versiones anteriores de Python, 1/3 es igual a 0. En Python 3.0, 1/3 es igual a 0.33333333333 (y 1//3 es igual a 0).

Entonces, cambie su código para usar 1/3.0 o cambie a Python 3.0.

Answer 3

Intente convertir el exponente a un número flotante, ya que el comportamiento predeterminado de / en Python es la división de enteros

n ** (1 / float (3))

Answer 4

Oh, para números tan grandes, usarías el módulo decimal.

ns: tu número como una cadena

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

y la respuesta es: 2.287391878618402702753613056E + 305

TZ señaló que esto no es exacto ... y tiene razón. Aquí está mi prueba.

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

Está apagado aproximadamente 10 ** 891

Answer 5

Posiblemente por su curiosidad:

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

Esta podría ser la técnica que utilizaría Maple para encontrar realmente la enésima raíz de grandes números.

Plantea el hecho de que x^n - 11968003.... = 0 mod p , y ve desde allí ...

Answer 6

Puede hacer que corra un poco más rápido evitando los bucles while a favor de establecer bajo a 10 ** (len (str (x)) / n) y alto a bajo * 10. Probablemente es mejor reemplazar el len (str (x) )) con la longitud bit a bit y usando un bit shift. Según mis pruebas, calculo una aceleración del 5% desde la primera y una aceleración del 25% desde la segunda. Si las entradas son lo suficientemente grandes, esto podría importar (y las aceleraciones pueden variar). No confíes en mi código sin probarlo con cuidado. Hice algunas pruebas básicas, pero puede haber perdido una caja de borde. Además, estas aceleraciones varían con el número elegido.

Si los datos reales que está utilizando son mucho más grandes que los que publicó aquí, este cambio puede valer la pena.

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)

Norma 0.626754999161

Alt 0.566340923309

Answer 7

Se me ocurrió mi propia respuesta, que toma la idea de @Mahmoud Kassem, simplifica el código y lo hace más reutilizable:

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

Lo probé en Python 3.5.1 y Python 2.7.8, y parecía funcionar bien.

El resultado tendrá tantos dígitos como se especifique en el contexto decimal en el que se ejecuta la función, que de forma predeterminada tiene 28 decimales. De acuerdo con la documentación para la función de power en el módulo decimal , " El resultado está bien definido pero solo" casi siempre redondeado correctamente ". ". Si necesita un resultado más preciso, puede hacerlo de la siguiente manera:

with decimal.localcontext() as context:
context.prec = 50
print(cube_root(42))

Answer 8

Si es un número REALMENTE grande. Puedes usar una búsqueda binaria.

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

Por ejemplo:

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

Answer 9

Si está buscando algo estándar, rápido para escribir con alta precisión. Yo usaría el decimal y ajustaría la precisión (getcontext (). Prec) a al menos la longitud de x.

Código (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)

Responder

x es el número cúbico de 22873918786185635329056863961725521583023133411 451452349318109627653540670761962215971994403670045614485973722724603798 107719978813658857014190047742680490088532895666963698551709978502745901 704433723567548799463129652706705873694274209728785041817619032774248488 2965377218610139128882473918261696612098418

Answer 10

Gmpy es un módulo de extensión Python codificado en C que envuelve la biblioteca GMP para proporcionar al código Python aritmética rápida de multiples medidas (entero, racional y flotante), generación de números aleatorios, funciones avanzadas de números teóricos y más.

Incluye una función root :

x.root (n): devuelve una tupla de 2 elementos (y, m), tal que y es la raíz (posiblemente truncada) n-ésima de x; m, un int Python ordinario, es 1 si la raíz es exacta (x == y ** n), sino 0. n debe ser un int ordinario de Python,> = 0.

Por ejemplo, vigésima raíz:

>>> import gmpy
>>> i0=11968003966030964356885611480383408833172346450467339251
>>> m0=gmpy.mpz(i0)
>>> m0
mpz(11968003966030964356885611480383408833172346450467339251L)
>>> m0.root(20)
(mpz(567), 0)