Python multiplicación larga

Question

Estoy en la necesidad de un algoritmo más rápido que el actual multiplicación larga normal de Python.

Me tratado de encontrar una aplicación decente Karatsuba, pero no puedo.

def main():
    a=long(raw_input())
    if(a<0):
        a=a*-1
        a=((a*(a+1)/2)-1)
        print(-a)
    else:
        a=(a*(a+1))/2
        print(a)
main()

Como se puede ver, no es nada complicado, sólo unas pocas multiplicaciones. Pero tiene que manejar números con hasta 100.000 dígitos en menos de 2,5 segundos.

Me gustaría algún fragmento de una función o simplemente un enlace a algún implementación de una función de multiplicación más rápido, o cualquier cosa que ayude.

Answer 1

Se puede echar un vistazo a la aplicación de la href="http://home.comcast.net/~casevh/" rel="nofollow noreferrer"> DecInt módulo (versión Python puro es gmpy ).

Answer 2

Soy el autor de la DecInt (decimal entero) de la biblioteca, así que va a hacer algunos comentarios.

La biblioteca DecInt fue diseñado específicamente para trabajar con números enteros muy grandes que deben ser convertidos a formato decimal. El problema con la conversión a formato decimal es que la mayoría de las bibliotecas almacenar valores de precisión arbitraria en binario. Esto es más rápida y más eficaz para colocar los memoria, pero la conversión de binario a decimal es por lo general lento. binario de Python a decimal conversión utiliza un O (n ^ 2) algoritmo y obtiene lento muy rápidamente.

DecInt utiliza una gran radix decimal (generalmente 10 ^ 250) y almacena el número muy grande en bloques de 250 dígitos. La conversión de un número muy grande a formato decimal ahora se ejecuta en O (n).

Naive, o escuela primaria, la multiplicación tiene un tiempo de ejecución de O (n ^ 2). Python utiliza multiplicación Karatsuba que ha tiempo de O (n ^ 1.585) que se ejecuta. DecInt utiliza una combinación de Karatsuba, Toom-Cook, y convolución Nussbaumer para obtener un tiempo de ejecución de O (n * ln (n)).

A pesar de que DecInt tiene mucho más alta encima de la cabeza, la combinación de O (n * ln (n)) multiplicación y O conversión (n) con el tiempo será más rápido que el O de Python (n ^ 1.585) multiplicación y O (n ^ 2) conversión.

Como la mayoría de los cálculos no requieren todos los resultados que se muestran en formato decimal, casi todas las bibliotecas de precisión arbitraria utiliza binaria ya que hace que los cálculos más fácil. DecInt se dirige a un nicho muy pequeño. Para cantidades suficientes, DecInt será más rápido para la multiplicación y división que Python nativo. Pero si después de rendimiento puro, una biblioteca como GMPY será el más rápido.

Me alegra que hayas encontrado útil DecInt.

Answer 3

15,9 ms en mi bloc de notas lento. Es la impresión que se está desacelerando. La conversión a números binarios a decimal es bastante lento, lo cual es un paso necesario de imprimirlo. Si necesita dar salida a la cantidad que debe tratar la DecInt ChristopheD ya se ha mencionado.

DecInt será más lenta haciendo la multiplicación, pero que la huella mucho más rápido

In [34]: a=2**333000

In [35]: len(str(a))
Out[35]: 100243

In [36]: b=2**333001

In [37]: len(str(b))
Out[37]: 100244

In [38]: timeit c=a*b
10 loops, best of 3: 15.9 ms per loop

A continuación se muestra un ejemplo con una versión ligeramente modificada de su código. Tenga en cuenta que la conversión de una cadena de dígitos 100000 a una larga ya tiene ~ 1seg en este equipo

In [1]: def f(a):
   ...:     if(a<0):
   ...:         a=a*-1
   ...:         a=((a*(a+1)/2)-1)
   ...:     else:
   ...:         a=(a*(a+1))/2
   ...:     return a
   ...: 

In [2]: a=3**200000

In [3]: len(str(a))
Out[3]: 95425

In [4]: timeit f(a)
10 loops, best of 3: 417 ms per loop

Answer 4

Le sugiero que la href="http://www.sagemath.org/" rel="nofollow noreferrer"> Sage