El mejor algoritmo de la historia

Cuando entré a la universidad, en el curso de Cálculo I me tocó estudiar las series y la transformada de Fourier. Como yo venía de estudiar técnico electrónico esa fue la primera vez que una cosa matemática me dejó maravillado, porque había trabajado armando un transmisor de FM (Radio Inacap) y conocía el asunto de las onda estacionarias, que es una de las cosas más maravillosas de la naturaleza.

¿Cual era la maravilla? Que cualquier onda -cualquier función matemática en realidad, pero yo pensaba en ondas- podía ser representada por una suma infinita de senos y cosenos con amplitudes decrecientes, como aparece explicado en este excelente video.

Por ejemplo una onda cuadrada como esta

Se puede obtener sumando senos y cosenos, por ejemplo en este caso a una onda seno sumemos otra del triple de su frecuencia

Al hacer la suma, obtenemos esto 

¡Que se empieza a parecer a una onda cuadrada! Si a la segunda onda le bajamos su amplitud obtenemos algo así 

¡Mucho mejor! ¿o no? y si agregamos muchos términos en múltiplos de frecuencia tenemos ago así como esto 

Que no es perfecta pero se parece, y mientras más senos agrgamos de amplitud menor y menos, más nos acercamos a la onda cuadrada. Si se fijan en los picos que aparecen en las esquinas de la onda cuadrada se corresponden al fenómeno físico de los transientes, que vemos al prender y apagar un interruptor por ejemplo. Y la onda cuadrada es solo un ejemplo simple, se puede hacer con casi cualquier onda por ejemplo una diente de sierra como se muestra aquí 

Lo importante es que prácticamente cualquier onda de sonido, electromagnética o de lo que sea que encontremos en la naturaleza, no importa si no tiene una frecuencia fija o si su amplitud es lo más estrafalaria que se nos ocurra, siempre estará compuesta por una suma de muchos senos y cosenos de diferentes amplitudes (es el número que lleva adelante el seno en el ejemplo: 0, 1/3 para la onda cuadrada 1/, 1/3 para la diente de sierra) y de múltiplos de frecuencia (2x, 3x... etc).

Por ejemplo esta onda 

Que corresponde a una música grabada en MP3 y contiene millones de frecuencias diferentes, también se puede descomponer como una suma de senos y cosenos, si la tenemos descompuesta podemos sacarle partes que tenga sin tocar las demás, así es -por ejemplo- como se elimina el cantante y se deja solo el acompañamiento en una pista de sonido, de la misma manera podríamos eliminar selectivamente los ruidos, algún instrumento, etc. etc sin alterar el resto de la música. 

Algo que parece imposible pero es perfectamente posible, incluso matemáticamente simple, en el primer curso de cálculo se enseñan las series y la Transformada de Fourier, que es el método que permite tomar una onda compuesta y descomponerla en una serie de senos y cosenos. Para que les digo el poder que se tuvo cuando se empezó a aplicar esto en el computador.

La primera vez que vi esto me golpeó la cabeza porque empecé a relacionar cientos de cosas prácticas que parecían inexplicable pero las series de Fourier las mostraban claras como el vodka: 

-Por qué la nota Do de un piano suena diferente a la de un violin o a la de un cantante, pese a ser la misma nota (tienen diferentes armónicos por las distintas cajas de resonancia)

-Por qué funciona el superheterodino en los receptores de radio y se pueden "batir" frecuencias

-Cómo se puede transmitir cualquier sonido "modulando" una onda portadora de radio

En fin, son cientos de fenómenos que se abren al entendimiento, especialmente de un electrónico. Las series de Fourier están en el corazón de la naturaleza y muestran que no existen realmente las "ondas raras" porque todas son una combinación de ondas sinusoidales puras, de distintas frecuencias y amplitudes.

Como decía, la Transformada de Fourier es una herramienta matemática muy simple, al alcance de cualquier alumno de primer año de matemáticas en la U que tenga nociones del cálculo integral. El problema es que antes que existieran los computadores era imposible soñar siquiera con descomponer una señal compleja en la suma de sus componentes, mucho menos en tiempo real por la cantidad y velocidad de cálculos simples que se necesitan.

Unas pocas veces en mi vida he tenido grandes golpes de intuición, lástima que nunca me han servido para nada práctico, Este fue uno de esos golpes, los computadores recién estaban empezando y comprendí en seguida -intuitivamente- que ese era un asunto fundamental, el problema estrella para resolverlo computacionalmente.

Tanto así que en la primera oportunidad que tuve para usar un computador, en 1979, partí corriendo a la perforadora de tarjetas para escribir un programa que calculara computacionalmente la transformada de Fourier siguiendo el método analítico en lugar del numérico, que era el que se enseñaba entonces.

Así, el primer programa que escribí fue para determinar los coeficientes de Fourier de una señal compleja usando el método analítico. Mi enfoque estaba equivocado, claro, porque el cálculo usando el método analítico requería un numero de operaciones que crecía en forma exponencial, esto lo hacía inútil en la práctica.

En 1966, 13 años antes, Cooley del Centro de Investigación de IBM y Turkey de la Universidad de Princeton habían publicado la idea del algoritmo de la Transformada Rápida de Fourier, "rápida" porque bajaba la cantidad de cálculos desde N cuadrado a NlognN, es decir de una cantidad exponencial a una logarítmica que es muchísimo menor. 

Usa las posibilidades combinatorias e iterativas de las matrices y está muy bien descrito en este artículo de Wikipedia, no es nada extremadamente complejo o abstracto

El método era típicamente numérico, iterativo y para colmo sencillo de implementar en un algoritmo, las tenía todas y así fue como la Transformada Rápida de Fourier (FFT) se convirtió en el algoritmo computacional más importante y con más aplicaciones jamás inventado.

Yo no tenía el conocimiento de las herramientas matemáticas, pero si tuve lo más importante: la comprensión del problema y la intuición de lo impactante que sería solucionarlo. Ni siquiera los que inventaron al FFT se dieron cuenta, durante mucho tiempo, de la importancia que tenía su invento, yo la vi desde el primer momento, cosa que hoy me enorgullece, inútilmente claro.

Hoy la FFT se usa prácticamente en todo: análisis y control de señales, reconocimiento de imágenes, inteligencia artificial, comunicaciones satelitales y GPS, multiplicación de números grandes, multiplicación de polinomios, representación de enteros como polinomios, cálculo aproximado de frecuencias en señales analógicas, espectro de una señal analógica, aplicaciones en mecánica cuántica, en fin, la lista es interminable.

La FFT es hoy la herramienta computacional más poderosa y con más aplicaciones que existe, el mejor algoritmo de la historia y yo todavía tengo una de las tarjetas perforadas de cuando intenté programarla en un vetusto computador IBM 1130, con las patas y el buche

P,D. Bah, ahora que veo bien la tarjeta me doy cuenta que es de otro programa en Fortran, mucho más penca, pero "la imagen es para referencia" jaja

P.D.2 Si miran este video de El Traductor de Ingeniería podran apreciar como se explican las series y la transformada en la universidad, sin ningún contexto y con énfasis a la parte mecánica de la matemática, usadas por un profesor medio ególatra que trata de lucirse "miren que soy inteligente", Esa forma de enseñar las cosas -en mi modo de ver- es una completa desgracia, le puede matar la vocación a cualquiera.