algorithm - simulacion - random numeros decimales
¿Por qué cuadrar un número es más rápido que multiplicar dos números aleatorios? (13)
Multiplicar dos números binarios lleva n ^ 2 tiempo, pero cuadrar un número se puede hacer de una manera más eficiente. (siendo n el número de bits) ¿Cómo podría ser eso?
¿O acaso no es posible? ¡Esto es una locura!
Existen algoritmos más eficientes que O (N ^ 2) para multiplicar dos números (ver Karatsuba, Pollard, Schönhage – Strassen, etc.)
Los dos problemas "multiplican dos números arbitrarios de N bits" y "Cuadrado un número arbitrario de N bits" tienen la misma complejidad.
Tenemos
4*x*y = (x+y)^2 - (x-y)^2
Por lo tanto, si cuadrar los enteros de N bits toma O (f (N)) el tiempo, entonces el producto de dos enteros de bits N arbitrarios también se puede obtener en O (f (N)). (esto es 2x sumas de N bits, 2x cuadrados de N bits, 1x suma de 2N bits y 1x desplazamiento de 2N bits)
Y obviamente tenemos
x^2 = x * x
Por lo tanto, si la multiplicación de dos enteros de N bits toma O (f (N)), el cuadrado de un entero de N bits se puede hacer en O (f (N)).
Cualquier algoritmo que calcule el producto (resp el cuadrado) proporciona un algoritmo para calcular el cuadrado (resp el producto) con el mismo costo asintótico.
Como se señaló en otras respuestas, los algoritmos utilizados para la multiplicación rápida se pueden simplificar en el caso de la cuadratura. La ganancia estará en la constante frente a f (N), y no en f (N) en sí.
¡Lo tengo!
2 * 2
es mas caro que
2 << 1
(La advertencia es que solo funciona para un caso).
¿Quieres decir multiplicar un número por una potencia de 2? Esto suele ser más rápido que multiplicar dos números aleatorios ya que el resultado se puede calcular mediante un simple desplazamiento de bits. Sin embargo, tenga en cuenta que los microprocesadores modernos dedican gran cantidad de silicio de fuerza bruta a este tipo de cálculos y la mayor parte de la aritmética se realiza con una velocidad de cegamiento en comparación con los microprocesadores más antiguos.
Ante todo una gran pregunta! Ojalá hubiera más preguntas como esta.
Así que resulta que el método que se me ocurrió es O (n log n) solo para la multiplicación general en la complejidad aritmética. Puedes 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
dónde
x_i, y_i /in {0,1}
entonces
XY = sum _ {k=0} ^ m+n r_k 2^k
dónde
r_k = sum _ {i=0} ^ k x_i y_{k-i}
que es solo una aplicación directa de FFT para encontrar los valores de r_k para cada k en el tiempo de registro (n + m) (n + m).
Luego, para cada r_k debe determinar qué tan grande es el desbordamiento y agregarlo en consecuencia. Para cuadrar un número, esto significa O (n log n) operaciones aritméticas .
Puede sumar los valores r_k de manera más eficiente utilizando el algoritmo de Schönhage-Strassen para obtener un límite de operación de bit O (n log n log log n).
La respuesta exacta a su pregunta ya está publicada por Eric Bainville.
Sin embargo, puede obtener un límite mucho mejor que O (n ^ 2) para cuadrar un número simplemente porque existen límites mucho mejores para multiplicar enteros.
Como han señalado otros, la cuadratura solo puede ser aproximadamente 1.5X o 2X más rápida que la multiplicación regular entre números arbitrarios. ¿De dónde viene la ventaja computacional? Es simetría. Calculemos el cuadrado de 1011 e intentemos detectar un patrón que podamos explotar. u0:u3 representa los bits en el número desde el más significativo hasta el menos significativo.
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 considera que los elementos ui * ui para i=0, 1, ..., 4 forman la diagonal y los ignora, verá que los elementos ui * uj para i ≠ j se repiten dos veces.
Por lo tanto, todo lo que necesita hacer es calcular la suma del producto para los elementos por debajo de la diagonal y duplicarla, con un desplazamiento a la izquierda. Finalmente agregarías los elementos diagonales. Ahora puedes ver de dónde viene la velocidad de 2X. En la práctica, la aceleración es de aproximadamente 1.5X debido a las operaciones diagonales y adicionales.
Creo que estás completamente equivocado en tus declaraciones.
Multiplicar dos números binarios lleva n ^ 2 tiempo
Multiplicar dos números de 32 bits toma exactamente un ciclo de reloj. En un procesador de 64 bits, asumo que multiplicar dos números de 64 bits toma exactamente 1 ciclo de reloj. Ni siquiera me sorprendería que un procesador de 32 bits pueda multiplicar dos números de 64 bits en un ciclo de reloj.
yet squaring a number can be done more efficiently somehow.
Cuadrar un número es simplemente multiplicar el número consigo mismo, de modo que es solo una simple multiplicación. No hay operación "cuadrada" en la CPU.
Quizás estás confundiendo "cuadratura" con "multiplicar por una potencia de 2". La multiplicación por 2 se puede realizar desplazando todos los bits una posición a la "izquierda". Multiplicar por 4 es desplazar todos los bits dos posiciones a la "izquierda". Por 8, 3 posiciones. Pero este truco solo se aplica a una potencia de dos.
Creo que puede estar refiriéndose a la exponenciación por cuadratura . Esta técnica no se usa para multiplicar, sino para elevar a una potencia x ^ n, donde n puede ser grande. En lugar de multiplicar x veces sí mismo N veces, uno realiza una serie de operaciones de cuadratura y adición que pueden asignarse a la representación binaria de N. El número de operaciones de multiplicación (que son más caras que las adiciones para grandes números) se reduce de N a log (N) con respecto al algoritmo de exponenciación ingenua.
La cuadratura de un número de n dígitos puede ser más rápida que multiplicar dos números de n dígitos aleatorios. Google he encontrado este artículo . Se trata de aritmética de precisión arbitraria, pero puede ser relevante para lo que está pidiendo. En ella los autores dicen esto:
Al cuadrar un entero grande, es decir, X ^ 2 = (xn-1, xn-2, ..., x1, x0) ^ 2 muchos términos de producto cruzado de la forma xi * xj y xj * xi son equivalentes. Deben calcularse solo una vez y luego cambiarse a la izquierda para duplicarlos. Una operación de cuadratura de n dígitos se realiza utilizando solo (n ^ 2 + n) / 2 multiplicaciones de precisión simple.
La raíz cuadrada de 2 n es 2 n / 2 o 2 n >> 1 , por lo que si su número es una potencia de dos, todo es totalmente simple una vez que conozca la potencia. Multiplicar es aún más simple: 2 4 * 2 8 es 2 4 + 8 . No tiene sentido en estas declaraciones que has hecho.
Si asume una longitud fija para el tamaño de palabra de la máquina y si el número que se va a cuadrar está en la memoria, una operación de cuadratura requiere solo una carga de la memoria, por lo que podría ser más rápida.
Para enteros de longitud arbitraria, la multiplicación es típicamente O (N²) pero hay algoritmos que reducen esto para enteros grandes.
Si asume el enfoque simple de O (N²) para multiplicar a por b , entonces para cada bit en a tiene que desplazar b y agregarlo a un acumulador si ese bit es uno. Para cada bit en un necesita 3N turnos y adiciones.
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, puede 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 es O (N²).
Puede haber otra simetría mejor para explotar.
Si tiene un número binario A, puede (siempre, la prueba que se deja al lector entusiasta) expresarse como (2 ^ n + B), esto puede ser cuadrado como 2 ^ 2n + 2 ^ (n + 1) B + B ^ 2. Podemos repetir la expansión hasta que B sea igual a cero. No lo he mirado con demasiada atención, pero intuitivamente, parece que debería poder hacer que una función de cuadratura tome menos pasos algorítmicos que una multiplicación de propósito general.
Supongamos que desea expandir la multiplicación (a+b)×(c+d) . Se divide en cuatro multiplicaciones individuales: a×c + a×d + b×c + b×d .
Pero si desea expandirse (a+b)² , entonces solo necesita tres multiplicaciones (y una duplicación): a² + 2ab + b² .
(Note también que dos de las multiplicaciones son cuadrados).
Esperemos que esto solo empiece a dar una idea de algunas de las aceleraciones que son posibles cuando se realiza un cuadrado sobre una multiplicación regular.
a ^ 2 (a + b) * (a + b) + b ^ 2 por ejemplo. 66 ^ 2 = (66 + 6) (66-6) + 6 ^ 2 = 72 * 60 + 36 = 4356
para una ^ n solo usa la regla de poder
66 ^ 4 = 4356 ^ 2