¿Cómo multiplicar números grandes más rápido?

Estaba experimentando con la multiplicación de grandes números en python. Para mi propósito estaba tratando de evaluar.

2*odd*(4*odd^2 + 7)/3 - 6*odd^2 - 3 

Ahora mi pregunta se reduce a cómo multiplicar números más rápido en python. ¿Es más rápido hacerlo con flotador? La respuesta parece no. Tomemos un ejemplo más simple con

n * (n + 1) / 2

Mi idea fue que el siguiente código es más rápido.

 product = 1 if n % 2 == 0: product *= n/2 product *= n else: product *= (n+1)/2 product *= n return product 

¿Por qué sería esto más rápido? Bueno, no tendrías que dividir el número enorme n*(n+1) entre dos. Sin embargo, uno desperdicia un cálculo comprobando el número módulo2. Tal vez try exception es más rápido?

Así que mi pregunta se reduce a ¿Cómo se calcula el producto y la división de números muy grandes en python? Aquí está mi código de trabajo. No pedir mejoras de velocidad específicamente en este código. Pero la pregunta más amplia sobre cómo lidiar con la división y la multiplicación de grandes números. Mi rango es alrededor de 10^(10^6) atm.

 def spiral_sum_fast(num): rem = num % 6 if rem % 2 == 0: raise Exception("The sidelength must be a odd number") odd = 1 + num / 2 odd_squared = 2 * odd**2 if rem % 3 == 0: temp = odd / 3 temp *= 8 * odd_squared + 14 else: temp = (4 * odd_squared + 7) / 3 temp *= 2 * odd return temp - 3 * odd_squared - 3 if __name__ == '__main__': k = 10**(10**6) + 1 spiral_sum_fast(k) 

En general debes bibliotecas especializadas para trabajos especializados. En su caso, tratar con números grandes y obtener una velocidad óptima puede requerir esto. Eche un vistazo a este blog que trata sobre grandes números y hace comparaciones rápidas entre Python puro y el uso de la biblioteca de aritmética de precisión múltiple GNU de Python, que resulta en una gran mejora de rendimiento.

En primer lugar, 4 * impar ^ 2 + 7 siempre será 2 mod 3. Por lo tanto, no es necesario verificar.

Pero de todos modos no quieres reordenar las operaciones. Considere lo que sucede con la aritmética de enteros de 4 * 5/3 vs 4/3 * 5. El primer resultado es 6. Mientras que el segundo resultado es 5. Con números más grandes obtendría aún más pérdida de información si mueve la división a una posición anterior en el orden de las operaciones.

Otro punto: nunca quieres hacer x**2 . ** usa el poder de C pow() para que tenga un resultado de punto flotante. Solo usa x * x en su lugar. Será más rápido y más preciso.

En cuanto al ejemplo de n*(n+1)/2 , n*(n+1) siempre será divisible entre 2. Y todo lo que hace es desplazar un número grande en 1 bit a la derecha y sabe que el bit tu pierdes es 0

Parece que generalmente estás preocupado por dividir grandes números por pequeños. Pero (como en el primer ejemplo que di), si haces la división demasiado pronto, perderás información y obtendrás respuestas menos precisas. El cálculo tampoco será más rápido. Es posible que necesite trucos como este si divide números grandes por números grandes, pero si divide números grandes por números pequeños (y está usando aritmética de enteros), el resultado será solo unos pocos bits más corto que el número grande con el que comenzó . No será más rápido ni más preciso “dividir temprano” o usar aritmética de punto flotante.

El núcleo de tu pregunta parece ser una variación de “¿qué tan rápido son las operaciones numéricas en Python?” y la respuesta a eso depende de en qué tipo de número estás trabajando y qué tipo de máquina estás usando.

Hay 4 tipos de números en Python: https://docs.python.org/2/library/stdtypes.html#numeric-types-int-float-long-complex

La pregunta de qué tipo de máquina está utilizando afecta si la matemática de punto flotante será rápida o lenta. En su mayor parte, todo el trabajo numérico será eclipsado por la lentitud de la memoria, pero hay algunos casos en los que el conjunto de números en el que está trabajando y todas las instrucciones cabrán en la memoria caché y no estarán limitados por el tiempo de acceso a la memoria.

Entonces, la siguiente pregunta es, ya que una “int” es en realidad una C de 32 bits en python, y una “larga” es algo más grande que eso, ¿son tus intenciones lo suficientemente grandes como para cruzar la barrera 4B en largos? Por lo que parece, sí, así que echemos un vistazo a la implementación del objeto de larga duración de Python: https://github.com/python/cpython/blob/master/Objects/longobject.c

Por lo tanto, es sólo un grupo de int int. Es cierto que es una cadena lineal de ellos, entonces, ¿cuánto tiempo es esa cadena?

 >>> k = 10**(10**6) + 1 >>> k.bit_length()/32 103810 

Ok, la cadena int es más larga que los pocos cientos de ciclos que toma cada golpe a la memoria principal, por lo que podría estar llegando al punto en el que realmente está enlazado a la CPU …

hasta que mires qué tan grande es ese número en realidad .

 >>> k.bit_length()/(8*1024) 405 

405KB? ¿Qué tan grandes son los cachés? http://www.intel.com/content/www/us/en/processors/core/6th-gen-core-family-mobile-uy-processor-lines-datasheet-vol-1.html

Entonces, L1, 64B? L2 es probablemente 256KB? L3 es el que probablemente esté alrededor de 4M. Incluso entonces, ¿cuántos de estos 405KB se mantienen durante el proceso? ¿Cuánta memoria necesita Python para ejecutarse? ¿Estamos golpeando el caché? ¿Qué tan caro es eso?

¿Costo aproximado para acceder a varios cachés y memoria principal?

Esto es lo más lejos que estoy cavando en este agujero por ahora, pero las señales apuntan a la lentitud del agotamiento del caché. Estás utilizando números grandes. Lo grande es más que un concepto matemático, se empuja contra la realidad física de la memoria. El perfil restante de “¿cuántas copias temporales está guardando Python?” y “¿cómo usa el intérprete el rest de la memoria?” Son preguntas interesantes, y más allá del scope de esta respuesta.