Desenhando para Entender

A DFT (Transformada Discreta de Fourier) é relativamente simples de entender, mas é um algoritmo de complexidade o(n²). A FFT (Transformada Rápida de Fourier) tem complexidade o(nlogn), mas é mais complicada, naturalmente.

Para ajudar minha compreensão, resolvi desenhar os valores para enxergar as zonas comuns que ajudam o FFT a acelerar as contas.

Com ajuda do GD, excrevi um programa em Perl para gerar uma imagem com os valores das funções-base para diferentes resoluções (potências de dois).

A imagem abaixo vai de 2⁰ a 2¹⁰. Cada valor tem 100 linhas de altura e 2ⁿ divisões. Isto é, a imagem começa com 1 valor, depois 2, depois 4, etc. Deixei linhas pretas para demarcar os valores (cada um ocupa um retângulo de altura 100 e largua 1024/2ⁿ.

O valor de cada célula é e^-i2pik/N. O componente vermelho é abs(re)*255, ou seja, a parte inteira. O componente verde é a parte imaginária e o azul é zero.

Já dá para enxergar por onde otimizar o DFT.

Se adiciono um componente azul para valores negativos da parte real, terminho com isto:

Se faço o mesmo para a parte imaginária, tenho isto:

Já que não tenho 4 componentes de cor, vario a intensidade do azul conforme as partes real e imaginária são postivas ou negativas.

Juntando essas ideias, dá para imaginar como atacar o problema.