El problema fundamental que aborda el Fast Fourier Transform (FFT) es la eficiente descomposición de una señal en sus componentes de frecuencia. Históricamente, el cálculo directo de la Discrete Fourier Transform (DFT) requiere O(n^2) operaciones aritméticas para una señal de longitud n. La invención del algoritmo de Cooley-Tukey en 1965 redujo esta complejidad a O(n log n), transformando radicalmente el procesamiento de señales digitales y haciendo viables aplicaciones que antes eran imposibles. Esta mejora asintótica es un pilar de la computación moderna, desde el análisis de audio hasta las telecomunicaciones y el procesamiento de imágenes.

La reciente afirmación de OpenAI de un 'Faster Fourier Transform' con una complejidad O(n log log n) plantea la pregunta de si es posible superar los límites establecidos por algoritmos como Cooley-Tukey. Sin embargo, este 'avance' se inscribe en una tendencia preocupante dentro de la teoría de la computación donde la formalización se desvincula de la realidad práctica. El artículo argumenta que, si bien teóricamente 'más rápido', el algoritmo de OpenAI es un ejemplo de un 'algoritmo galáctico', cuya utilidad práctica es nula debido a constantes ocultas astronómicamente grandes y a un modelo de computación que no corresponde a ninguna máquina física existente.

Arquitectura del Sistema

El algoritmo estándar de Cooley-Tukey para el FFT se basa en una estrategia de 'divide y vencerás'. Descompone una DFT de tamaño n en dos DFTs de tamaño n/2 (una para los elementos pares y otra para los impares de la entrada), y luego combina los resultados. Este proceso recursivo se repite log2(n) veces. La 'mariposa' de Cooley-Tukey es la unidad básica de recombinación, que realiza operaciones aritméticas atómicas para combinar las salidas de las sub-DFTs. La eficiencia proviene de la reutilización de cálculos y la reducción de multiplicaciones redundantes, transformando la complejidad de O(n^2) a O(n log n).

El supuesto 'Faster Fourier Transform' de OpenAI, aunque no se detalla su construcción específica, se enmarca en la búsqueda de algoritmos que reduzcan aún más el factor log n. Sin embargo, su modelo de computación asume 'aritmética compleja exacta' y la capacidad de multiplicar números complejos de precisión arbitraria cuyas magnitudes crecen superpolinómicamente con n en una sola operación. Esto implica requisitos de memoria y capacidad de cómputo que son exponencialmente inviables en cualquier hardware real. La 'mejora' O(n log log n) es puramente teórica y se logra a expensas de constantes ocultas tan grandes (ej., 10^100) que el algoritmo solo sería 'más rápido' para tamaños de entrada n mayores que el número de átomos en el universo, haciendo que la venerable FFT de Cooley-Tukey sea 10^99 veces más rápida para cualquier n práctico.

Trade-offs

Ganancias
  • △ Reducción de la complejidad asintótica de O(n log n) a O(n log log n) (teórico)
Costes
  • ▲▲ Constantes ocultas 'galácticas' que invalidan la mejora en cualquier escala práctica
  • ▲▲ Modelo de computación irrealista (aritmética de precisión arbitraria, memoria infinita)
  • ▲▲ Inestabilidad numérica y requisitos de memoria exponencial para números complejos de gran magnitud

Fundamentos Teóricos

La búsqueda de límites inferiores para la complejidad computacional de la Fourier Transform tiene una rica historia académica. Jacques Morgenstern demostró en 1973 que no se podía obtener una Fourier Transform más rápida que O(n log n) si se requería que los coeficientes complejos utilizados en el cálculo tuvieran una magnitud acotada. Esto estableció un límite práctico importante. Más tarde, Nir Ailon demostró que no se podía computar un FFT más rápido que O(n log n) sin introducir inestabilidades numéricas severas.

El trabajo de OpenAI, al ignorar estas restricciones de magnitud y precisión, se sitúa en una rama de la teoría de la computación que, aunque matemáticamente válida bajo sus propias premisas, se desvincula de las limitaciones físicas de los ordenadores. Este fenómeno de 'algoritmos galácticos' fue acuñado por Richard Lipton y Ken Regan para describir algoritmos que, aunque asintóticamente superiores, tienen constantes tan grandes que nunca serán prácticos. La 'mejora' de OpenAI es un ejemplo clásico de cómo la formalización excesiva y la abstracción del modelo de computación pueden llevar a resultados teóricos que no tienen relevancia para la ingeniería de sistemas reales.