Быстрое преобразование Фурье (FFT): умножение многочленов и больших чисел за O(n log n)
FFT и NTT простыми словами: зачем переходить к значениям в точках, корни из единицы, итеративная реализация на Python, проблемы точности и NTT по модулю 998244353.
Коротко
| Что | Значение |
|---|---|
| Задача | Перемножить два многочлена (или два больших числа) степени |
| Наивно | — каждый коэффициент на каждый |
| FFT / NTT | |
| Главная идея | Многочлен степени однозначно задаётся значениями в точках, а в значениях умножение делается поэлементно |
| Трюк | Точки — комплексные корни из единицы, тогда значения во всех точках считаются рекурсией «разделяй и властвуй» |
| FFT | Числа с плавающей точкой: быстро, но возможны ошибки округления |
| NTT | То же самое, но в арифметике по модулю : точно, без погрешностей |
Задача: свёртка
Возьмём два многочлена:
Коэффициенты их произведения :
Такая операция над массивами называется свёрткой. Она встречается чаще, чем кажется:
- Умножение больших чисел. Число
123— это многочлен при . Перемножили многочлены, раскидали переносы — получили произведение. - Подсчёт сумм пар. «Сколькими способами можно получить сумму , взяв по одному элементу из двух множеств?» — свёртка массивов частот.
- Сопоставление строк с шаблонами и масками, где обычный KMP не справляется (например, с символами-джокерами).
- Комбинаторика: перемножение производящих функций.
Наивная свёртка — два вложенных цикла:
def multiply_naive(a, b): res = [0] * (len(a) + len(b) - 1) for i, x in enumerate(a): for j, y in enumerate(b): res[i + j] += x * y return res print(multiply_naive([1, 2, 3], [4, 5])) # [4, 13, 22, 15]
Это . Для массивов длиной — операций, слишком медленно. FFT решает ту же задачу за .
Идея: коэффициенты против значений
Многочлен можно хранить двумя способами.
- Коэффициенты: .
- Значения в точках: для каких-то различных точек. Через точек проходит ровно один многочлен степени меньше — так же, как через две точки проходит ровно одна прямая.
Во втором представлении умножение тривиально: , всего операций. Нужно только взять достаточно точек — у степень , значит точек нужно хотя бы .
Отсюда план:
- Дополнить оба массива нулями до длины (удобно, чтобы было степенью двойки).
- Посчитать значения и в точках (прямое преобразование).
- Перемножить значения поэлементно.
- Восстановить коэффициенты по значениям (обратное преобразование).
Если точки выбрать как попало, шаги 2 и 4 стоят , и выигрыша нет. Весь фокус FFT — в правильном выборе точек.
Корни из единицы
Возьмём в качестве точек комплексные корни -й степени из единицы:
Геометрически это точек, равномерно расставленных по единичной окружности. У них два свойства, на которых держится весь алгоритм:
- Возведение в квадрат уменьшает их число вдвое: . Квадраты корней — это ровно корней степени .
- Антиподы: . Вторая половина корней — это первая половина со знаком минус.
Разделяй и властвуй
Разобьём коэффициенты на чётные и нечётные:
где и — многочлены вдвое меньшей длины.
Подставим . Благодаря первому свойству , то есть и нужно вычислить всего в точках — это та же задача половинного размера. Благодаря второму свойству одна пара значений даёт сразу два ответа:
Эта пара формул называется «бабочкой» (butterfly). Рекуррентность даёт — как у сортировки слиянием.
Прямолинейная рекурсивная версия:
import cmath def fft_recursive(a): n = len(a) if n == 1: return a[:] even = fft_recursive(a[0::2]) odd = fft_recursive(a[1::2]) res = [0] * n for k in range(n // 2): w = cmath.exp(-2j * cmath.pi * k / n) res[k] = even[k] + w * odd[k] res[k + n // 2] = even[k] - w * odd[k] return res
Знак в показателе экспоненты — договорённость: в большинстве реализаций прямое преобразование берут с минусом, обратное — с плюсом. Для умножения важно лишь, чтобы они были противоположными.
Обратное преобразование
Как вернуться от значений к коэффициентам? Оказывается, обратное преобразование — это то же самое FFT, только с сопряжёнными корнями и делением результата на :
Доказательство сводится к тому, что сумма равна при и нулю иначе (сумма точек, равномерно расставленных по окружности, — ноль). Для практики достаточно запомнить: меняем знак угла и делим на .
Итеративная реализация
Рекурсивная версия наглядна, но создаёт кучу временных списков. На практике пишут итеративную версию, которая работает на месте. Она опирается на наблюдение: если раскрыть рекурсию до конца, элементы окажутся в порядке бит-реверса индексов. Для :
| Индекс | Двоичная запись | Реверс | Новая позиция |
|---|---|---|---|
| 0 | 000 | 000 | 0 |
| 1 | 001 | 100 | 4 |
| 2 | 010 | 010 | 2 |
| 3 | 011 | 110 | 6 |
| 4 | 100 | 001 | 1 |
| 5 | 101 | 101 | 5 |
| 6 | 110 | 011 | 3 |
| 7 | 111 | 111 | 7 |
То есть сначала переставляем элементы, а потом идём снизу вверх: склеиваем блоки длины 2, затем 4, 8 и так далее до — точно как в итеративной сортировке слиянием.
import math def fft(a, invert=False): n = len(a) # 1. Перестановка бит-реверса j = 0 for i in range(1, n): bit = n >> 1 while j & bit: j ^= bit bit >>= 1 j |= bit if i < j: a[i], a[j] = a[j], a[i] # 2. Корни считаем заранее, каждый напрямую через cos/sin sign = 1 if invert else -1 roots = [ complex(math.cos(2 * math.pi * k / n), sign * math.sin(2 * math.pi * k / n)) for k in range(n // 2) ] # 3. Бабочки: блоки длины 2, 4, 8, ..., n length = 2 while length <= n: half = length // 2 step = n // length # корень степени length = roots[k * step] for start in range(0, n, length): for k in range(half): u = a[start + k] v = a[start + k + half] * roots[k * step] a[start + k] = u + v a[start + k + half] = u - v length <<= 1 if invert: for i in range(n): a[i] /= n def multiply(a, b): need = len(a) + len(b) - 1 n = 1 while n < need: n <<= 1 fa = [complex(x) for x in a] + [0j] * (n - len(a)) fb = [complex(x) for x in b] + [0j] * (n - len(b)) fft(fa) fft(fb) for i in range(n): fa[i] *= fb[i] fft(fa, invert=True) return [round(x.real) for x in fa[:need]] print(multiply([1, 2, 3], [4, 5])) # [4, 13, 22, 15]
Цикл перестановки — классический приём: j хранит бит-реверс i и обновляется «прибавлением единицы со старшего бита». Каждый обмен делается один раз благодаря условию i < j.
Обратите внимание на round(x.real): после обратного FFT вместо 15 получится что-то вроде 15.000000000000002 - 3e-16j. Мнимая часть — шум, вещественную округляем до целого.
Разбор на примере
Умножим на . Нужно коэффициента, , корни: (прямое преобразование с минусом).
| Точка | |||
|---|---|---|---|
Обратное преобразование по столбцу возвращает , то есть . Проверка: — сходится.
Умножение больших чисел
Число раскладываем по цифрам, младшие — первыми, перемножаем как многочлены и разносим переносы:
def multiply_big(x: str, y: str) -> str: a = [int(c) for c in reversed(x)] b = [int(c) for c in reversed(y)] res = multiply(a, b) carry = 0 for i in range(len(res)): res[i] += carry carry, res[i] = divmod(res[i], 10) while carry: carry, digit = divmod(carry, 10) res.append(digit) while len(res) > 1 and res[-1] == 0: res.pop() return ''.join(map(str, reversed(res))) print(multiply_big('12345678901234567890', '98765432109876543210')) # 1219326311370217952237463801111263526900 print(multiply_big('0', '123')) # 0
Перенос разрядов — та же логика, что в задаче Plus One, только переносов много и они бывают больше единицы. Удаление ведущих нулей нужно, когда один из множителей равен нулю.
Можно хранить в элементе не одну цифру, а несколько (основание или ): массивы станут в 3–4 раза короче. Но тут вступает в силу главная проблема FFT.
Точность: где FFT ломается
Числа типа double хранят около 15–16 значащих десятичных цифр. Коэффициент свёртки может достигать , где — максимальный элемент. Если результат и накопленная ошибка округления сравнимы, round вернёт не то число — и никакого исключения вы не увидите, просто неправильный ответ.
Я замерил максимальную ошибку на случайных массивах длиной (свёртка длины ), сравнивая с точным результатом:
| Макс. элемент | Корни через w *= w_len | Корни через cos/sin заранее |
|---|---|---|
| , ответ верный | , ответ верный | |
| , тысячи ошибок | , ответ верный | |
| , почти всё неверно | , ответ верный, но запас мал |
Выводы:
- Способ вычисления корней важнее, чем кажется. Популярная запись «
w = 1, на каждом шагеw *= w_len» накапливает ошибку умножением: на длинных блоках она растёт линейно. Корни, посчитанные напрямую черезcos/sin(как в коде выше), на два-три порядка точнее. - Держите элементы маленькими. Для умножения длинных чисел безопасно основание или ; – — только с точными корнями и проверкой на ваших размерах.
- Если нужен ответ по модулю или коэффициенты огромные — не мучайтесь с double, берите NTT. Есть и промежуточные трюки (разбить каждое число на две половины по 15 бит и сделать несколько FFT), но NTT проще и надёжнее.
На Python, кстати, ручной FFT нужен в основном для понимания: встроенное умножение int уже использует алгоритм Карацубы, а для свёртки массивов есть numpy:
import numpy as np def multiply_np(a, b): need = len(a) + len(b) - 1 n = 1 << (need - 1).bit_length() fa = np.fft.rfft(a, n) fb = np.fft.rfft(b, n) return np.rint(np.fft.irfft(fa * fb, n)[:need]).astype(np.int64).tolist() print(multiply_np([1, 2, 3], [4, 5])) # [4, 13, 22, 15]
rfft — версия для вещественного входа, примерно вдвое быстрее полной. Ограничения точности у неё те же.
NTT: FFT без погрешностей
Что на самом деле нужно алгоритму от ? Только две вещи: (а меньшие степени не равны единице) и то, что для половины длины годится . Комплексные числа здесь не обязательны — подойдёт любая арифметика, где такой элемент существует.
В модульной арифметике по простому модулю корень степени из единицы существует, когда делит . Поэтому берут простые вида . Самое популярное:
У множитель , значит можно делать преобразования длиной до млн. Число — первообразный корень по этому модулю, и корень степени из единицы равен . Обратный корень и берутся через малую теорему Ферма — быстрым возведением в степень pow(x, p - 2, p).
Это и есть NTT (Number Theoretic Transform). Код почти дословно повторяет FFT:
MOD = 998244353 # 119 * 2**23 + 1 G = 3 # первообразный корень по модулю MOD def ntt(a, invert=False): n = len(a) j = 0 for i in range(1, n): bit = n >> 1 while j & bit: j ^= bit bit >>= 1 j |= bit if i < j: a[i], a[j] = a[j], a[i] length = 2 while length <= n: w_len = pow(G, (MOD - 1) // length, MOD) if invert: w_len = pow(w_len, MOD - 2, MOD) half = length // 2 for start in range(0, n, length): w = 1 for k in range(start, start + half): u = a[k] v = a[k + half] * w % MOD a[k] = (u + v) % MOD a[k + half] = (u - v) % MOD w = w * w_len % MOD length <<= 1 if invert: n_inv = pow(n, MOD - 2, MOD) for i in range(n): a[i] = a[i] * n_inv % MOD def multiply_mod(a, b): need = len(a) + len(b) - 1 n = 1 while n < need: n <<= 1 fa = [x % MOD for x in a] + [0] * (n - len(a)) fb = [x % MOD for x in b] + [0] * (n - len(b)) ntt(fa) ntt(fb) for i in range(n): fa[i] = fa[i] * fb[i] % MOD ntt(fa, invert=True) return fa[:need] print(multiply_mod([1, 2, 3], [4, 5])) # [4, 13, 22, 15]
Здесь w *= w_len уже безопасно: арифметика по модулю точная, ошибки не копятся. Результат — коэффициенты свёртки по модулю 998244353. Если в задаче ответ просят именно по этому модулю (а авторы олимпиадных задач выбирают его как раз ради NTT), это ровно то, что нужно.
FFT или NTT
| FFT (complex) | NTT (mod 998244353) | |
|---|---|---|
| Точность | Ошибки округления, зависят от и | Абсолютно точно |
| Результат | Настоящие целые (если влезли в точность) | Остатки по модулю |
| Произвольный модуль, например | Только с трюками разбиения | Три NTT по разным модулям + КТО |
| Скорость в C++ | Сравнима | Сравнима, без double |
| Когда брать | Небольшие значения, нужен точный ответ без модуля | Ответ по модулю , комбинаторика |
Если нужны точные коэффициенты, которые больше модуля, делают NTT по двум-трём разным простым (, , — у всех делится на большую степень двойки) и собирают ответ китайской теоремой об остатках.
Сложность
- Время: , где — ближайшая степень двойки, не меньшая . Три преобразования плюс поэлементное умножение.
- Память: .
- Константа заметная: на массивах в несколько десятков элементов наивные работают быстрее. В библиотеках обычно переключаются на наивное умножение при малых размерах.
Типичные ошибки
- Длина меньше . Преобразование считает циклическую свёртку: старшие коэффициенты «заворачиваются» и складываются с младшими. Нули в хвосте обязательны.
- Длина не степень двойки. Описанный алгоритм делит массив пополам на каждом уровне.
- Забыли поделить на в обратном преобразовании или поделили в прямом.
int(x.real)вместоround(x.real).14.999999превратится в14.- Накопление ошибки в корнях (
w *= w_lenдля комплексных) на больших размерах — см. таблицу выше. - NTT с «неподходящим» модулем. Для напрямую NTT не работает: , корней из единицы большой степени двойки нет.
- Переполнение в NTT на C++/Java. Произведение двух остатков до не помещается в 32-битный
int— умножайте вlong long/long.
Где встречается на собеседованиях
На обычном собеседовании в продуктовую компанию реализовать FFT с нуля попросят вряд ли — это тема олимпиадного программирования. Но она полезна в трёх ситуациях:
- Вопрос «как перемножить два числа длиной в миллион цифр?» Ожидаемый ответ: школьное умножение — , Карацуба — , FFT — . Достаточно объяснить идею со значениями в точках и проблемы точности.
- Задачи вида «сколько пар дают сумму для всех сразу» при больших диапазонах значений: свёртка частот вместо двойного цикла. Это развитие идеи Two Sum на все суммы одновременно.
- Олимпиадные и алгоритмические секции (Яндекс, спортивное программирование): NTT по модулю — стандартный кирпичик для задач на производящие функции и комбинаторику, о которой есть отдельная статья про комбинаторику для программистов.
Главное, что стоит вынести: свёртка — это умножение многочленов, умножение многочленов дёшево в значениях, а корни из единицы позволяют перейти к значениям и обратно за .