A Transformada Rápida de Fourier

Pressione Gauss, 3 períodos de 4. Estes doze números provêm do manuscrito de Gauss: a declinação da margem norte da faixa de céu onde o asteroide Pallas pode deambular, a cada 30° de ascensão reta, em minutos de arco, copiados da revista de von Zach. Ele procurava a série trigonométrica que passasse por eles. Em vez de uma única soma de doze termos, pegou em cada terceiro valor (0°, 90°, 180°, 270°; depois 30°, 120°, …; depois 60°, …), ajustou cada conjunto de quatro de forma independente e combinou os três ajustes curtos. As curvas a tracejado são esses ajustes, e divergem: quatro pontos não conseguem detetar as oscilações mais rápidas, logo cada conjunto obtém uma resposta diferente, e foi isso que o levou a procurar a combinação. A tabela sob os resultados é o seu cálculo refeito: o primeiro período dá 779,5, −415,0, −726,0 e 43,5, os números do manuscrito, e a série combinada é a série direta de doze termos. Fez isto de uma segunda forma, quatro períodos de três, e obteve a mesma série. A aritmética de índices é aquela que Cooley e Tukey publicaram em 1965, tal como Heideman, Johnson e Burrus mostraram em 1984. O que o manuscrito omite é igualmente importante. Nunca conta o trabalho poupado: onde Gauss diz que a divisão é mais rápida, deixa a prova para a prática, praxis tentantem docebit, quem tentar verá. Os seus exemplos resolvidos têm dois fatores, 12 = 3 × 4 e 36 = 6 × 6, e o artigo 27 diz apenas que a divisão se estende a mais. O texto não foi publicado em vida, surgindo em latim nas suas obras coligidas em 1866, e não tem data: o editor das obras chama-lhe uma revisão de um rascunho aparentemente iniciado em outubro de 1805, e Heideman, Johnson e Burrus situam-no em outubro ou novembro de 1805 a partir de várias pistas. Uma delas é a excentricidade de Juno, 0,254236, que o manuscrito utiliza e que foi impressa em maio de 1805.

Pressione 1.024 pontos. A soma direta multiplica cada amostra por cada fator de rotação: N² = 1.048.576 multiplicações. A FFT executa log₂N = 10 etapas de N/2 = 512 borboletas com uma multiplicação cada: 5.120. Isso é 204,8 vezes menos, e a razão é 2N/log₂N, portanto continua a crescer. Pressione Um milhão de pontos: 1.099.511.627.776 multiplicações contra 10.485.760, uma razão de 104.857,6. Duplique N e o trabalho da soma direta aumenta quatro vezes; o da FFT aumenta 2,2 vezes aos mil pontos, e aproxima-se do dobro quanto mais avança. Com 8 pontos a poupança é de apenas 5,3 vezes, razão pela qual o diagrama parece ter muitas ligações para pouco ganho. Ambas as contagens incluem as multiplicações por W⁰ = 1, tal como o próprio N² de Cooley e Tukey faz. Eles contaram pares de multiplicar e somar e obtiveram menos do que 2N log₂N, e de qualquer forma a razão cresce como N/log N. Nenhum computador altera as contagens, nem a sua razão: um computador mais rápido muda os tempos, e não necessariamente ambos pelo mesmo fator. O botão sob as tabelas cronometra ambos no seu navegador. A razão medida também sobe com N, embora não até estes valores, porque o tráfego de memória e as adições custam tempo e a contagem ignora-os.

A tabela de exatidão executa ambos os métodos com cada operação arredondada para precisão simples, cerca de sete algarismos significativos, contra uma resposta de dupla precisão. Aos 1.024 pontos, a soma direta tem um desvio de 5,75×10⁻⁷ da magnitude da resposta e a FFT de 1,23×10⁻⁷, cerca de 4,7 vezes menos. Passar de 16 pontos para 1.024, 64 vezes mais, tornou o erro da soma direta 7,3 vezes maior e o da FFT 1,4 vezes. Cada saída da soma direta é um total corrente de N produtos arredondados, de modo que os seus erros de arredondamento acumulam-se ao longo de 1.024 adições. Cada saída da FFT passa apenas por log₂N = 10 borboletas. Aos 16 pontos quase não há diferença, e nesta entrada a FFT é até ligeiramente pior, 8,74×10⁻⁸ contra 7,91×10⁻⁸. Ambos os métodos obtêm cada fator de rotação da mesma forma, calculado em dupla precisão e arredondado uma vez, pelo que a tabela compara os dois algoritmos e não duas formas de obter um seno.