Быстрое преобразование Фурье (FFT): умножение многочленов и больших чисел за O(n log n)

FFT и NTT простыми словами: зачем переходить к значениям в точках, корни из единицы, итеративная реализация на Python, проблемы точности и NTT по модулю 998244353.

13 мин чтенияалгоритмы · математика · python

Коротко

ЧтоЗначение
ЗадачаПеремножить два многочлена (или два больших числа) степени nn
НаивноO(n2)O(n^2) — каждый коэффициент на каждый
FFT / NTTO(nlog⁡n)O(n \log n)
Главная идеяМногочлен степени <n< n однозначно задаётся значениями в nn точках, а в значениях умножение делается поэлементно
ТрюкТочки — комплексные корни из единицы, тогда значения во всех точках считаются рекурсией «разделяй и властвуй»
FFTЧисла с плавающей точкой: быстро, но возможны ошибки округления
NTTТо же самое, но в арифметике по модулю 998244353998244353: точно, без погрешностей

Задача: свёртка

Возьмём два многочлена:

A(x)=a0+a1x+⋯+an−1xn−1,B(x)=b0+b1x+⋯+bm−1xm−1A(x) = a_0 + a_1 x + \dots + a_{n-1} x^{n-1}, \quad B(x) = b_0 + b_1 x + \dots + b_{m-1} x^{m-1}

Коэффициенты их произведения C(x)=A(x)⋅B(x)C(x) = A(x) \cdot B(x):

ck=∑i+j=kai⋅bjc_k = \sum_{i + j = k} a_i \cdot b_j

Такая операция над массивами называется свёрткой. Она встречается чаще, чем кажется:

  • Умножение больших чисел. Число 123 — это многочлен 3+2x+1x23 + 2x + 1x^2 при x=10x = 10. Перемножили многочлены, раскидали переносы — получили произведение.
  • Подсчёт сумм пар. «Сколькими способами можно получить сумму kk, взяв по одному элементу из двух множеств?» — свёртка массивов частот.
  • Сопоставление строк с шаблонами и масками, где обычный 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]

Это O(n⋅m)O(n \cdot m). Для массивов длиной 10510^5 — 101010^{10} операций, слишком медленно. FFT решает ту же задачу за O(nlog⁡n)O(n \log n).

Идея: коэффициенты против значений

Многочлен можно хранить двумя способами.

  1. Коэффициенты: [a0,a1,…,an−1][a_0, a_1, \dots, a_{n-1}].
  2. Значения в точках: [A(x0),A(x1),…,A(xn−1)][A(x_0), A(x_1), \dots, A(x_{n-1})] для каких-то nn различных точек. Через nn точек проходит ровно один многочлен степени меньше nn — так же, как через две точки проходит ровно одна прямая.

Во втором представлении умножение тривиально: C(xi)=A(xi)⋅B(xi)C(x_i) = A(x_i) \cdot B(x_i), всего O(n)O(n) операций. Нужно только взять достаточно точек — у CC степень n+m−2n + m - 2, значит точек нужно хотя бы n+m−1n + m - 1.

Отсюда план:

  1. Дополнить оба массива нулями до длины N≥n+m−1N \ge n + m - 1 (удобно, чтобы NN было степенью двойки).
  2. Посчитать значения AA и BB в NN точках (прямое преобразование).
  3. Перемножить значения поэлементно.
  4. Восстановить коэффициенты CC по значениям (обратное преобразование).

Если точки выбрать как попало, шаги 2 и 4 стоят O(N2)O(N^2), и выигрыша нет. Весь фокус FFT — в правильном выборе точек.

Корни из единицы

Возьмём в качестве точек комплексные корни NN-й степени из единицы:

ωNk=e2πik/N=cos⁡2πkN+isin⁡2πkN,k=0,1,…,N−1\omega_N^k = e^{2\pi i k / N} = \cos\frac{2\pi k}{N} + i \sin\frac{2\pi k}{N}, \quad k = 0, 1, \dots, N-1

Геометрически это NN точек, равномерно расставленных по единичной окружности. У них два свойства, на которых держится весь алгоритм:

  • Возведение в квадрат уменьшает их число вдвое: (ωNk)2=ωN/2k(\omega_N^k)^2 = \omega_{N/2}^k. Квадраты NN корней — это ровно N/2N/2 корней степени N/2N/2.
  • Антиподы: ωNk+N/2=−ωNk\omega_N^{k + N/2} = -\omega_N^k. Вторая половина корней — это первая половина со знаком минус.

Разделяй и властвуй

Разобьём коэффициенты AA на чётные и нечётные:

A(x)=A0(x2)+x⋅A1(x2)A(x) = A_0(x^2) + x \cdot A_1(x^2)

где A0(y)=a0+a2y+a4y2+…A_0(y) = a_0 + a_2 y + a_4 y^2 + \dots и A1(y)=a1+a3y+a5y2+…A_1(y) = a_1 + a_3 y + a_5 y^2 + \dots — многочлены вдвое меньшей длины.

Подставим x=ωNkx = \omega_N^k. Благодаря первому свойству x2=ωN/2kx^2 = \omega_{N/2}^k, то есть A0A_0 и A1A_1 нужно вычислить всего в N/2N/2 точках — это та же задача половинного размера. Благодаря второму свойству одна пара значений даёт сразу два ответа:

A(ωNk)=A0(ωN/2k)+ωNk⋅A1(ωN/2k)A(\omega_N^k) = A_0(\omega_{N/2}^k) + \omega_N^k \cdot A_1(\omega_{N/2}^k)

A(ωNk+N/2)=A0(ωN/2k)−ωNk⋅A1(ωN/2k)A(\omega_N^{k + N/2}) = A_0(\omega_{N/2}^k) - \omega_N^k \cdot A_1(\omega_{N/2}^k)

Эта пара формул называется «бабочкой» (butterfly). Рекуррентность T(N)=2T(N/2)+O(N)T(N) = 2T(N/2) + O(N) даёт O(Nlog⁡N)O(N \log N) — как у сортировки слиянием.

Прямолинейная рекурсивная версия:

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, только с сопряжёнными корнями ωN−k\omega_N^{-k} и делением результата на NN:

aj=1N∑k=0N−1yk⋅ωN−jka_j = \frac{1}{N} \sum_{k=0}^{N-1} y_k \cdot \omega_N^{-jk}

Доказательство сводится к тому, что сумма ∑kωNk⋅t\sum_k \omega_N^{k \cdot t} равна NN при t≡0(modN)t \equiv 0 \pmod N и нулю иначе (сумма точек, равномерно расставленных по окружности, — ноль). Для практики достаточно запомнить: меняем знак угла и делим на NN.

Итеративная реализация

Рекурсивная версия наглядна, но создаёт кучу временных списков. На практике пишут итеративную версию, которая работает на месте. Она опирается на наблюдение: если раскрыть рекурсию до конца, элементы окажутся в порядке бит-реверса индексов. Для N=8N = 8:

ИндексДвоичная записьРеверсНовая позиция
00000000
10011004
20100102
30111106
41000011
51011015
61100113
71111117

То есть сначала переставляем элементы, а потом идём снизу вверх: склеиваем блоки длины 2, затем 4, 8 и так далее до NN — точно как в итеративной сортировке слиянием.

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. Мнимая часть — шум, вещественную округляем до целого.

Разбор на примере

Умножим A=1+2x+3x2A = 1 + 2x + 3x^2 на B=4+5xB = 4 + 5x. Нужно 3+2−1=43 + 2 - 1 = 4 коэффициента, N=4N = 4, корни: 1,−i,−1,i1, -i, -1, i (прямое преобразование с минусом).

Точка xxA(x)A(x)B(x)B(x)C(x)=A⋅BC(x) = A \cdot B
1166995454
−i-i−2−2i-2 - 2i4−5i4 - 5i−18+2i-18 + 2i
−1-122−1-1−2-2
ii−2+2i-2 + 2i4+5i4 + 5i−18−2i-18 - 2i

Обратное преобразование по столбцу C(x)C(x) возвращает [4,13,22,15][4, 13, 22, 15], то есть C=4+13x+22x2+15x3C = 4 + 13x + 22x^2 + 15x^3. Проверка: (1+2x+3x2)(4+5x)=4+5x+8x+10x2+12x2+15x3(1 + 2x + 3x^2)(4 + 5x) = 4 + 5x + 8x + 10x^2 + 12x^2 + 15x^3 — сходится.

Умножение больших чисел

Число раскладываем по цифрам, младшие — первыми, перемножаем как многочлены и разносим переносы:

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, только переносов много и они бывают больше единицы. Удаление ведущих нулей нужно, когда один из множителей равен нулю.

Можно хранить в элементе не одну цифру, а несколько (основание 10310^3 или 10410^4): массивы станут в 3–4 раза короче. Но тут вступает в силу главная проблема FFT.

Точность: где FFT ломается

Числа типа double хранят около 15–16 значащих десятичных цифр. Коэффициент свёртки может достигать N⋅V2N \cdot V^2, где VV — максимальный элемент. Если результат и накопленная ошибка округления сравнимы, round вернёт не то число — и никакого исключения вы не увидите, просто неправильный ответ.

Я замерил максимальную ошибку на случайных массивах длиной 2152^{15} (свёртка длины 2162^{16}), сравнивая с точным результатом:

Макс. элемент VVКорни через w *= w_lenКорни через cos/sin заранее
10310^38⋅10−38 \cdot 10^{-3}, ответ верный4⋅10−64 \cdot 10^{-6}, ответ верный
10410^40.80.8, тысячи ошибок4⋅10−44 \cdot 10^{-4}, ответ верный
10510^58282, почти всё неверно0.050.05, ответ верный, но запас мал

Выводы:

  • Способ вычисления корней важнее, чем кажется. Популярная запись «w = 1, на каждом шаге w *= w_len» накапливает ошибку умножением: на длинных блоках она растёт линейно. Корни, посчитанные напрямую через cos/sin (как в коде выше), на два-три порядка точнее.
  • Держите элементы маленькими. Для умножения длинных чисел безопасно основание 1010 или 100100; 10310^3–10410^4 — только с точными корнями и проверкой на ваших размерах.
  • Если нужен ответ по модулю или коэффициенты огромные — не мучайтесь с 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 без погрешностей

Что на самом деле нужно алгоритму от ω\omega? Только две вещи: ωN=1\omega^N = 1 (а меньшие степени не равны единице) и то, что для половины длины годится ω2\omega^2. Комплексные числа здесь не обязательны — подойдёт любая арифметика, где такой элемент существует.

В модульной арифметике по простому модулю pp корень степени NN из единицы существует, когда NN делит p−1p - 1. Поэтому берут простые вида c⋅2k+1c \cdot 2^k + 1. Самое популярное:

p=998244353=119⋅223+1p = 998244353 = 119 \cdot 2^{23} + 1

У p−1p - 1 множитель 2232^{23}, значит можно делать преобразования длиной до 223≈8.42^{23} \approx 8.4 млн. Число 33 — первообразный корень по этому модулю, и корень степени NN из единицы равен 3(p−1)/N mod p3^{(p-1)/N} \bmod p. Обратный корень и 1/N1/N берутся через малую теорему Ферма — быстрым возведением в степень 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)
ТочностьОшибки округления, зависят от NN и VVАбсолютно точно
РезультатНастоящие целые (если влезли в точность)Остатки по модулю
Произвольный модуль, например 109+710^9+7Только с трюками разбиенияТри NTT по разным модулям + КТО
Скорость в C++СравнимаСравнима, без double
Когда братьНебольшие значения, нужен точный ответ без модуляОтвет по модулю 998244353998244353, комбинаторика

Если нужны точные коэффициенты, которые больше модуля, делают NTT по двум-трём разным простым (998244353998244353, 167772161167772161, 469762049469762049 — у всех p−1p-1 делится на большую степень двойки) и собирают ответ китайской теоремой об остатках.

Сложность

  • Время: O(Nlog⁡N)O(N \log N), где NN — ближайшая степень двойки, не меньшая n+m−1n + m - 1. Три преобразования плюс поэлементное умножение.
  • Память: O(N)O(N).
  • Константа заметная: на массивах в несколько десятков элементов наивные O(nm)O(nm) работают быстрее. В библиотеках обычно переключаются на наивное умножение при малых размерах.

Типичные ошибки

  1. Длина меньше n+m−1n + m - 1. Преобразование считает циклическую свёртку: старшие коэффициенты «заворачиваются» и складываются с младшими. Нули в хвосте обязательны.
  2. Длина не степень двойки. Описанный алгоритм делит массив пополам на каждом уровне.
  3. Забыли поделить на NN в обратном преобразовании или поделили в прямом.
  4. int(x.real) вместо round(x.real). 14.999999 превратится в 14.
  5. Накопление ошибки в корнях (w *= w_len для комплексных) на больших размерах — см. таблицу выше.
  6. NTT с «неподходящим» модулем. Для 109+710^9 + 7 напрямую NTT не работает: p−1=2⋅500000003p - 1 = 2 \cdot 500000003, корней из единицы большой степени двойки нет.
  7. Переполнение в NTT на C++/Java. Произведение двух остатков до 10910^9 не помещается в 32-битный int — умножайте в long long/long.

Где встречается на собеседованиях

На обычном собеседовании в продуктовую компанию реализовать FFT с нуля попросят вряд ли — это тема олимпиадного программирования. Но она полезна в трёх ситуациях:

  • Вопрос «как перемножить два числа длиной в миллион цифр?» Ожидаемый ответ: школьное умножение — O(n2)O(n^2), Карацуба — O(n1.58)O(n^{1.58}), FFT — O(nlog⁡n)O(n \log n). Достаточно объяснить идею со значениями в точках и проблемы точности.
  • Задачи вида «сколько пар дают сумму kk для всех kk сразу» при больших диапазонах значений: свёртка частот вместо двойного цикла. Это развитие идеи Two Sum на все суммы одновременно.
  • Олимпиадные и алгоритмические секции (Яндекс, спортивное программирование): NTT по модулю 998244353998244353 — стандартный кирпичик для задач на производящие функции и комбинаторику, о которой есть отдельная статья про комбинаторику для программистов.

Главное, что стоит вынести: свёртка — это умножение многочленов, умножение многочленов дёшево в значениях, а корни из единицы позволяют перейти к значениям и обратно за O(nlog⁡n)O(n \log n).

Потренироваться в спокойной обстановке

Все задачи