Метод четырёх русских и основы длинной арифметики

Доска 1 — НОП двоичных строк: блоки k×k и предподсчёт 2^{4k}

Доска 2 — представление длинного числа и выбор основания системы счисления

Наша основная тема сегодня — повтор: вам придётся вспомнить всякое из того, что вы уже узнали. Но сперва давайте разберём маленький кусочек того, что нужно было сделать и до чего мы ещё не успели дойти, — метод четырёх русских. В прошлый раз это было в умножении матриц, а сегодня потренируемся ускорять НОП. Пусть у нас есть две двоичные строки, например 0101001010 и 1010010100; наибольшую общую подпоследовательность мы умеем искать динамикой за время n2n^2. Динамика выглядит как fi,jf_{i,j} — наибольшая общая подпоследовательность префикса длины ii и префикса длины jj. А сейчас я напишу ту же самую динамику, но получу время n2(log⁡n)2\dfrac{n^2}{(\log n)^2}.

Кто уже умеет так делать? Нужно смотреть на подматрицы размера log⁡n\log n, разрезать таблицу на такие подматрицы. Нужно уметь решать какие-то маленькие подзадачки — вот то направление, по которому мы пойдём; и нам повезло, что строчки состоят из ноликов и единичек. Давайте попробуем эту квадратную табличку разбить на кусочки размера k×kk \times k — на такие клеточки. Что нам нужно, чтобы посчитать очередную клетку?

Чтобы посчитать вот эту клетку целиком, а она состоит из k2k^2 чисел, мне нужно знать значения динамики в начале строки, значения динамики в начале столбца и, видимо, ещё важно, какие символы выпали. У меня есть две строки: по одному направлению я отложу строку ss, по другому — строку tt. Значит, мне нужен кусок строки ss длины kk и кусок строки tt длины kk. Утверждение: всё это можно описать 4k4k битами, если клеточка размера k×kk \times k.

С двумя кусками строк всё понятно: тут kk бит, потому что kk ноликов и единичек, и тут тоже kk бит. А вот значения функции — это, вообще говоря, целые числа, это не биты. Как увидеть в них биты?

— Там не биты, там инты какие-то.

— Нет, там всё гораздо лучше устроено, потому что соседние клетки в динамике почти не отличаются. Соседние значения могут отличаться либо на 00, либо на 11: величина fi,j+1−fi,jf_{i,j+1} - f_{i,j} всегда принимает одно из двух значений, 00 или 11. Поэтому нам действительно хватает даже не kk бит, а чуть меньше: здесь нужно k−1k-1 бит и здесь k−1k-1 бит. А то число, которое стоит в самом начале, на самом деле не нужно, потому что оно сдвигает всё на константу. Если я храню разности соседних в строке и разности соседних в столбце, то от того, что я забуду эту константу, все числа просто одновременно уменьшатся на одну и ту же величину, а на то, как динамика пересчитывается дальше, эта константа не влияет: пересчёт будет точно таким же.

Итого, после того как я всё это нарисовал, я говорю, что могу сделать себе предподсчёт по всем 24k2^{4k} вариантам и для каждого сохранить результат. Что именно я хочу сохранить? Внутри клетки я считал динамику — долго и нудно, — но интересно только то, что окажется на выходе из клеточки, чтобы начать считать следующие клеточки. Причём здесь я сказал, что хочу работать с массивом разностей, а не с массивом ff: переходить туда-обратно очень глупо — хранить ff, в момент запуска динамики пересчитать разности, потом получить обратно ff, ещё раз посчитать разности и снова вернуться к разностям. Давайте просто везде таскать с собой разности соседних. Тогда динамика получила битовую маску разностей по строке, битовую маску разностей по столбцу и вернула две битовые маски — то есть подсчёт одной клеточки у меня теперь работает за O(1)O(1). И естественно, так мы сделаем «количество клеток» раз.

Моё решение сейчас работает за время 24k+n2k22^{4k} + \dfrac{n^2}{k^2}, где второе слагаемое — количество клеточек. Нужно ещё не забыть подобрать kk, но, видимо, логарифм, делённый на что-то, подойдёт, чтобы предподсчёт был порядка nn. Например, k=log⁡n/4k = \log n / 4 точно подойдёт.

— А можешь, пожалуйста, объяснить, откуда 4k4k? Почему предподсчёт за столько?

— Ой, не за 4k4k, я глупость написал: я четвёрку не туда поставил. У нас 4k4k бит, а значит, вариантов 24k2^{4k}. Стало лучше?

— Да.

Тогда и kk возьмём не log⁡n/4\log n / 4, а log⁡n/5\log n / 5 — точно с запасом. А то вдруг тут полезут ещё какие-нибудь логарифмы, про которые я забыл, и буду двоечник. Метод четырёх русских закрыли, переходим в мир длинной арифметики.

Длинную арифметику обычно никто из вас не пишет. Или вы писали, на плюсах? Писали. А что именно? Реально быстрое сложение, которое работает в системе счисления 2322^{32}. Давайте сперва поговорим вообще о том, как работают простые операции. Сегодня мы с вами научимся делить и умножать за nlog⁡nn \log n — всё научимся делать, — но сперва простые вещи: число надо считать, вывести, сложить, как-то хранить в памяти.

Как же работает длинная арифметика? Число обычно хранят в массиве. Число иногда растёт, становится всё больше и больше, и вектор растёт вместе с ним; чтобы числу было удобно расти, оно растёт в ту же сторону, что и вектор. Соответственно, младший разряд числа лежит в нулевой ячейке вектора, следующий — в первой, и так далее. Дальше нужно выбрать систему счисления: в каждой ячейке вектора содержатся цифры числа, то есть 0⩽a[i]<B0 \leqslant a[i] < B, где BB — основание системы счисления, которое я буду обозначать буквой BB.

Какую выбрать систему счисления? Если я, например, хочу хранить цифры в int32\mathtt{int32}, первая идея — выбрать 2322^{32}. У этого способа есть плюсы и минусы. Плюс: код будет работать максимально эффективно. Минус: с ним столкнулись ребята, которые писали на питоне. Python хранит числа в двоичной системе, а ввод и вывод у него десятичный, поэтому их нужно постоянно переводить — и кто-то умный этот перевод реализовал за квадрат. Итак: плюс — быстро, минус — надо переводить.

Какие ещё варианты, какую систему счисления выбрать? Какую степень десятки брать? Видимо, 10910^9 как раз влезает, но есть и вариант выбрать что-то поменьше. Когда вы говорите 10910^9, вы предполагаете, что если потом эти числа предстоит умножать, то величина 109⋅109=101810^9 \cdot 10^9 = 10^{18} не переполнится — она влезает в int64\mathtt{int64}, и мы сможем посчитать её в том же самом типе. Иногда выбирают систему счисления чуть-чуть меньше, чтобы не было проблем с переполнением: берут, например, 10410^4. А когда мы будем писать длинную арифметику на основе быстрого преобразования Фурье, добавится ещё одна причина брать степень десятки поменьше: чтобы погрешность, которая набегает в вещественных числах, не оказалась слишком большой.

Давайте чуть-чуть поговорим про 2322^{32} — один раз, а дальше везде буду считать, что система счисления — это просто степень десятки. Когда вы пишете на ассемблере — помните курс про ассемблер? — там есть замечательная операция сложения двух чисел. Когда вы складываете длинные числа, вы обычно складываете в столбик: сперва складываете первые цифры, может быть, произошёл перенос; если произошёл, его надо не забыть прибавить, когда складываете две следующие цифры. Так вот, в ассемблере есть операция «сложить два числа с учётом переноса от предыдущего сложения». Перенос там не нужно держать ни отдельным флагом, ни отдельной фичей — это базовая инструкция процессора, одна такая. Соответственно, сложение двух чисел в системе счисления 2322^{32} — это ровно один такт на разряд, причём даже без учёта параллелизма. Поэтому её действительно очень любят.

Ускорение тут не «чуть-чуть». Казалось бы, система счисления поменялась незначительно: была степень десятки, стала 2322^{32}, — а скорость работы изменилась в несколько раз за счёт того, что процессор под 2322^{32} всё уже оптимизировал: if’а никакого нет. А в системе счисления — степени десятки будет лишний if и ещё лишнее прибавление потом. Писать в 2322^{32} неудобно, потому что нужно постоянно переводить, так что мы с вами, простые люди, будем работать в системе счисления — степени десятки.

Итак, как писать простые операции? Сложение чисел — это один for, который прибавляет, а дальше нужно где-то делать перенос. Когда мы говорим про перенос, у нас всегда есть два варианта. Первый: попытаться запихнуть его в тот же цикл; тогда код, например, будет выглядеть так — если ячейка переполнилась, то из a[i] сразу вычесть B и увеличить следующий разряд.

// a += b
for (int i = 0; i < n; i++) {
    a[i] += b[i];
    if (a[i] >= B) { a[i] -= B; a[i + 1]++; }
}

Это у меня операция «плюс равно». Естественно, я могу сделать и операцию «плюс», просто создав копию aa. Вообще любая операция, которую я сейчас пишу, будет в форме «плюс равно», «минус равно», «умножить равно на короткое» — это те функции, которые работают за линейное время, просто потому что их так писать удобно: я одной функцией пишу как бы сразу две. Так вот, переносы можно делать в том же цикле, а можно делать в конце. С точки зрения производительности почти всегда оптимально делать их сразу, если есть такая возможность. С точки зрения удобства написания кода, чтобы не думать лишний раз, удобно разделять эти две части: один цикл for делает операцию, другой цикл for занимается переносом.

Например, когда-то давно мы с вами изучали алгоритм Карацубы. Если у вас есть фанаты Карацубы, то в первую задачку контеста, где вам предстоит умножить два числа, Карацуба как раз отлично заходит. Карацуба — это такой алгоритм, который учит вас делать переносы в конце. Если вы пытаетесь делать переносы по ходу кода Карацубы, она перестаёт работать быстро, возникают всякие мелкие проблемы. В Фурье у нас будет то же самое. Везде, где можно думать без переноса, я считаю, что переносы делаются в конце, и мы как-нибудь их потом сделаем.

Главное — не забыть подумать про максимальный размер числа в ячейке. Например, если я складываю числа, то максимальное значение, которое окажется записано в одной ячейке, — это 2⋅B2 \cdot B. А если я делал умножение без переноса, какое максимальное значение одного разряда будет?

— B2B^2.

— Неточный ответ. Очень сильно неточный ответ. B2B^2 — это результат произведения двух цифр, но у вас же в одном разряде стоит сумма нескольких произведений: в каждом столбике вы умножаете много раз. Давайте обычное умножение:

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        c[i + j] += a[i] * b[j];

В одной ячейке у вас складывается сразу nn таких произведений по B2B^2, поэтому в одной ячейке будет n⋅B2n \cdot B^2. Соответственно, если вы умножаете числа с помощью Карацубы, которая переносит всё в конец, вы должны позаботиться о том, чтобы эта величина влезала в ваш элементарный тип. И тут система счисления 10910^9 нам уже не подойдёт. Можно запариться и делать переносы по ходу Карацубы; если запариваться не хотим, учитываем ещё nn, и оказывается, что для обычной Карацубы, которую мы пытались написать, основание можно брать только 10610^6. Поясню ещё раз эту мысль про n⋅B2n \cdot B^2: неважно, как именно работала Карацуба, — в конце результат получается без переноса, и в конце там точно будет n⋅B2n \cdot B^2.

Я написал один for для сложения, но кое-что забыл: ++ для следующего разряда. Надо делать a[i+1]++, это правда, не надо это бросать. Следующая операция — вычитание. Чтобы не писать for на доске каждый раз с нуля, я как бы скопировал код в новое место и исправляю уже там: a[i] -= b[i], а перенос, если значение стало меньше нуля, нужно, наоборот, прибавлять.

// a -= b
for (int i = 0; i < n; i++) {
    a[i] -= b[i];
    if (a[i] < 0) { a[i] += B; a[i + 1]--; }
}

Давайте напишем ещё что-нибудь — умножение на короткое число, операцию «умножить на kk». Умножаем на kk и, если нужно, в конце переносим. Кстати, с вычитанием у меня тут была опечатка: условие должно быть именно «меньше нуля», а не «меньше BB»; вот тогда и нужно делать перенос. Теперь я умножил на kk каждую цифру, и если результат больше либо равен основанию, то нужно делать перенос. Этот if почти никогда не срабатывает, казалось бы, — тем не менее мой опыт говорит, что он позволяет выиграть несколько процентов, поэтому я его на всякий случай пишу. Перенос здесь уже приходится делать с использованием деления: значение a[i]a[i] надо будет взять по модулю, поэтому сперва я делаю перенос вперёд — a[i+1] += a[i] / B, — а потом a[i] %= B.

// a *= k
for (int i = 0; i < n; i++) {
    a[i] *= k;
    if (a[i] >= B) { a[i + 1] += a[i] / B; a[i] %= B; }
}

Если вы пишете на приличном языке программирования, у которого нормально работает оптимизатор, например на C++, то, естественно, деление и взятие по модулю превращаются в одну процессорную операцию — «поделить с остатком». На языке ассемблера деление и остаток делаются одной операцией сразу, вам об этом думать не надо, оптимизатор всё за вас сделает.

И давайте ещё какую-нибудь отвратительную операцию — деление на короткое. Кто сейчас может сходу сообразить, как делить на короткое число, скажем, на три?

— Бинпоиск.

— Бинпоиск по ответу — вообще хорошая тема применительно к делению: если вы умеете умножать, но не умеете делить, делаем бинпоиск по ответу, и на коротеньких числах это как-то работает. Это правда. К сожалению, если у нас число длины nn, то есть оно порядка 10n10^n, то логарифм этого числа, за который будет работать бинпоиск по ответу, — это примерно nn. То есть у бинпоиска появился квадрат: деление стоило бы O(n2)O(n^2).

Надо делать цикл в другом порядке. Вот здесь я старался делать переносы в конце, а деление на короткое — это первый раз, когда перенос не получится отделить от самой операции, придётся переносить по ходу. Будем действовать как при умножении, но делить. Перед тем как поделить a[i]a[i] на kk, мне нужно отдать то, что не поделилось, то есть остаток, в предыдущий разряд. Поэтому я пишу: к a[i-1] прибавить остаток, а остаток — это a[i] % k, причём при переносе в предыдущий разряд он умножается на основание системы счисления.

// a /= k
for (int i = n - 1; i >= 0; i--) {
    a[i - 1] += (a[i] % k) * B;
    a[i] /= k;
}

Элементарные операции, сравнение алгоритмов умножения и интерполяция

Доска 3 — времена умножения: школьное, Карацуба, БПФ; рекомендуемые основания

Простые операции на этом закончились. Отдельно иногда выделяют ещё две элементарные операции: битовый сдвиг на один вправо и битовый сдвиг на один влево. Сдвиг >>1\texttt{>>}1 — это деление на два, сдвиг <<1\texttt{<<}1 — умножение на два. Почему выделяют именно эти две операции? Потому что бинарная арифметика — это вот такой набор элементарных операций: +, −, /2, ∗2, <, >, =+,\ -,\ /2,\ *2,\ <,\ >,\ =. Через них можно выразить всё остальное, что нам желательно иметь.

Что такое «всё остальное»? Во-первых, через эти операции можно выразить умножение. Правда, работать оно будет за квадрат, зато у вас получится простой короткий код; впрочем, умножение вы и так обычно умеете написать за квадрат, так что это не очень интересно. Во-вторых, можно выразить деление. Кто писал деление длинных чисел, знает, что через бинарные операции получается заметно более простой код, — и это уже важно. Подробно мы его обсуждать не будем, кому интересно — есть в конспекте. В-третьих, можно получить даже длинный gcd: для наибольшего общего делителя длинных чисел можно писать специальное умножение и взятие по модулю, а можно сказать, что gcd в BigInteger тоже выражается через эти простые бинарные операции. Если мы выражаем всё через деление и умножение на два, то все три операции работают за n2n^2, где nn — битовая длина числа. Про элементарную длинную арифметику, видимо, всё.

— Можно вопрос? Почему при делении ты добавляешь остаток к разряду с номером на единицу меньше, а эти слагаемые взяты по модулю BB и умножены на BB?

— Потому что я в любой момент могу взять и сделать такой перенос, от этого смысл числа не поменяется. Число — это на самом деле сумма ∑iBi⋅a[i]\sum_i B^i \cdot a[i], а массив устроен соответственно. Поэтому в любой момент я могу сказать, что старший разряд целиком переехал в более младший. Когда я делил на короткое, почти вся часть поделилась нацело, а какая-то часть не поделилась; я взял ту часть, которая сейчас не поделилась, и сказал, что поделю её потом. Давайте пример: делю число 7878 на 33, старшие цифры в привычной манере пишу слева. Семёрку делю на три, получаю два, остаётся единица — она переезжает в следующий разряд, и теперь я делю 1818 на 33, получаю шесть. Итого 78:3=2678 : 3 = 26 — всё так же, как мы делали руками.

Теперь про быстрое умножение. До того как мы начнём делать БПФ, давайте поймём, что у нас уже есть. Есть многочлены и есть числа, и любой алгоритм, который мы знаем, работает и для многочленов, и для чисел, но есть нюанс. Если мы берём базовое умножение за квадрат, то для многочленов он работает ровно за произведение длин многочленов, ровно за столько операций. Если мы говорим про числа, мы ещё выбираем систему счисления: числа нам обычно дают, например, в десятичной системе, и длину мы, как у строк, тоже измеряем в десятичной системе. Поэтому, если n,mn, m — это длины чисел в десятичной записи, а систему счисления мы выберем 10k10^k (или вообще какая-то маленькая константа в kk-й степени: 2k,10k2^k, 10^k), то на самом деле всё работает в k2k^2 раз быстрее. Поэтому не забывайте выбирать систему счисления настолько большую, насколько можете.

Аналогично с Карацубой; для неё я уже не буду писать O(nm)O(nm), а напишу просто от nn. Напомню, за какую степень работает Карацуба?

— 1,61{,}6.

— В каждой группе должен быть человек, который помнит константы. Давайте освежим. Число π\pi?

— 3,143{,}14.

— Число ee?

— 2,7182{,}718.

— Отлично. Золотое сечение?

— 1,6181{,}618.

— Неплохо. Логарифм трёх по основанию два?

— 1,581{,}58.

Вот за столько Карацуба работает для многочленов — n1,58n^{1{,}58}, и за (n/k)1,58(n/k)^{1{,}58} для чисел с максимально возможной выбранной системой счисления. Сейчас мы научимся делать то же самое за время nlog⁡nn\log n, а для чисел — за (n/k)log⁡n(n/k)\log n. Получается такая таблица: квадратичное умножение — n⋅mn\cdot m для многочленов и n⋅m/k2n\cdot m/k^2 для чисел в базе 10k10^k; Карацуба — n1,58n^{1{,}58} и (n/k)1,58(n/k)^{1{,}58}; БПФ — nlog⁡nn\log n и (n/k)log⁡n(n/k)\log n. Это к чему? К тому, что, несмотря на то что преобразование Фурье мы будем изучать для многочленов, оптимизация «выбрать большую систему счисления» для Фурье тоже работает.

Для умножения за квадрат систему счисления можно брать хоть 10910^9 — большое kk. Для Карацубы, как мы только что обсудили, если мы пишем её удобным образом, лучше взять систему счисления поменьше, порядка 10610^6. Для Фурье, если мы используем стандартный тип — а естественно использовать стандартный тип, потому что всё, что вы делаете с типом double\texttt{double}, процессор делает быстро, — нам, к сожалению, понадобится система счисления примерно 10410^4, иначе накопится слишком большая погрешность.

Второе, о чём хочу сказать, — сравнение двух последних строчек таблицы. Карацуба сильно дольше, но на самом деле в Карацубе, если nn очень маленькое, мы дёргаем умножение за квадрат: правильно написанная Карацуба естественно содержит такую оптимизацию — если nn уже не больше 16 или 32, то квадрат будет работать не хуже, а скорее всего даже лучше. То же самое с Фурье и Карацубой: на не слишком длинных числах Карацуба выигрывает, потому что, во-первых, показатель степени не сильно больше единицы, а во-вторых, в Фурье будут операции с комплексными числами. То есть в одном случае nlog⁡nn\log n умножений комплексных чисел, а в другом — nlog⁡nn\log n умножений целых чисел со взятием по модулю. Какая из констант быстрее, нужно тестировать уже на конкретной архитектуре. Я когда-то считал, что примерно до n≈1000n \approx 1000 выгодно пускать Карацубу, но это должен быть результат эксперимента на конкретной архитектуре.

Теперь, собственно, пусть нам дали длинные числа и мы хотим умножать их очень быстро. Вообще Карацуба тоже неплохо справляется: если числа длины до 100 тысяч, то в правильной системе счисления Карацуба работает почти мгновенно. БПФ же позволит умножать за секунду числа длины порядка 3 000 000 — это пример, чтобы вы понимали порядок.

Перейдём к общей идее БПФ. Было ли у вас преобразование Фурье?

— Только формула.

— Хорошо. Тогда про интерполяцию. Что вы уже знаете про интерполяцию?

— Например, что интерполяционный многочлен существует и единственный.

— Да. Если у меня есть точки x1,x2,…,xnx_1, x_2, \dots, x_n и значения в этих точках y1,y2,…,yny_1, y_2, \dots, y_n, которые я хочу получить, то существует единственный многочлен PP такой, что deg⁡P<n\deg P < n, то есть у него ровно nn коэффициентов, и P(xi)=yiP(x_i) = y_i. Если бы степень была равна nn, коэффициентов было бы уже n+1n+1. Интерполяцию вы умеете делать с какого-то времени: есть формула Лагранжа, есть метод Ньютона. Вопрос в том, за сколько это работает, если мы попытаемся действительно провести вычисление. Есть небольшая разница между тем, когда вы пишете формулу от руки на бумажке, и тем, когда компьютер запускает алгоритм. Единственное, на чём нам нужно зафиксироваться: Лагранж или Ньютон — что вам ближе после курса математики? Мне тогда ближе Ньютон. Будем делать по Ньютону.

Метод Ньютона — это метод по индукции. Пусть по индукции мы уже решили задачу для первых n−1n-1 точек; давайте добавим последнюю точку. Для предыдущих значений у нас всё точно совпадает, и чтобы в них ничего не испортилось, я добавляю такую вещь: (x−x1)(x−x2)⋯(x−xn−1)(x - x_1)(x - x_2)\cdots(x - x_{n-1}). Я уверен, что значения в первых точках это не испортит. Умножить это нужно на что-то, чтобы подогнать значение в точке xnx_n. Многочлен по первым n−1n-1 точкам обозначим Pn−1P_{n-1}, а произведение из n−1n-1 скобочки обозначим Qn−1Q_{n-1}. Оба они имеют какие-то значения в точке xnx_n, и мы хотим, чтобы выполнялось линейное уравнение Pn−1(xn)+Qn−1(xn)⋅α=ynP_{n-1}(x_n) + Q_{n-1}(x_n)\cdot\alpha = y_n, где α\alpha — искомый коэффициент. Отсюда α=yn−Pn−1(xn)Qn−1(xn)\alpha = \dfrac{y_n - P_{n-1}(x_n)}{Q_{n-1}(x_n)}, и именно с таким коэффициентом α\alpha я домножаю скобку.

За сколько это всё работает? Очередной шаг — это, во-первых, умножение Qn−1Q_{n-1} на ещё одну скобку; умножение на такую короткую скобку работает за линейное время O(n)O(n). Ещё нужно посчитать значения в точке, а подстановка — это тоже линейное время. Посчитали значение, посчитали значение, умножили — это один шаг; шагов всего nn, итого n2n^2. За столько у вас сейчас работает интерполяция. Если бы вы всё делали по Лагранжу, получили бы тот же самый квадрат.

Теперь в чём суть быстрого преобразования Фурье? В совершенно определённых точках, красивых, мы сейчас сумеем проинтерполировать за время nlog⁡nn\log n. Общая схема преобразования Фурье такая. Мы просто хотим умножить два числа, а начинаем делать странные вещи: сперва мы считаем значения AA и значения BB в каких-то красивых точках. Эти точки давайте уже начнём обозначать ω0,ω1,…,ωN−1\omega_0, \omega_1, \dots, \omega_{N-1}. Зная значения многочленов AA и BB в точках ω\omega, мы можем узнать значения произведения в этих же точках. Как?

— Значения перемножаются.

— Верно. Получили здесь массив fAfA, здесь массив fBfB — это преобразования Фурье AA и BB — и за линейное время посчитали их поточечное произведение. Схема целиком:

fA = FFT(A)
fB = FFT(B)
for i: fAB[i] = fA[i] * fB[i]
AB = FFT^{-1}(fAB)

Я, видимо, вас обманул: интерполяция — это не первая стрелочка, первая стрелочка — это вычисление значений в точках, а вот последняя стрелочка — обратное преобразование, и она как раз интерполяция. Именно вычисление значений в точках называют прямым преобразованием Фурье, а обратную стрелочку — обратным преобразованием Фурье. Поскольку прямое и обратное преобразования Фурье — это один и тот же код, запущенный с разными параметрами, наша цель сейчас — научиться делать одно преобразование и понять, почему второе то же самое. Будем учиться вычислять значения в точках.

Какие точки, строго? Точки комплексные, равные корням из единицы: jj-я точка — это корень из единицы нужной нам степени. Напоминаю, как комплексные корни из единицы выглядят на картинке; здесь я нарисовал все корни из единицы степени восемь. Нам нужно число, которое в восьмой степени даёт единицу: длина этого числа должна быть ровно единицей, чтобы и длина в восьмой степени была единицей, а угол должен быть 2π/82\pi/8, умноженный на какую-то константу, и эта константа у меня меняется от 0 до 7. Корни из единицы обладают замечательным свойством: они образуют группу по умножению, циклическую и очень просто устроенную. Есть базовый корень, обозначим его ω1=e2πi/N\omega_1 = e^{2\pi i / N}, а любой другой корень ωj\omega_j — это просто ω1 j\omega_1^{\,j}. Я специально не использую букву ii для индексов, потому что сегодня она зарезервирована под мнимую единицу; потом вернётся в обиход.

Вот в таких точках мы и собираемся считать значения. БПФ — это алгоритм «разделяй и властвуй», мы делим пополам. Поделить пополам не получится, если взять NN не степенью двойки: на каком-то шаге нужно будет делить пополам нечётное число, и это вызовет неразрешимую проблему. Поэтому скажем, что длина каждого из многочленов AA и BB равна степени двойки. Я собираюсь их перемножить и получить многочлен произведения, а длина произведения — это сумма длин. Соответственно, обратному БПФ нужно, чтобы точки были те же самые, а NN было не меньше суммы длин. Поэтому я выбираю любую степень двойки 2k⩾len(A)+len(B)2^k \geqslant \mathrm{len}(A) + \mathrm{len}(B).

Что такое сумма длин? В математике любят слово «степень», но со степенью постоянно нужно делать плюс-минус единичку. У меня есть массив коэффициентов, у него есть длина, и длина многочлена — это len=deg⁡+1\mathrm{len} = \deg + 1. Вот из-за этих плюс-минус единичек я и не люблю работать со степенями — есть длина массива. Кстати, на доске у меня в этом месте опечатка: под вторым слагаемым написано deg⁡A+1\deg A + 1, а должно быть deg⁡B+1\deg B + 1. Все многочлены в C++ хранятся просто массивом.

И, собственно, как же мы это сделаем? Смотрите, фокус. Всё предыдущее было подготовкой, а теперь единственный фокус, в котором и заключается преобразование Фурье. Если я хочу посчитать значения многочлена P(x)P(x) в точках, я записываю его в следующем виде: P(x)=P0(x2)+x⋅P1(x2)P(x) = P_0(x^2) + x\cdot P_1(x^2). Здесь я просто сгруппировал все чётные степени — это P0(x2)P_0(x^2) — и все нечётные, вынеся из них xx, — это x⋅P1(x2)x\cdot P_1(x^2). Это я сделал за линейное время: разбил массив коэффициентов PP на два массива коэффициентов — чётные степени и нечётные степени.

А потом — два рекурсивных вызова. Чтобы посчитать значения многочлена PP в точках ω0,ω1,…,ωN−1\omega_0, \omega_1, \dots, \omega_{N-1}, мне нужно посчитать в этих точках значения многочленов P0P_0 и P1P_1. Если рекурсия вернула эти значения, я циклом for\texttt{for} пробегаюсь по точкам и в каждой говорю, что P(ωj)=P0(ω2j)+x⋅P1(ω2j)P(\omega_j) = P_0(\omega_{2j}) + x\cdot P_1(\omega_{2j}), где x=ωjx = \omega_j, — потому что (ωj)2=ω2j(\omega_j)^2 = \omega_{2j}, то есть квадрат jj-го корня — это ровно 2j2j-й корень. А дальше в чём фокус? Фокус в том, что от возведения в квадрат корней стало в два раза меньше: у меня было NN величин ωj\omega_j, а разных квадратов очень мало — N/2N/2, порядок падает N→N/2N \to N/2.

Давайте убедимся в этом на картинке. Возьмём корни четвёртой степени — их четыре: 1,i,−1,−i1, i, -1, -i. После того как я все корни возвёл в квадрат, они перешли в корни второй степени — логично, что квадраты корней четвёртой степени являются корнями второй степени, и осталось только 11 и −1-1. Действительно: 12=11^2 = 1, (−1)2=1(-1)^2 = 1, i2=−1i^2 = -1 и (−i)2=−1(-i)^2 = -1 тоже. Так что четыре корня четвёртой степени при возведении в квадрат дают всего два значения — {1,−1}\{1, -1\}.

Алгоритм преобразования Фурье на идейном уровне уже закончился. Дальше мы будем долго заниматься реализацией: сперва чтобы она была корректной, потом чтобы её оптимизировать. А идея закончилась здесь: распилили на два массива, сделали два рекурсивных вызова и, делая их, заметили, что теперь считаем значения только в N/2N/2 интересных точках, а не в NN. Вопросы какие-нибудь?

— А база в этой рекурсии какая?

— Давайте поговорим про базу. Кстати, я тут по индукции поддерживал замечательное свойство: количество точек ω0,…,ωN−1\omega_0, \dots, \omega_{N-1}, то есть NN точек, совпадает с длиной многочлена. Плохо, что коэффициенты я тоже назвал той же буквой — можно перепутать, поэтому скажу, что коэффициенты — это a0,…,aN−1a_0, \dots, a_{N-1}. Так вот, длина многочлена поделилась пополам и количество точек поделилось пополам, соответственно, в базе рекурсии у меня есть многочлен длины 1, который я хочу посчитать в одной точке. Многочлен длины 1 — это только свободный член, так что я возвращаю его коэффициент:

if (N == 1) return a_0;

return a0\texttt{return } a_0 — это значение многочлена в точке ω0\omega_0, которая равна единице. Да и вообще в любой точке многочлен длины 1 даст значение a0a_0.

Корни из единицы, предподсчёт и рекурсивное БПФ

Доска 4 — корни из единицы: ω^{N/2+j} = −ω^j и (ω_j)² = ω_{2j}

Давайте сделаем рекурсивную реализацию. Нам ещё нужно уметь быстро предпосчитать корни всех степеней двойки. Сейчас я буду писать код целиком, а начинается он с предподсчёта — поэтому сперва общие слова про предподсчёт корней. Есть два способа: правильный и неправильный.

Неправильный способ — вычислять корни по цепочке умножений: когда я в цикле считаю значение P(ωj)P(\omega_j), получать ωj\omega_j из предыдущего корня. Или делать то же самое на этапе предподсчёта. Соблазн понятен: все наши корни имеют вид ωj=ω1 j\omega_j = \omega_1^{\,j}, то есть следующий корень — это предыдущий, умноженный на главный корень ω1\omega_1. Так делать, к сожалению, нельзя, если вы не хотите словить проблемы с погрешностью. Причём они будут прямо хардкорные: даже для системы счисления с основанием 100100 вы, скорее всего, уже получите неверный ответ, может быть, и для 1010 на очень длинных числах. Слишком много умножений — и всё схлопывается по погрешности в неправильный ответ.

Как правильно? Правильно вспомнить, что экспонента считается через косинус и синус, и честно завести массив всех корней — это самый простой способ. В массиве корней лежат комплексные числа, а комплексное число — это пара, поэтому я пишу фигурную скобку:

Root[j] = { cos(2 * PI / N * j), sin(2 * PI / N * j) };

Обратите внимание: внутри косинуса и синуса мнимой единицы нет — она относилась к записи e2πi/Ne^{2\pi i/N}. Я предлагаю посчитать сейчас один массив корней, используя начальное значение NN. Само nn при рекурсии будет убывать, делиться пополам, а предподсчитанный массив я построю один раз — для самого мелкого корня. Извините, я забыл домножить на jj внутри косинуса и синуса; теперь формула верная.

Если я посчитал длинный массив корней, а мне нужны корни порядка N/2N/2, то я буду ходить по этому массиву шагом 22: нулевая ячейка, вторая, четвёртая и так далее. Если мне нужны корни порядка N/8N/8, я буду ходить шагом 88. То есть если сейчас длина массива nn маленькая, например n=N/8n = N/8, то я знаю исходную длину массива, который сделал в предподсчёте, знаю текущую длину, знаю, корень какого порядка мне нужен, — и значит, знаю, с каким шагом идти по массиву. Видимо, с шагом N/nN/n. Соответственно, к jj-му корню я обращаюсь так:

root[j * N / n]

Вот это и будет ωj\omega_j нужного порядка.

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

— Серёж, а можешь ещё раз тезисно, что произошло? Мы ввели этот массив корней и…

У меня была математическая формула. Математическую формулу нельзя запрограммировать напрямую, потому что в коде нет этих значков. Я только что сказал, что вместо ω\omega я буду подставлять вот такую штуку. Что это такое? У меня есть один посчитанный массив корней порядка NN; когда мне понадобится корень порядка nn, — а nn всегда получается из NN делением пополам, в рекурсии всегда пополам, — я вот так к нему обращусь. Я посмотрел, что нужно идти с некоторым шагом, и понял, что в общем случае шаг именно такой.

Теперь про оптимальность вычислений. Более оптимальный способ выглядит так. На контесте, честно говоря, не помню, как было; я планирую, что везде будет заходить и этот способ, но не проверял. Более быстрый способ говорит, что корни с номерами 2j2j и 2j+12j+1 мы будем получать из jj-го корня. Соответственно, косинус и синус я вызову только один раз — когда посчитаю ω1\omega_1. Для краткости массив корней будем обозначать буквой rr. Оказывается, что

r[2 * j]     = r[j] * r[j];
r[2 * j + 1] = r[2 * j] * r[1];

то есть r2j=rj2r_{2j} = r_j^2, а r2j+1=r2j⋅r1r_{2j+1} = r_{2j} \cdot r_1. Несмотря на то, что здесь тоже много умножений, глубина цепочек умножений уже не nn, а всего log⁡n\log n. Поэтому на практике погрешность оказывается удовлетворительной. В первом варианте, когда длина цепочки умножений была nn, напоминаю, под угрозой была даже точность в маленькой системе счисления; здесь же я теряю примерно полразряда. То есть, скажем, работало для 104.510^{4.5} — теперь работает для 10410^{4}, что-то такое.

Переходим собственно к Фурье. Пишем код FFT. Я получаю вектор aa и должен вернуть его преобразование Фурье — ещё один вектор. Длина вектора aa — это как раз степень двойки, ∣a∣=2k=n|a| = 2^k = n, и эту степень я буду обозначать kk. В некоторых реализациях люди любят таскать kk за собой; мне оно, вроде бы, нигде не нужно, поэтому я не буду. Итак, nn я сохраню из вектора — я знаю его size.

Теперь мне нужно разбить aa на два кусочка, a0a_0 и a1a_1. Я пробегаюсь по индексам и в зависимости от чётности записываю элемент либо в a1a_1, либо в a0a_0. Через push_back, кажется, можно, да? То есть a1a_1 — это вектор нечётных, a0a_0 — вектор чётных. Получил два вектора.

for (int i = 0; i < n; i++)
    (i & 1 ? a1 : a0).push_back(a[i]);

Что дальше? Собственно, рекурсивные вызовы: длины этих векторов в два раза меньше, поэтому от a0a_0 я могу вызвать себя, и от a1a_1 я тоже могу вызвать себя. Теперь надо из двух ответов получить то, что я верну. Пусть fafa — вектор из nn нулей; в него я и буду записывать ответы. Пишем по формуле — на всякий случай выпишу её в рамочке. Буква aa у меня занята вектором коэффициентов, поэтому многочлен обозначу большой буквой:

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

Вот это та формула, которую я хочу использовать в цикле for. В неё я хочу подставить x=ωjx = \omega_j. Причём многочлен A0A_0 считался только от квадратов, поэтому если здесь я беру jj-й корень, то туда мне нужно взять jj-й квадрат. Поэтому fa[j]fa[j] — это просто fa0[j]fa_0[j] плюс корень ωj\omega_j, умноженный на fa1[j]fa_1[j]. Это единственное место, где я использую ωj\omega_j, и сюда я его и поставлю — к предподсчитанному массиву надо обратиться. Беру из предподсчитанного массива нужное мне значение: я хочу jj-й корень, но иду с большим шагом, потому что текущее nn уже отличается от исходного NN.

В этом коде есть сейчас ровно одна ошибка. Я не учёл, что квадраты пробегают цикл два раза. Если корни, когда я их рисую на круге, бегут вот так, то квадраты бегут с вдвое большим шагом — а значит, проходят круг два раза. Поэтому при обращении к массивам нужно не забывать брать jj по модулю длины меньшего массива. Длину меньшего массива можно было бы обозначить n′n', и n′=n/2n' = n/2, но давайте без штрихов — не будем вводить лишние обозначения, просто напишу «пополам». И модуль нужно применить к обоим индексам:

vector<comp> fa(n);
for (int j = 0; j < n; j++)
    fa[j] = fa0[j % (n / 2)] + root[j * N / n] * fa1[j % (n / 2)];
return fa;

Вопросы по идее, по коду, по предподсчёту?

— Серёж, можешь ещё раз пояснить, когда мы обращаемся к половинкам, которые так же посчитали, к чётным и нечётным, почему там jj по модулю?

Потому что там я считал от всех квадратов. Соответственно, первому корню отсюда соответствует первый квадрат, второму — второй квадрат. Если сейчас n=4n = 4, я хочу посчитаться в точках 1,i,−1,−i1, i, -1, -i, то в рекурсивном вызове я сосчитаю не от этих четырёх точек, а только от n/2n/2 точек — от точек 11 и −1-1. Дальше: точке 11 соответствует квадрат 11, точке ii — квадрат −1-1, точке −1-1 — снова квадрат 11, точке −i-i — снова −1-1. При возведении в квадрат остаются только 11 и −1-1. Ещё что-нибудь?

Нужно ещё сказать про базу. Когда мы писали код, я до этого отвечал на этот вопрос, но по ходу мы забыли: если длина равна единице — вот здесь, когда мы узнаём длину, — то я, естественно, возвращаю просто a0a_0, поскольку ω0=1\omega_0 = 1. Это про то, что на нижнем уровне рекурсии всё просто.

if (n == 1) return a0;

Эта версия Фурье считается просто — это простая версия, которой никто никогда не пользуется, потому что она бесконечно долго работает. Асимптотика, конечно, O(nlog⁡n)O(n \log n), но нам надо, чтобы она работала ещё раз в десять быстрее. Хотя, ладно, она не прямо плохая: если выберем хорошую систему счисления, она вполне норм. Хуже было бы, если бы вот тут вы написали прямо косинус и синус — тогда был бы честный 100% TL. Или если бы пытались вычислять корни nn-го порядка вместо обращения к предподсчитанному массиву. Как только мы ввели предподсчёт, мы решили почти все проблемы; осталось дорешать остальные.

Переходим к хорошей реализации Фурье. Вообще, сейчас это чем-то похоже на merge sort. Классическая схема «разделяй и властвуй»: взяли две половинки, сделали от них рекурсивный вызов, по двум половинкам собрали результат. А merge sort можно было написать нерекурсивно.

— Помните, как нерекурсивно писать merge sort?

— Снизу вверх.

Да, снизу вверх. Давайте, перед тем как переходить к новому алгоритму, я нарисую картинку для merge sort. Она выглядит вот так — это дерево merge sort. Давайте нарисую подробнее, там ещё отдельные элементы были: изначально у нас массив вот в таком состоянии. Как делать нерекурсивно? Подниматься вверх по слоям и говорить, что мы идём шагом степени двойки: вот здесь пойдём шагом 22, вот здесь шагом 44 и так далее, — и будем вызывать merge половин. Идём шагом 22, вызываем merge половин; идём шагом 44, вызываем merge половин.

Фурье — то же самое. Смотрите, вот у нас написан merge половин — вот он. Давайте идти снизу вверх и делать то же самое, что в merge sort. Видите: половинка fa0fa_0, половинка fa1fa_1, и я могу записать результат слияния на то же самое место. Нюанс только один: merge sort, когда спускался вниз, не переставлял элементы — он просто спускался, а всё интересное происходило потом. А здесь я, когда спускаюсь вниз, хитро переставляю коэффициенты: сперва идут чётные коэффициенты, потом нечётные.

Я сейчас оптимизирую код принципиально, потому что вот этот кусочек кода, который переставляет коэффициенты, тоже работает за nlog⁡nn \log n. Пока спускался — выполнял перестановки на каждом уровне; а теперь я чуть подумаю, пойму, в каком порядке их нужно расставить, и сразу поставлю их за линейное время в правильном порядке. Сперва идут чётные, потом нечётные. Обычно как идут числа? Обычно сперва идут те, у которых старший разряд — ноль, а потом те, у которых старший разряд — один. А у нас сейчас сперва идут числа, у которых младший разряд — ноль, а потом те, у которых младший разряд — один. Значит, нужно записать числа в порядке обратной битовой записи.

Пусть aa — исходный массив, и я не буду его трогать. Мне дали массив; я — функция FFT, и не принято портить входные данные, которые мне кто-то дал: вдруг они ценные. Я буду создавать массив fafa. Сперва я запишу в fafa то, что лежит на самом нижнем уровне, а потом несколько раз вызову цикл for, который мержит половинки. Изначально в fafa по индексу «перевёрнутая битовая запись числа ii» я запишу значение a[i]a[i]:

fa[rev(i)] = a[i];

— А что такое rev(i)rev(i) ещё раз?

rev(i)rev(i) — это обратная битовая запись числа ii. У меня сейчас есть все числа от нуля до некоторой степени двойки.

— «Обратная» — это в смысле «меньше»?

Нет, в смысле «реверс строки». Реверс строки. Я хочу сперва поставить числа, у которых младший бит — ноль, на те места, где они стояли в исходном массиве. Нет, получается неочевидно; давайте я произнесу так, чтобы было прямо очевидно. Что такое обратная битовая запись числа? Видимо, начинать нужно вот так.

Естественно, revrev — это перестановка порядка два: если применю её два раза, ничего не поменяется. Поэтому неважно, пишу я revrev тут или там — код будет работать одинаково. Но по смыслу того, как я сейчас объясняю, revrev надо написать вот здесь:

fa[i] = a[rev(i)];

Итак, что стоит на ii-й позиции? На ii-й позиции стоит то число, у которого младший бит такой, как у ii старший, следующий бит такой, как у ii следующий сверху, и так далее. То есть я перевернул битовую запись ii и посмотрел, какое же aa встало на эту позицию.

Как всё-таки посчитать массив revrev? Мы это уже делали, когда проходили динамику по подмножествам в первом семестре: rev[i]rev[i] считается динамикой. Нужно сперва перевернуть все биты, кроме первого, а все биты кроме первого — это i/2i/2. Давайте на картинке попробуем понять, что такое «все биты кроме первого» и как они переворачиваются. Вот число, вот все биты кроме первого. Казалось бы, беда — но они как раз перевернутся, всё прекрасно, и автоматически встанут на нужные позиции. Если тут был порядок 0,1,2,3,40, 1, 2, 3, 4, то в результате переворота я как раз получу… или нет? Или да? Сейчас.

Нет, я пытался вас обмануть. Не ровно то же самое: в числе всегда ровно kk бит. Если я возьму i/2i/2 и начну переворачивать, то из-за сдвига к числу дописался нолик, и после переворота этот нолик как раз встанет на первую позицию — вот этот нолик я лучше буду обозначать звёздочкой. Итого результат переворота: фиктивный нолик встанет на младшую позицию, а дальше пойдут уже все биты 0,1,2,30, 1, 2, 3 и так далее до конца числа. Поэтому мне нужно результат переворота числа i/2i/2 ещё поделить пополам — сдвинуть вот в эту сторону. А потом нужно ручками взять младший бит числа ii и поставить его на старшую позицию. Я так и делаю: беру rev[i/2]rev[i/2], сдвигаю его, и добавляю младший бит на место старшего:

rev[i] = rev[i / 2] / 2 + ((i & 1) << (k - 1));

здесь ii пробегает все значения из [0,  2k=N)[0,\; 2^k = N).

Нерекурсивное БПФ: бабочка и битреверс

Доска 5 — бабочка in place, итеративный код и битовый разворот

Этот предподсчёт я делал один раз заранее — тогда же, когда вычислял корень. При каждом умножении я его повторять не буду. Спуск вниз закончен, теперь надо писать подъёмы. Давайте я их напишу, потому что там тоже есть что заоптимизировать — ровно в два раза.

Я перепишу цикл for, который у меня сейчас есть. Я буду вести его по jj от нуля не до nn, а — внимание — до n/2−1n/2 - 1 включительно, то есть до n/2n/2. Я сделаю только половину работы и напишу

fa[j] = fa0[j] + w[j] * fa1[j];

то есть fa[j]=fa0[j]+ωj⋅fa1[j]fa[j] = fa_0[j] + \omega_j \cdot fa_1[j]. Корень ωj\omega_j я здесь пишу для понятности: формулу мы один раз выписали, второй раз переписывать её лень.

Что будет происходить, когда я пойду во вторую половину? Раньше цикл шёл от нуля до n/2n/2, а теперь посмотрим на значения от n/2n/2 до n−1n - 1. В том коде индекс jj брался как раз по модулю n/2n/2, поэтому в обращениях к массивам fa0fa_0 и fa1fa_1 ничего не поменяется. Поменяется только корень. Чем корень с номером n/2+jn/2 + j отличается от jj-го корня?

— Как из корня ωj\omega^j быстро получить корень ω n/2+j\omega^{\,n/2 + j}?

— Они почти равны, но со знаком минус.

Да. Нарисуем картинку. Вот корни, которые шли до номера n/2n/2, а вот следующие корни. Каждый из них как раз получается из предыдущей половины: вот нулевой корень и вот корень номер n/2n/2, вот первый корень и вот корень номер n/2+1n/2 + 1. Каждый раз это тот же корень с минусом.

Это было геометрическое объяснение, а можно понять то же самое и алгебраически. По определению ω n/2+j=ω j⋅ω n/2\omega^{\,n/2 + j} = \omega^{\,j} \cdot \omega^{\,n/2}, а ω n/2\omega^{\,n/2} внезапно равно −1-1: если взять корень nn-й степени из единицы и возвести его в степень n/2n/2, получится ровно −1-1. Итого ω n/2+j=−ω j\omega^{\,n/2 + j} = -\omega^{\,j}.

Если бы я сейчас написал второй цикл for, мне нужно было бы сделать в нём всё то же самое, только произведение взять со знаком минус. Вывод: я могу делать в два раза меньше умножений комплексных чисел. Я могу прямо в том же самом цикле for дописать строчку fa[j+n/2]=A−Bfa[j + n/2] = A - B. Давайте обозначим те половинки, которые я уже посчитал: A=fa0[j]A = fa_0[j], B=ωj⋅fa1[j]B = \omega_j \cdot fa_1[j]. Я как раз ввёл специальные переменные, сохранил в AA, сохранил в BB — и теперь просто пишу A+BA + B и A−BA - B:

for (int j = 0; j < n / 2; j++) {
    A = fa0[j];
    B = w[j] * fa1[j];
    fa[j]         = A + B;
    fa[j + n / 2] = A - B;
}

У меня уменьшилось число обращений к памяти и уменьшилось число умножений.

Осталось сказать, кто такие массивы fafa, fa0fa_0 и fa1fa_1. Вы можете писать как-то иначе, но по смыслу надо записать в fa, fa0 и fa1 указатели на правильные куски массива. Вы же можете пользоваться не только векторами, а прямо указателями — это C++-ный трюк. Тогда fa — указатель вот сюда, туда же, куда указывает fa0; fa0 — указатель на первую половину, fa1 — на вторую.

И здесь есть ещё приятный момент. Смотрите: когда я работаю с jj-й ячейкой, данные я беру из jj-й и из (j+n/2)(j + n/2)-й ячейки — это как раз fa0[j]fa_0[j] и fa1[j]fa_1[j]. И результат я записываю в те же самые ячейки. Поэтому мне не нужно каждый раз создавать новый массив fa. Как это делается в merge sort: взяли две половинки, результат слияния — абсолютно новый массив. Здесь я тоже планировал начать так делать: fa0fa_0 и fa1fa_1 — две половинки, результат слияния — новый массив, который потом скопирую на место. Но я могу сделать преобразование прямо в том же самом месте — просто потому что на картинке увидел, что ячейки как раз совпадают.

Пишем код. Сперва перебираем степень двойки, для которой у меня уже всё посчитано: перебираем kk, пока k<Nk < N, и каждый раз умножаем kk на два. Моя цель — взять два кусочка длины kk и смержить их в кусочек длины 2k2k. Дальше я перебираю начало кусочка: перебираю ss с шагом 2k2k, естественно, пока оно не вылезет за пределы массива.

— А может, в первом цикле for ты имел в виду k++?

— Нет, именно k∗=2k \mathrel{*}= 2. Можно было выбрать показатель степени двойки, а можно саму длину — у меня kk это именно длина блока, степень двойки. Я хочу пользоваться таким kk, поэтому в условии пишу k<Nk < N.

Теперь вношу самый главный цикл. Сейчас у меня два кусочка длины kk — рисую картинку — мержатся в один кусочек длины 2k2k. Внутренний цикл for будет идти именно до kk: я перебираю все элементы одного из кусочков, jj от нуля до k−1k - 1 включительно. И дальше я пишу четыре строчки кода: A=…A = \ldots, B=…B = \ldots и две записи в массив.

for (int k = 1; k < N; k *= 2)
    for (int s = 0; s < N; s += 2 * k)
        for (int j = 0; j < k; j++) {
            A = fa[s + j];
            B = roots[j * N / (2 * k)] * fa[s + j + k];
            fa[s + j]     = A + B;
            fa[s + j + k] = A - B;
        }

Чему равно AA? Это элемент массива fa[s+j]fa[s + j]. Чему равно BB? Это нужный корень, умноженный на элемент второй половины. Корень я копирую из массива roots: беру roots[ j⋅N/(2k) ]roots[\,j \cdot N / (2k)\,] — видите, делить надо именно на 2k2k, потому что когда я мержу два кусочка длины kk в кусочек длины 2k2k, я хочу брать корни порядка 2k2k. Умножить это надо на fa[s+j+k]fa[s + j + k]. И оставшиеся две строчки: я беру две ячейки, первая — fa[s+j]fa[s + j], вторая — fa[s+j+k]fa[s + j + k], и пишу в них A+BA + B и A−BA - B.

Здесь важная поправка: в двух местах я по инерции написал n/2n/2, а должно быть kk — спасибо. Сейчас поправлю оба места. И да, правильно заметить, что в этих обозначениях n=2kn = 2k, а значит n/2=kn/2 = k. Просто где-то в предыдущей жизни у меня числа kk не было, а в цикле for я почему-то решил его использовать.

Это называется быстрое нерекурсивное преобразование Фурье. На него можно навешивать ещё какие-то небольшие оптимизации, но всю принципиальную работу мы уже сделали. Давайте перечислим, что произошло. Первое: я сразу написал код с предпосчитанными корнями — корни заранее предпосчитал, разменивая память на время. Второе: мы избавились от той части работы объёмом nlog⁡nn \log n, которую делали на этапе рекурсивного спуска, сказав, что у нас есть перевёрнутые биты (битреверс) и элементы исходного массива изначально расставлены в правильном порядке. Третье: когда я мержу кусочки, мне не нужен специальный новый массив, чтобы копировать туда результат. Раньше fa0fa_0 и fa1fa_1 были отдельными массивами, и потом я создавал новый массив и записывал результат в него. Теперь я делаю преобразование прямо в том же самом месте: беру два элемента, вот это AA, вот это BB, и крест-накрест меняю их друг с другом.

— Серёжа, можешь ещё раз про индексацию s+js + j, почему она такая?

— Начиная с позиции ss в массиве сейчас лежат подряд два массива, которые в предыдущей жизни назывались у нас fa0fa_0 и fa1fa_1. Соответственно, если я хочу обратиться к fa0[j]fa_0[j], я обращаюсь к fa[s+j]fa[s + j]. Аналогично с fa1[j]fa_1[j]: к началу ss надо добавить длину первой половины, и поскольку половина — это kk, получается fa1[j]=fa[s+k+j]fa_1[j] = fa[s + k + j].

Теперь вы хранители тайного знания о том, как писать Фурье нормально. У вас будет возможность это применить. Советую сперва попробовать написать рекурсивно: там всё идёт по формуле — видим одну формулу, применяем её, и сразу работает. Нерекурсивная версия — это результат нескольких заходов размышлений, и в ней есть ровно два места, где легко ошибиться, несмотря на то что получается красиво и коротко. Если вы хотите уметь это самостоятельно, лучше начинать с рекурсивной версии. Специально для этого на Codeforces есть задачка, и там заходит почти всё что угодно — ну, как «всё что угодно»: надо всё-таки помнить про константу и подсчитывать.

Давайте поговорим о тематике. За семестр мы не прошли две темы: одна называется теория чисел, вторая — архиваторы. Содержание лекции про архиваторы: это Хаффман; это арифметическое кодирование, то есть Хаффман с нецелыми длинами кодов; это LZSS и алгоритмы, как написать его за линейное время, с некоторыми техническими подробностями, как написать правильно. И это BWT — преобразование Барроуза–Уилера — плюс MTF (move-to-front) плюс RLE, то преобразование, которое обычно делают до Хаффмана. Мы двумя способами научимся получать такой же хороший результат, как делают архиваторы RAR. И ещё поговорим про теорию информации.

— А вы в BWT уже поняли, как делать обратное преобразование?

— Нет, ещё не поняли.

А в теории чисел — дискретное логарифмирование, поиск первообразного корня. Вы знаете, что это такое? Вы, кстати, знали, как первообразный корень искать?

— Искать перебором.

Да, и ещё про то, где всё это нужно и как применять, например в длинной арифметике, при работе с первообразными корнями; дискретное логарифмирование, чуть-чуть про факторизацию — наверное, совсем чуть-чуть, и ещё что-то там было. Кажется, я уже рассказал про обратные числа и про решето — а тут будет немного подробнее, как считать всякие функции. Итак, есть выбор: архиваторы или теория чисел. Могу выбрать я, а можете сейчас проголосовать, кто что хочет.

— Это за сегодня?

— Нет, сегодня мы это не будем. У нас сегодня предпоследняя лекция, и вы получите домашку про Фурье. Следующая лекция будет последней, и домашки не предполагается: практика будет, а домашки через неделю не будет. Поэтому вы можете выбрать ту тему, которая вам интереснее. Семестр у нас на этом заканчивается. В принципе, если будет желание, можно в какой-нибудь день просто собраться онлайн и рассказать оставшуюся часть.

Я предлагал рассказать что-нибудь одно из двух: или архиваторы, или теорию чисел. По умолчанию у меня стояли архиваторы, так что если вы сейчас ничего не поменяете, то будет про архиваторы. Голосуем. Теория чисел: раз, два, три, четыре, пять, шесть, семь. Архиваторы: раз, два, три, четыре, пять, шесть, семь, восемь. Вам, конечно, надо было встать, чтобы я считал аккуратнее. Итого: архиваторы — восемь голосов, теория чисел — семь. Здорово. Меня, и не только меня, всегда удивляло, почему в некоторых странах с двухпартийными системами выборы каждый раз проходят прямо на грани, 45–50%. А у нас сейчас получилось точно так же, причём само по себе — я к такому не готовился.

Возвращаемся в мир FFT. Сегодня нам нужно доделать преобразование Фурье: мы ещё не знаем обратное преобразование и не знаем, как использовать FFT именно для умножения чисел. Казалось бы, всё уже есть: есть чёрный ящик FFT, есть схема — сперва применить прямое преобразование, потом поточечно умножить, потом применить обратное, и всё. Но вы же видите, что FFT работает с комплексными числами, а многочлены, которые вы хотите умножать, обычно с вещественными, даже с целыми коэффициентами. Нельзя ли это как-то подхачить — поиспользовать то, что исходные коэффициенты вещественные, а преобразование мы делаем от комплексных чисел? Ответ, конечно, да, можно.

Если наши исходные многочлены — это AA и BB, то я могу получить два преобразования Фурье за одно. Я беру FFT от массива CC, где cj=aj+i⋅bjc_j = a_j + i \cdot b_j: из двух вещественных чисел очень естественно сделать одно комплексное. Сделали, запустили FFT от массива CC — и теперь нужно сделать расщепление, то есть расщепить результат на F(A)F(A) и F(B)F(B). Это универсальный приём, его можно применять не только в умножении двух чисел.

Как расщепить? Когда я начинаю думать про формулу, у меня что-то в фоновом режиме напрягается, но на самом деле расщепление — это просто одна формула; давайте разберёмся, что в ней происходит. Если бы у меня было просто комплексное число, то я бы взял сопряжённое к нему, чтобы получить действительную часть: 12(cj+cj‾)=Re⁡cj\tfrac{1}{2}\left(c_j + \overline{c_j}\right) = \operatorname{Re} c_j. Вот так вообще достаётся вещественная часть. Значит, мне нужно научиться делать сопряжение — но не самого cjc_j, а внутри: у меня от таких коэффициентов уже посчитано что-то сложное, и сопрягать я хочу как бы под преобразованием.

Начнём с простого. Если у меня есть jj-й корень, то чему равно его сопряжение?

— Умножить на минус один?

— Нет-нет-нет, а что такое сопряжение? Давайте нарисуем на картинке. Сопряжение — это явно не умножение на минус один: умножение на минус один — это поворот на π\pi, а сопряжение — это отражение относительно вещественной оси. Вот jj-й корень, а вот сопряжённый к нему. Какой это корень?

— Можно сказать, что N−jN - j-й.

— Да, а можно коротко написать ω j‾=ω−j\overline{\omega^{\,j}} = \omega^{-j}: естественно, я всё понимаю по модулю NN, так что это и есть ω N−j\omega^{\,N-j}.

Теперь подумаем про свойства сопряжения. Если я сопрягаю произведение двух чисел, я утверждаю, что это то же самое, что сперва сопрячь каждое, а потом умножить: xy‾=x‾⋅y‾\overline{xy} = \overline{x} \cdot \overline{y}. По сути сопряжение — это умножение угла на минус один, а при умножении комплексных чисел углы просто складываются. Поэтому я могу сперва сложить углы, а потом умножить результат на минус один, а могу сперва умножить оба угла на минус один, а потом сложить — получится одно и то же. Про сложение можно сказать то же самое: сопряжение суммы — это сумма сопряжений, x+y‾=x‾+y‾\overline{x + y} = \overline{x} + \overline{y}.

И этого мне, наверное, хватит для счастья. Потому что что такое преобразование Фурье? Это подстановка корней в многочлен, то есть сплошные умножения и сложения. Сопрягать сам корень я уже умею, а умножения и сложения у меня теперь тоже под контролем.

Обратное преобразование и итоговая схема умножения

Доска 6 — схема умножения через БПФ, обратное преобразование и лемма Σω^j = 0

Сопряжение можно вынести за все умножения и все сложения — именно на этом держится трюк. Посмотрим, что у нас есть. Есть многочлен CC, составленный из двух множителей: C(x)=A(x)+i⋅B(x)C(x) = A(x) + i\cdot B(x), где AA и BB — многочлены с вещественными коэффициентами. Есть посчитанные значения: C(ωj)=f[j]C(\omega_j) = f[j], а C(ωj‾)=f[−j]C(\overline{\omega_j}) = f[-j]. Моя задача — из посчитанных значений C(ωj)C(\omega_j) вытащить A(ωj)A(\omega_j) и B(ωj)B(\omega_j). Если кто-то уже видит, как это сделать, можете меня ускорять.

Если бы у меня было сопряжение C(ωj)‾\overline{C(\omega_j)}, всё было бы очень просто. И ведь оно у меня есть: я могу взять конкретное посчитанное комплексное число и просто его сопрячь — гениально, никакого дополнительного преобразования Фурье для этого не нужно. Давайте расписывать, чему это сопряжение равно. Поскольку в комплексных числах и сложение, и умножение можно вынести за сопряжение, получается

C(ωj)‾=A(ωj)‾+i⋅B(ωj)‾=A(ω−j)−i⋅B(ω−j)\overline{C(\omega_j)} = \overline{A(\omega_j)} + \overline{i\cdot B(\omega_j)} = A(\omega_{-j}) - i\cdot B(\omega_{-j})

Здесь я воспользовался тем, что мои конкретные AA и BB — вещественные: сопряжение их коэффициентов ничего не делает, оно только сопрягает аргумент, то есть переводит ωj\omega_j в ω−j\omega_{-j}. А сопряжение мнимой единицы — это минус ii, отсюда и минус перед вторым слагаемым.

Если я хочу, чтобы здесь был не минус, а плюс, нужно брать сопряжение в точке ω−j\omega_{-j}. Итого получаются такие формулы для коэффициентов прямого преобразования Фурье многочленов AA и BB:

fa[j]=Re⁡12(fc[j]+fc[n−j]‾),fb[j]=Im⁡12(fc[j]−fc[n−j]‾)fa[j] = \operatorname{Re}\tfrac{1}{2}\bigl(fc[j] + \overline{fc[n-j]}\bigr),\qquad fb[j] = \operatorname{Im}\tfrac{1}{2}\bigl(fc[j] - \overline{fc[n-j]}\bigr)

Индекс n−jn-j я ставлю под сопряжение, чтобы после сопряжения там оказался как раз нужный мне jj. В первой формуле мнимые части сократились, и осталась вещественная. Во второй, наоборот, сократилась вещественная, а мнимая осталась с коэффициентом 2i2i, поэтому строго математически там стоит не 12\tfrac{1}{2}, а 12i\tfrac{1}{2i}. Но делить на 2i2i не нужно: можно поделить пополам и взять мнимую часть числа. Поэтому в реализуемой форме я пишу так: здесь беру вещественную часть, а здесь — просто мнимую. У стандартных комплексных чисел всё это, естественно, есть: real и imag.

Кстати, про стандартные комплексные числа. Когда вы в прошлые годы писали свои комплексные числа вместо std::complex, программа начинала работать процентов на десять быстрее. Я до сих пор не знаю, за счёт чего, но чуть-чуть ускориться так можно. Казалось бы, как можно неправильно написать комплексные числа? Умножение, деление, вещественная часть, мнимая часть — как ни пиши, всегда получится одинаково. А вот пишешь сам — получается на десять процентов быстрее. Если когда-нибудь узнаете почему, расскажите мне, мне это очень интересно.

Вопрос: во сколько раз последняя оптимизация позволила ускорить итоговый алгоритм умножения двух длинных чисел AA и BB через Фурье? В полтора раза. Изначально у нас было три преобразования Фурье: два прямых сверху и одно обратное. Теперь — одно прямое и одно обратное, то есть два вместо трёх. Ускорение в полтора раза.

Переходим к обратному FFT, и начнём с реализации. Пусть у нас есть функция FFT. Я умею применять её к исходному массиву aa — получается прямое преобразование Фурье. Чтобы получить aa обратно, достаточно написать

a = FFT(fa);

и потом сделать ещё две вещи. Первая — пореверсить всё, кроме нулевого элемента: reverse(a + 1, a + N). Этот плюс один означает, что нулевой элемент я оставляю на своей позиции. Вторая — не забыть поделить весь массив на константу: a /= N. Что константа равна именно NN, мы поймём по ходу доказательства. Итого функция одна, и прямой ход, и обратный.

Есть и другая реализация, которая работает чуть иначе. Она говорит, что можно пользоваться практически одной и той же функцией, но с параметром: fa=FFT(a,ω)fa = FFT(a, \omega), а потом a=FFT(fa,ω−1)a = FFT(fa, \omega^{-1}). Тогда нужно запускать функцию либо в точке ω\omega и её степенях — ω0,ω1\omega^0, \omega^1 и так далее, — либо в точке ω−1\omega^{-1} и её степенях: ω−1,ω−2,ω−3\omega^{-1}, \omega^{-2}, \omega^{-3}. Деление на NN при этом остаётся, а реверс уходит. Но этот /= N всё равно придётся дописывать после вызова FFT, то есть какой-то код снаружи остаётся в любом случае. Чтобы упростить себе код функции FFT и предподсчёт, я обычно на этот параметр забиваю и делаю реверс.

Давайте сперва поймём, почему реверс в точности эквивалентен вычислению в точке ω−1\omega^{-1}. Что у меня записано в ячейках до реверса? Значение в точке ω0\omega^0, значение в точке ω1\omega^1, значение в точке ω2\omega^2 и так далее. После реверса в первой ячейке оказывается значение в точке ωN−1\omega^{N-1}. А мы знаем, что ωN−1=ω−1\omega^{N-1} = \omega^{-1}. Одной строчкой reverse я добился того, что в массиве теперь записаны значения многочлена в степенях ω−1\omega^{-1}.

Доказательство. Что у нас есть? У нас есть такие суммы:

fak=∑jaj⋅ωj⋅kfa_k = \sum_j a_j \cdot \omega^{j\cdot k}

Здесь aja_j — мой коэффициент, а ωj⋅k\omega^{j\cdot k} — это kk-й корень, возведённый в степень jj; сам kk-й корень получается из исходного возведением в степень kk. Давайте распишу эти суммы подлиннее, чтобы с ними было проще общаться, — получится вот такая табличка:

fa0=a0+a1ω0+a2ω0+a3ω0+…fa_0 = a_0 + a_1\omega^0 + a_2\omega^0 + a_3\omega^0 + \ldots fa1=a0+a1ω1+a2ω2+a3ω3+…fa_1 = a_0 + a_1\omega^1 + a_2\omega^2 + a_3\omega^3 + \ldots fa2=a0+a1ω2+a2ω4+a3ω6+…fa_2 = a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6 + \ldots

В первой строке я подставляю ω0\omega^0, во второй — ω1\omega^1, в третьей — ω2\omega^2. Надеюсь, на трёх строчках уже понятно, что я делаю. Я знаю массив fafa и хочу узнать массив aa.

Как найти a0a_0, как вы думаете? Обратите внимание: a0a_0 присутствует в каждой сумме. Например, fa0fa_0 — это просто сумма всех коэффициентов; про остальные строки так сказать уже нельзя, там у коэффициентов стоят разные степени корня. Я предлагаю вам сейчас мысленно сложить все строчки, складывая их по столбцам. Сумма первого столбца — это, очевидно, N⋅a0N\cdot a_0: в первом столбце везде написано a0a_0. Сумма второго столбца — это a1a_1, умноженное на сумму всех ω\omega, и эта сумма оказывается равна нулю. Сумма следующего столбца — это a2a_2, умноженное на сумму степеней ω\omega с шагом два; поскольку ω\omega — корень nn-й степени, здесь суммируются корни степени n/2n/2.

Сформулируем лемму: ∑jωj=0\sum_j \omega^{j} = 0. Доказывали вы когда-нибудь такое? Геометрически. Доказательств много, а я хотел повторить уже известное вам, так что давайте геометрическое. Можно было бы сказать, что для каждого слагаемого найдётся противоположное ему, и слагаемые соберутся по парам, — но это точно правда только для чётных nn, хорошая ремарка. Поэтому произнесу геометрическое доказательство иначе. Если повернуть весь этот круг на ω\omega, то есть на угол 2π/n2\pi/n, то множество слагаемых перейдёт в себя. Значит, ответ — это какое-то комплексное число, которое не меняется от поворота на некоторый угол. Я знаю только одно такое число — это ноль. Множество слагаемых не поменялось от поворота, значит, и сумма не поменялась, значит, это число — ноль.

Единственное исключение — на какой угол поворачивать нельзя, чтобы доказательство осталось корректным. Нельзя поворачивать на нулевой угол; если поворачиваем на любой ненулевой, доказательство имеет смысл. Поэтому с первым столбцом так и выходит: угол, на который там нужно поворачивать, — это ω0\omega^0, то есть угол нулевой, и при повороте число остаётся собой. Для остальных столбцов углы поворота — ω1\omega^1, ω2\omega^2 и так далее; все эти числа не единицы, угол не нулевой, поэтому все суммы зануляются.

Итак, мы научились получать a0a_0: это просто сумма всех fafa, поделённая на большое NN. Как теперь получить a1a_1? Я хочу привести мои строки примерно к такому же виду, чтобы у a1a_1 везде коэффициент был единицей. Для этого fa0fa_0 я умножу на ω−0\omega^{-0}, fa1fa_1 — на ω−1\omega^{-1}, fa2fa_2 — на ω−2\omega^{-2} и так далее, целиком всю сумму. Тогда в столбце, соответствующем a1a_1, получится N⋅a1N \cdot a_1, а остальные столбцы по той же лемме занулятся.

Давайте теперь внимательно посмотрим на ту величину, которую я при этом посчитал. Чтобы вернуть a1a_1, я взял fa0fa_0 на какую-то степень ω\omega, fa1fa_1 на какую-то степень ω\omega и так далее — а это ровно значение многочлена с коэффициентами fafa в точке ω−1\omega^{-1}. Проверим гипотезу, что это и правда похоже на подстановку в многочлен. Чтобы получить a2a_2, мне нужно домножить строки на ω−0,ω−2,ω−4\omega^{-0}, \omega^{-2}, \omega^{-4} и так далее, то есть я подставляю в многочлен FAFA точку ω−2\omega^{-2}.

Сделаю вывод:

aj=1N⋅FA(ω−j)a_j = \frac{1}{N}\cdot FA(\omega^{-j})

где FAFA — многочлен с коэффициентами fafa. И эту величину можно посчитать двумя способами: либо чуть подкостылить функцию FFT внутри, либо в конце взять и перевернуть результат.

— Вопросы по обратному преобразованию? А где у нас само перемножение? Где перемножение многочленов?

Да, оно потерялось. С произведением многочленов у нас никогда не было проблем, поэтому мы им особо и не занимались. Схема состоит из трёх кусочков: из aa получить fafa, потом перемножить значения, потом сделать обратное преобразование. Зная значения двух многочленов AA и BB в точке, значение произведения получаем так: берём значения в одной и той же точке и перемножаем. Запишу на всякий случай:

(AB)(x)=A(x)⋅B(x)(AB)(x) = A(x)\cdot B(x)

Поэтому в каждой точке мы тратим одну операцию.

— В формуле, где мы выражаем aja_j: как получается, что такое FAFA и почему умножается на ω−j\omega^{-j}? Рассуждения, которые были рядом, я понял, а как обобщить их до общей формулы — нет.

Вот эта степень — это на самом деле произведение номера строки на номер столбца. Я заметил, что когда я первый столбец делаю единичным, мне нужно домножать на ω\omega в степени «номер строки». Для следующего столбца нужно домножать на ω\omega в степени «номер строки, умноженный на два», а это то же самое, что подставить в многочлен с коэффициентами FAFA точку ω−2\omega^{-2}. Что-то у меня непонятно получается — давайте попробуем по-другому: меньше конкретных чисел, больше общих формул. Расписываю прямо:

FA(ω−j)=∑kfak⋅ω−j⋅kFA(\omega^{-j}) = \sum_k fa_k \cdot \omega^{-j\cdot k}

То есть я сложил все суммы в строках с какими-то коэффициентами. На картинке мы разобрали случаи j=0j = 0, j=1j = 1, j=2j = 2. На какие коэффициенты нужно домножать суммы в строках в общем случае? В общем случае нужно домножать на минус те степени, которые стоят в этом столбце, а в столбце стоят ровно ωj⋅k\omega^{j\cdot k}. Вот вся матрица: её (j,k)(j,k)-я ячейка — это aj⋅ωj⋅ka_j \cdot \omega^{j\cdot k}, где jj — номер столбца, а kk — номер строки. Я просто говорил всё это без общего индекса, потому что так обычно легче воспринимается, поэтому общий индекс нигде и не писал. Так вот, aja_j имеет вот такой коэффициент; я хочу, чтобы этот коэффициент стал единицей, и домножаю вот на такой. Сперва я увидел, что хочу ровно вот эту сумму, никакую другую, а потом обратил внимание, что эта сумма с точностью до множителя есть значение многочлена вот в такой точке.

— В чём тогда победа FFT над альтернативами, если у нас всё в итоге тоже свелось к перемножению двух многочленов, пусть и в преобразованном виде?

В том, что в преобразованном виде многочлены перемножаются за линейное время: в каждой точке xx я считаю значение за одну операцию. Вот эта стрелочка работает за nlog⁡nn \log n, обратная стрелочка тоже за nlog⁡nn \log n, а вот эта, средняя, — за nn. Профит в этом.

Давайте чуть-чуть поговорим про погрешности. Так же, как и метод Гаусса, всё это считается на вещественных числах, значит, погрешность точно будет. Никаких теоретических оценок, позволяющих сказать «вот это точно работает», я не знаю. Я знаю оценку, когда точно не работает, и эмпирический результат, когда работает. Итак, когда точно не работает? Мы уже знаем, что у произведения двух многочленов коэффициенты будут порядка nn, умноженного на квадрат основания системы счисления. Соответственно, эта величина должна быть не больше того, что вмещает используемый вами тип: double держит примерно 101510^{15}–101610^{16}, long double — примерно 101810^{18}–101910^{19}.

Это теоретическая оценка. Если вы выбрали систему счисления так, что даже это неравенство не выполнено, то вы точно получили переполнение — вам не хватит значащих знаков. Эмпирически мы видим — просто запускаем решение на разных тестах, — что если взять чуть-чуть меньше, буквально на треть разряда меньше, то точности уже хватает. То есть этими формулами можно пользоваться как основой для выбора системы счисления. Если система счисления не подошла и вы поймали WA, можно потом взять основание поменьше: 10k−110^{k-1}.

Теперь вы готовы писать FFT. Отдыхайте, всем приятного.