Gauss FFT

 История открытия **быстрого преобразования Фурье (БПФ / FFT)** Карлом Фридрихом Гауссом — это один из самых поразительных сюжетов в истории науки.

Гаусс разработал этот алгоритм **осенью 1805 года** — за **два года до того**, как Жозеф Фурье представил свою первую работу о тригонометрических рядах (1807 г.), и за **160 лет до статьи Джеймса Кули и Джона Тьюки (1965 г.)**, обессмертившей БПФ в эпоху ЭВМ.

Ниже описано, где именно в трудах Гаусса это содержится, для чего ему это понадобилось и как математически устроен его алгоритм.

---

### 1. Где это написано? (Рукопись 1805 года)

Работа называется:
> **«Theoria interpolationis methodo nova tractata»** (*«Теория интерполяции, изложенная новым методом»*).

* **Время написания:** Октябрь–ноябрь 1805 года.
* **Публикация:** При жизни Гаусс ее не опубликовал (считая лишь удобным рабочим инструментом). Рукопись была найдена в его архиве после смерти и напечатана в **1866 году** в **III томе Собрания сочинений Гаусса (*Carl Friedrich Gauss, Werke*, Band 3, S. 265–327)**, в разделах 27–30.

---

### 2. Зачем это понадобилось? (Астрономический вызов Паллады)

В 1801 году Гаусс прославился на всю Европу, рассчитав по трем наблюдениям орбиту первого открытого астероида — **Цереры**.

В 1802 году астроном Генрих Ольберс открыл второй астероид — **Палладу**. В отличие от Цереры, Паллада имела огромный наклон орбиты к плоскости эклиптики (\(34^\circ\)) и высокий эксцентриситет. Гравитационные возмущения от Юпитера были колоссальными.

Чтобы рассчитать траекторию Паллады, Гауссу требовалось:
1. Взять \(N\) точек наблюдения по времени (\(N = 12\), \(N = 36\) и т.д.);
2. Найти коэффициенты тригонометрического интерполяционного многочлена (дискретного ряда Фурье):
   \[
   c_j = \frac{1}{N} \sum_{k=0}^{N-1} f_k \, e^{-2\pi i j k / N}, \quad j = 0, 1, \dots, N-1.
   \]

**Вычислительный тупик:**
Прямое вычисление требует \(N^2\) комплексных умножений и сложений. Для \(N = 36\) это \(1296\) операций на каждый шаг, а для трехмерной задачи возмущений — десятки тысяч умножений вручную пером на бумаге. Гаусс искал способ кардинально сократить рутинный счет.

---

### 3. Как устроен алгоритм Гаусса? (Рождение идеи «разделяй и властвуй»)

В параграфах 27–28 своей рукописи 1805 года Гаусс замечает, что если число узлов \(N\) составное:
\[
N = N_1 \cdot N_2 \quad (\text{например, } N = 2m),
\]
то всю сумму можно расщепить на две независимые подсуммы вдвое меньшего размера.

#### Схема алгоритма Гаусса (Radix-2 / алгоритм с прореживанием по времени):
Обозначим \(\omega = e^{-2\pi i / N}\). Разделим исходный набор данных \(\{f_k\}_{k=0}^{N-1}\) на **четные** (\(k = 2l\)) и **нечетные** (\(k = 2l + 1\)) узлы:
\[
c_j = \sum_{l=0}^{\frac{N}{2}-1} f_{2l} \, \omega^{j(2l)} + \sum_{l=0}^{\frac{N}{2}-1} f_{2l+1} \, \omega^{j(2l+1)}.
\]

Вынося за скобки фазовый множитель:
\[
c_j = \sum_{l=0}^{\frac{N}{2}-1} f_{2l} \left(\omega^2\right)^{j l} + \omega^j \sum_{l=0}^{\frac{N}{2}-1} f_{2l+1} \left(\omega^2\right)^{j l}.
\]

Заметим, что:
1. \(\omega^2 = e^{-2\pi i / (N/2)}\) — это корень степени \(N/2\);
2. Первая сумма \(A_j\) — это **дискретное преобразование Фурье длины \(N/2\)** для четных точек;
3. Вторая сумма \(B_j\) — это **дискретное преобразование Фурье длины \(N/2\)** для нечетных точек;
4. Коэффициент \(\omega^j\) — это знаменитый **«поворотный множитель» (twiddle factor)**.

Гаусс получает базовые уравнения бабочки:
\[
c_j = A_j + \omega^j B_j,
\]
\[
c_{j + N/2} = A_j - \omega^j B_j.
\]

> Вместо \(N^2\) операций вычисление свелось к двум задачам размера \((N/2)^2\) плюс \(N\) сложений:
> \[
> 2 \left(\frac{N}{2}\right)^2 + N = \frac{N^2}{2} + N.
> \]
> Повторяя процедуру рекурсивно для \(N = 2^k\), сложность падает с \(O(N^2)\) до \(O(N \log N)\).

---

### 4. Что конкретно написал Гаусс?

Гаусс не просто выписал формулы — в параграфе 28 он дал строгую оценку вычислительной сложности своего метода и составил практические алгоритмические таблицы.

Гаусс пишет (на латыни):
> *«Трудность вычислений значительно уменьшается, если число наблюдений \(N\) разлагается на множители. Если \(N = a \cdot b\), то вместо \(a^2 b^2\) операций требуется лишь \(a b (a + b)\) операций...»*

В рукописи приведены полностью рассчитанные примеры:
* Для \(N = 12\) Гаусс раскладывает задачу как \(12 = 3 \times 4\) и \(12 = 2 \times 6\), уменьшая число операций с \(144\) до \(12 \times (3 + 4) = 84\);
* Для \(N = 36\) он строит двумерную факторизацию \(36 = 4 \times 9\), получая сокращение счета почти в четыре раза.

---

### 5. Как мир потерял и заново открыл БПФ

1. **1866 год:** Рукопись опубликована на латыни в томе 3 Собрания сочинений Гаусса, но математики XIX века восприняли ее просто как частную астрономическую вычислительную таблицу.
2. **1965 год:** Джеймс Кули (*IBM*) и Джон Тьюки (*Принстон*) независимо переоткрывают алгоритм для цифровой обработки сигналов и анализа данных ядерных испытаний. Статья производит революцию в компьютерных науках.
3. **1984 год:** Историки науки и инженеры **Майкл Хайдеман, Дон Джонсон и Сидни Бёррус** (*M. T. Heideman, D. H. Johnson, C. S. Burrus, IEEE ASSP Magazine, 1984*) подробно исследуют архив Гаусса и доказывают: **алгоритм Кули — Тьюки полностью и до мельчайших деталей содержится в рукописи Гаусса 1805 года.**

### Итог
Быстрое преобразование Фурье родилось у Гаусса в **1805 году** в трактате *Theoria interpolationis methodo nova tractata* как инструмент тригонометрической интерполяции по узлам \(q^k = e^{2\pi i k / N}\) ради спасения астрономов от бесконечных ручных расчетов траектории астероида Паллада.