Multiplicación más rápida de polinomios univariantes

Question

Estaba leyendo cómo se puede reducir el número de multiplicaciones necesarias para multiplicar dos números complejos (sustituyendo esta reducción de multiplicaciones por un aumento del número de sumas y restas). Luego decía que un algoritmo similar se podía utilizar para multiplicar dos polinomios univariantes (es decir, se puede reducir el número de multiplicaciones necesarias para multiplicar dos polinomios univariantes).

¿Cómo se puede hacer esto?

Answer 1

Utilizando $FFT^{-1}(FFT(a*b) ) = FFT^{-1}(FFT(a)FFT(b))$ . Donde $*$ es la convolución, y $a,b$ son vectores de los coeficientes de los dos polinomios. Como la convolución se convierte en multiplicación en el dominio de Fourier de $O(n^2)$ se reducen a $O(n)$ . Sin embargo, transformar el vector de coeficientes de su polinomio en el dominio de Fourier no es gratuito, pero puede hacerse en $O(n\log n)$ tiempo utilizando la transformada rápida de Fourier. Por lo tanto, se necesita $O(n\log n)$ tiempo para multiplicar dos polinomios.

Edición: Para utilizar específicamente el método de Karatsuba que tienes en mente puedes "dividir" tu polinomio. Como un ejemplo: $$p(x) = a_0 + a_1x+a_2x^2+...+a_nx^n = $$ $$(a_0 + a_1x) + x^2(a_2 + a_3x) + ... + x^{n-1}(a_{n-1} + a_nx)$$ A continuación, realice el procedimiento de forma recursiva. También se puede hacer una división con polinomios de diferentes potencias. La mayoría de la gente utiliza el $FFT$ sin embargo.

Answer 2

La identidad $$(a+bi)(c+di) = ac + bdi^2 + ((a+b)(c+d)-ac-bd)i$$ funciona igual de bien con otros valores de $i$ . En particular, puede tomar $i=x^k$ para un valor adecuado de $k$ (aproximadamente la mitad del grado de los polinomios).