Tema
Transformada rápida de Fourier
- Algoritmos
- Nivel avanzado
La transformada rápida de Fourier evalúa un polinomio en n raíces de la unidad en tiempo n log n, lo que permite multiplicar polinomios en ese mismo orden.
Nombre en inglés
Fast Fourier transform
Intuición
Multiplicar polinomios por sus coeficientes cuesta cuadrático, mientras que multiplicarlos por sus valores cuesta lineal, así que el truco consiste en cambiar de representación, multiplicar barato y volver. Las raíces de la unidad hacen que ese cambio se pueda partir en dos mitades, la de los índices pares y la de los impares, porque sus cuadrados vuelven a ser raíces de la unidad de la mitad de orden.
Fórmula
T(n) = 2 T(n/2) + O(n) = O(n log n) ; evaluar, multiplicar punto a punto, interpolar con la transformada inversa
Ejemplo resuelto
Para multiplicar el polinomio 1 más x por sí mismo se evalúa en las cuatro raíces cuartas de la unidad, se multiplican los cuatro valores y se interpola. El resultado es 1 más 2 x más x^2, que también se obtiene a mano. La ventaja aparece con grados grandes: Con 1024 coeficientes, el método directo hace del orden de un millón de productos y la transformada unas 10 000 operaciones.
Errores frecuentes
- Olvidar rellenar con ceros hasta una potencia de dos que cubra el grado del producto: El producto de dos polinomios de grado n tiene grado 2 n, de manera que hay que reservar sitio de sobra.
- Confundir la transformada con su inversa: La inversa cambia el signo del exponente y divide entre n, y omitir ese factor escala mal el resultado.
- Ignorar el error de coma flotante: Con coeficientes enteros grandes conviene redondear al final o trabajar con aritmética modular.
Ejercicio
Se multiplican dos polinomios de grado 100 con la transformada rápida de Fourier. ¿Cuál es el menor tamaño potencia de dos que hay que usar?
Ver la solución
El producto tiene grado 200 y por tanto 201 coeficientes. La menor potencia de dos que alcanza 201 es 256.
Respuesta: 256