¿Por qué es el cuadrado de un número más rápido que la multiplicación de dos números aleatorios?

https://stackoverflow.com/questions/1377430

21-09-2019
|

Pregunta

La multiplicación de dos números binarios se lleva a n^2 tiempo, sin embargo, el cuadrado de un número se puede hacer de manera más eficiente, de alguna manera.(con siendo n el número de bits) ¿Cómo puede ser eso?

O no es posible?Esto es una locura!

Solución

Existen algoritmos más eficientes que O (N ^ 2) para multiplicar dos números (ver Karatsuba, Pollard, Schönhage-Strassen, etc.)
Los dos problemas "multiplicar dos números N bits arbitrarios" y "cuadrado un número de N bits arbitrario" tienen el mismo complejidad.

Tenemos

4*x*y = (x+y)^2 - (x-y)^2

Así que si cuadratura números enteros de N bits lleva tiempo O (f (N)), entonces el producto de dos enteros arbitraria de N bits puede obtenerse en O (f (n)) también. (Es decir 2x sumas de N bits, plazas de N bits 2x, 1x suma 2N bits, y 1x 2N bits de desplazamiento)

Y, obviamente, tenemos

x^2 = x * x

Así que si la multiplicación de dos números enteros de N bits toma O (f (N)), a continuación, elevar al cuadrado un número entero de N bits puede hacerse en O (f (N)).

Cualquier algoritmo de cálculo del producto (RESP el cuadrado) proporciona un algoritmo para calcular el cuadrado (RESP el producto) con el mismo coste asintótica.

Como se ha señalado en otras respuestas, los algoritmos utilizados para la multiplicación rápida pueden simplificarse en el caso de la cuadratura. La ganancia se encuentra a la constante frente a la f (N), y no en f (N) en sí.

Otros consejos

cuadratura un número dígitos n puede ser más rápido que la multiplicación de números de dos dígitos aleatorio n. Buscar en Google encontré este artículo . Se trata de precisión arbitraria, sino que puede ser relevante para lo que su venta. En él los autores dicen lo siguiente:

En la cuadratura un entero grande, es decir, X ^ 2 = (Xn-1, xn-2, ..., x1, x0) ^ 2 muchos términos de productos cruzados de la forma xi * XJ yxj * xi son equivalentes. Ellos necesitar ser calculada solamente una vez y luego izquierda desplazado con el fin de ser duplicado. Una operación de elevación al cuadrado de n dígitos es realizado usando solamente (n ^ 2 + n) / 2 multiplicaciones de precisión simple.

Como otros han señalado, cuadratura sólo puede ser aproximadamente 1,5 veces o 2 veces más rápido que la multiplicación regular entre números arbitrarios. ¿De dónde viene la ventaja computacional viene? Es simetría. Vamos a calcular el cuadrado de 1011 y tratar de detectar un patrón que podemos explotar. u0:u3 representan los bits en el número de los más significativos a los menos significativos.

    1011 //                               u3 * u0 : u3 * u1 : u3 * u2 : u3 * u3
   1011  //                     u2 * u0 : u2 * u1 : u2 * u2 : u2 * u3       
  0000   //           u1 * u0 : u1 * u1 : u1 * u2 : u1 * u3                 
 1011    // u0 * u0 : u0 * u1 : u0 * u2 : u0 * u3

Si se tiene en cuenta la ui * ui elementos para i=0, 1, ..., 4 para formar la diagonal y hacer caso omiso de ellos, verá que los elementos ui * uj para i ≠ j se repite dos veces.

Por lo tanto, todo lo que necesita hacer es calcular la suma del producto de los elementos debajo de la diagonal y duplicarlo, con una desviación a la izquierda. Finalmente agregaría los elementos de la diagonal. Ahora se puede ver dónde está el 2X velocidad viene. En la práctica, la aceleración es de aproximadamente 1,5 veces a causa de las operaciones y diagonales adicionales.

Creo que es posible que se refiere a exponenciación binaria . Esta técnica no se utiliza para multiplicar, pero para elevar a una potencia x ^ n, donde n puede ser grande. En lugar de x se multiplican multiplicado por sí mismo N veces, uno realiza una serie de elevar al cuadrado y la adición de operaciones que se pueden asignar a la representación binaria de N. El número de operaciones de multiplicación (que son más caros que las adiciones de grandes números) se reduce de N a log (N) con respecto al algoritmo de exponenciación ingenuo.

¿Se refiere a multiplicar un número por una potencia de 2? Esto es generalmente más rápido que la multiplicación de dos números aleatorios puesto que el resultado se puede calcular por simple desplazamiento de bits. Sin embargo, tenga en cuenta que los microprocesadores modernos dedican una gran cantidad de fuerza bruta de silicio a este tipo de cálculos y la mayoría aritmética se realiza con una velocidad de vértigo en comparación con los microprocesadores de edad avanzada

Lo tengo!

2 * 2

es más caro que

2 << 1

(La advertencia es que sólo funciona para un caso.)

Supongamos que desea ampliar el (a+b)×(c+d) multiplicación. Se divide en cuatro multiplicaciones individuales:. a×c + a×d + b×c + b×d

Pero si desea ampliar a cabo (a+b)², entonces sólo necesita tres multiplicaciones (y la duplicación):. a² + 2ab + b²

(Tenga en cuenta también que dos de las multiplicaciones son propios cuadrados.)

Esperamos que esto empiece a dar una idea de algunas de las aceleraciones que son posibles cuando se realiza un cuadrado sobre una multiplicación regular.

En primer lugar gran pregunta! Me gustaría que hubiera más preguntas de este tipo.

Así que resulta que el método que se me ocurrió es O (n log n) para la multiplicación en general sólo en la complejidad aritmética. Puede representar cualquier número X como

X = x_{n-1} 2^{n-1} + ... + x_1 2^1 + x_0 2^0
Y = y_{m-1} 2^{m-1} + ... + y_1 2^1 + y_0 2^0

donde

x_i, y_i \in {0,1}

entonces

XY = sum _ {k=0} ^ m+n r_k 2^k

donde

r_k = sum _ {i=0} ^ k x_i y_{k-i}

que es sólo una aplicación recta hacia adelante de FFT para encontrar los valores de r_k para cada k en (n + m) log (n + m) tiempo.

A continuación, para cada r_k debe determinar qué tan grande es el desbordamiento y añadirlo en consecuencia. Para elevar al cuadrado un número, esto significa O (n log n) aritmética operaciones.

Puede añadir hasta los valores r_k más eficientemente usando el algoritmo de Schönhage-Strassen para obtener un O (N log N log log n) operación de bit obligado.

La respuesta exacta a su pregunta ya se ha escrito por Eric Bainville.

Sin embargo, puede conseguir una mejor cota que O (n ^ 2) para elevar al cuadrado un número simplemente porque existen mucho mejores cotas para la multiplicación de números enteros!

Si se supone una longitud fija para el tamaño de la palabra de la máquina y que el número de elevar al cuadrado está en la memoria, una operación de elevar al cuadrado requiere una sola carga de la memoria, por lo que podría ser más rápido.

Para enteros de longitud arbitraria, la multiplicación es típicamente O (N $ ² $) pero hay algoritmos que reducen esta para grandes números enteros.

Si usted asume el enfoque O sencilla (N ²) para multiplicar a por b , a continuación, para cada bit en a usted tiene que cambiar b y añadirlo a un acumulador si ese bit es uno. Para cada bit en a se necesitan cambios y adiciones 3N.

Tenga en cuenta que

( x - y )² = x² - 2 xy + y²

Por lo tanto

x² = ( x - y )² + 2 xy - y²

Si cada y es la mayor potencia de dos no mayor que x, esto da una reducción a un cuadrado inferior, dos turnos y dos adiciones. Como N se reduce en cada iteración, es posible obtener una ganancia de eficiencia (la simetría significa que visita cada punto en un triángulo en lugar de un rectángulo), pero aún así es O (N ²).

Puede haber otra mejor simetría de explotar.

a ^ 2 (A + b) * (a + b) + b ^ 2 por ejemplo. 66 ^ 2 = (66 + 6) (66-6) + 6 ^ 2 = 72 * 60 + 36 = 4356

para un ^ n sólo tiene que utilizar la regla de la potencia

66 ^ 4 = 4356 ^ 2

Me gustaría que para resolver el problema mediante la multiplicación de N bits para un número

A los bits sea A (n-1) A (n-2) ........ A (1) A (0).

B los bits ser B (n-1) B (n-2) ........ B (1) B (0).

para el cuadrado del número A los bits de multiplicación único generado será para A (0) -> A (0) .... A (n-1) A (1) -> A (1) .... A (n-1) y así sucesivamente por lo que las operaciones totales serán

OP = n + n-1 + n-2 ....... + 1 Por lo tanto OP = n ^ 2 + n / 2; por lo que la notación asintótica será O (n ^ 2)

y para la multiplicación de A y B n ^ 2 multiplicaciones único será generada por lo que la notación asintótica será O (n ^ 2)

La raíz cuadrada de 2 ⁿ es de 2 ^{n / 2} o 2 ^{n >> 1}, por lo que si su número es una potencia de dos todo es totalmente sencillo una vez que conoce el poder. Para multiplicar es aún más simple: 2 ⁴ * 2 ⁸ es 2 ^{4 + 8}. No tiene sentido en este declaraciones que ha hecho.

Si usted tiene un número binario A, se puede (siempre, la prueba deja al lector con ganas) puede expresar como (2 ^ n + B), esto puede ser cuadrado como 2 ^ 2n + 2 ^ (n + 1) B + B ^ 2. entonces podemos repetir la expansión, hasta un punto tal que B es igual a cero. No he mirado demasiado duro en ello, pero intuitivamente, se siente como si usted debería ser capaz de hacer una función cuadrada tomar menos pasos algorítmicas que una multiplicación de propósito general.

Creo que está completamente equivocado en sus declaraciones

La multiplicación de dos números binarios se lleva a n^2 tiempo

La multiplicación de dos números de 32 bits tome exactamente un ciclo de reloj.En un procesador de 64 bits, supongo que al multiplicar dos de 64 bits números tienen exactamente 1 ciclo de reloj.Ni siquiera la sorpresa a mi que un procesador de 32 bits se pueden multiplicar dos números de 64 bits en 1 ciclo de reloj.

yet squaring a number can be done more efficiently somehow.

El cuadrado de un número es simplemente multiplicar el número consigo mismo, de modo que es sólo una simple multiplicación.No hay una "plaza" de la operación en la CPU.

Tal vez usted está confuso "cuadrar" con "la multiplicación por una potencia de 2".Multiplicando por 2 puede ser implemeted por el cambio de todos los bits una posición a la "izquierda".Multiplicando por 4 está cambiando todos los bits de dos posiciones a la "izquierda".Por 8, 3 posiciones.Pero este truco sólo se aplica a una potencia de dos.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow