Die schnelle Fourier-Transformation

Klick auf Gauß, 3 Perioden zu je 4. Diese zwölf Zahlen stammen aus Gauß' Manuskript: die Deklination der Nordkante jenes Himmelsstreifens, in dem der Asteroid Pallas wandern kann, alle 30° der Rektaszension in Bogenminuten, abgeschrieben aus von Zachs Zeitschrift. Er suchte nach der trigonometrischen Reihe durch diese Punkte. Statt einer Summe aus zwölf Termen nahm er jeden dritten Wert (0°, 90°, 180°, 270°; dann 30°, 120°, …; dann 60°, …), passte jede Vierergruppe für sich an und kombinierte die drei kurzen Anpassungen. Die gestrichelten Kurven zeigen diese Anpassungen, und sie stimmen nicht überein. Vier Punkte können die schnelleren Schwankungen nicht erfassen. Jede Gruppe liefert also ein anderes Ergebnis, weshalb er überhaupt erst nach der Kombination suchte. Die Tabelle unter den Ergebnissen zeigt seine nachgerechnete Kalkulation. Die erste Periode liefert 779,5, −415,0, −726,0 und 43,5, exakt die Zahlen im Manuskript. Die kombinierte Reihe entspricht der direkten Reihe mit zwölf Termen. Er rechnete es noch auf einem zweiten Weg, mit vier Perioden zu je drei, und erhielt dieselbe Reihe. Die Indexarithmetik ist genau jene, die Cooley und Tukey 1965 veröffentlichten, wie Heideman, Johnson und Burrus 1984 zeigten. Was das Manuskript auslässt, ist genauso wichtig. Es berechnet nie die eingesparte Arbeit. Wo Gauß sagt, die Aufteilung sei schneller, überlässt er den Beweis der Praxis: praxis tentantem docebit, wer es versucht, wird es sehen. Seine durchgerechneten Beispiele haben zwei Faktoren, 12 = 3 × 4 und 36 = 6 × 6. Artikel 27 merkt lediglich an, dass sich die Aufteilung auf mehr Faktoren erweitern lässt. Es wurde nicht zu seinen Lebzeiten veröffentlicht, sondern erschien 1866 auf Latein in seinen gesammelten Werken, und es trägt kein Datum. Der Herausgeber der Werke nennt es die Überarbeitung eines Entwurfs, der offenbar im Oktober 1805 begonnen wurde. Heideman, Johnson und Burrus ordnen es anhand einer Reihe von Hinweisen auf Oktober oder November 1805 ein. Darunter findet sich eine Exzentrizität von Juno, 0,254236, die das Manuskript verwendet und die im Mai 1805 in den Druck ging.

Klick auf 1.024 Punkte. Die direkte Summe multipliziert jeden Wert mit jedem Drehfaktor: N² = 1.048.576 Multiplikationen. Die FFT durchläuft log₂N = 10 Stufen aus N/2 = 512 Schmetterlingen mit je einer Multiplikation: 5.120. Das sind 204,8-mal weniger, und da das Verhältnis 2N/log₂N beträgt, wächst es stetig weiter. Klick auf Eine Million Punkte: 1.099.511.627.776 Multiplikationen gegenüber 10.485.760, ein Verhältnis von 104.857,6. Verdopple N, und der Aufwand der direkten Summe vervierfacht sich; der der FFT steigt bei tausend Punkten um das 2,2-fache, und je weiter du gehst, desto näher rückt der Faktor an zwei. Bei 8 Punkten liegt die Ersparnis nur beim 5,3-fachen. Deshalb wirkt der Graph wie eine Menge Verkabelung für wenig Gewinn. Beide Zählungen schließen die Multiplikationen mit W⁰ = 1 ein, genauso wie Cooley und Tukeys eigenes N². Sie zählten Multiplikations-und-Additions-Paare und kamen auf weniger als 2N log₂N. So oder so wächst das Verhältnis wie N/log N. Kein Computer ändert eine dieser Zählungen oder ihr Verhältnis: Ein schnellerer Rechner ändert die Laufzeiten, und zwar nicht zwangsläufig beide um denselben Faktor. Die Schaltfläche unter den Tabellen misst für beide die Zeit in deinem Browser. Das gemessene Verhältnis steigt ebenfalls mit N, wenn auch nicht auf diese theoretischen Werte. Speicherzugriffe und Additionen kosten Zeit, und die Zählung lässt sie unberücksichtigt.

Die Genauigkeitstabelle führt beide Methoden so aus, dass jede Operation auf einfache Präzision, also etwa sieben signifikante Stellen, gerundet wird. Verglichen wird mit einem Ergebnis in doppelter Präzision. Bei 1.024 Punkten weicht die direkte Summe um 5,75×10⁻⁷ der Ergebnisgröße ab, die FFT um 1,23×10⁻⁷, also etwa 4,7-mal weniger. Der Schritt von 16 auf 1.024 Punkte, also 64-mal so viele, vergrößerte den Fehler der direkten Summe um das 7,3-fache und den der FFT um das 1,4-fache. Jede Ausgabe der direkten Summe ist eine laufende Summe von N gerundeten Produkten. Ihre Rundungsfehler summieren sich also über 1.024 Additionen auf. Jeder Ausgabewert der FFT durchläuft hingegen nur log₂N = 10 Schmetterlinge. Bei 16 Punkten tut sich nicht viel, und bei dieser Eingabe ist die FFT sogar geringfügig schlechter, 8,74×10⁻⁸ gegenüber 7,91×10⁻⁸. Beide Methoden beziehen jeden Drehfaktor auf demselben Weg, berechnet in doppelter Präzision und einmal gerundet. Die Tabelle vergleicht somit die beiden Algorithmen und nicht zwei verschiedene Arten, einen Sinus zu berechnen.