Фурье и длинка (6 мая 2016)

1. FFT для умножения многочленов
1. Интерполяция, экстраполяция
2. Схема для быстрого умножения: экстраполяция, перемножение, интерполяция
3. Экстраполяция и интерполяция за O(n²) (не думаем здесь про переполнения)
4. Поле комплексных корней из единицы степени n=2^k. w = e^2πi/n = complex(cos(2πi/n), sin(2πi/n))
5. Прямое Фурье (рекурсивная процедура)
6. Обратное Фурье через прямое. Сперва формулируем результат, затем доказательство.

1. Улучшения FFT
1. Точность вычислений.
2. Код обратного: прямое a → f; reverse(f + 1, f + n); f /= n;
3. Ускорение: свой класс complex. 10-20% ускорения.
4. Два вещественных в одном
5. Нерекурсивная реализация (разворот битовой записи)
6. [skipped] Что делать, если коэффициенты не помещаются в память?
7. [skipped] Предподсчёт корней. Как быстро и точно посчитать?
2. [skipped] Длинная арфиметика
1. [skipped] Многочлены ↔ длинные целые неотрицательные числа
2. [skipped] Длинные чисел → длинные вещественные числа, числа со знаком
3. [skipped] Хранение длинных чисел: vector<int>; int num[N];
4. [skipped] Сложение, вычитание, сравнение, умножение и деление на короткое.
5. [skipped] Алгоритмы для умножения многочлены/чисел: квадрат, Карацуба, Фурье.
6. [skipped] Деление и умножение многочленов за O(nm).
7. [skipped] Двоичная арифметика: деление и gcd чисел за O(nm)
8. [skipped] Деление чисел за O(nm).