Комментарии 22
Вот всегда когда читаю про подобную математику всплывает мысль, что имелись оптические процессоры осуществлявшие быстрое фурье-преобразование.
Собственно сама идея там весьма проста - транспарант стоит в передней главной плоскости объектива и освещается плоской волной, в фокусе объектива распределение интенсивности излучения является фурье-образом такого распределения на выходе транспаранта. Если ещё фаза важна, то в фокальной плоскости первого объектива ставят второй такой же, и вплотную к нему распределение с корректной фазой. Но физическая реализация этого безобразия обычно несколько монструозна.
проблема с оптическими процессорами пока ещё решается. Сами процессоры сложно конструировать, наличие в линзах примесей сказывается на точности результатов. Буквально на днях была новость про улучшение работы фотонных чипов (src, обзор), которые вроде как научились митигировать эту проблему, но до полноценных вычислительных юнитов кажется довольно далеко.
Собственно, нужно лишь в школьном умножении "столбиком" разглядеть свертку цифр. А там где свертка, то сразу всплывает БПФ
Сейчас много где сталкиваюсь с утверждениями, что операции умножения с точки зрения вычислительной сложности равнозначны операциям сложения, мол они также выполняются за один такт. Но ведь это не совсем так? или поправьте меня!
Интересной особенностью этого преобразования является то, что f=0 строго говоря не является частотой...
... и обычно называется "постоянная смещения", "dc offset".
У этих двух значений не бывает мнимой части
Верно только по отношению к действительным данным, потому что в общем преобразование Фурье определено над комплексными числами.
что можно использовать для оптимизации хранения
От такой оптимизации будет больше неудобств, чем пользы. А вот что действительно можно оптимизировать - так это использовать преобразование Хартли вместо Фурье, которое даёт тот же результат (только слегка в другом виде), считается через действительные числа (для тех кто не хочет связываться с комплексными числами), и занимает в два раза меньше места. Для БПФ конечно тоже есть варианты для преобразования только половины спектра, но алгоритмически они значительно сложнее. Также через один БПФ можно обработать сразу два чисто действительных массива.
Разумеется, эта статья не претендует на глубокое и точное описание всех особенностей БПФ. Это огромная тема, в которой очень многое сделано. Я лишь привёл небольшой обзор основных моментов. Более того, как я показал в конце, для решения задач умножения больших чисел фокусироваться на одном БПФ не стоит.
Что касается хранения данных, то можно вспомнить, что БПФ обладает свойством эрмитовой симметричности. Это значит, что половина результата является комплексно-сопряжённой, а значит её можно не хранить. Хранить нужно (N -2)/2 комплексных чисел, а также два действительных. Если эти два действительных упаковать в одно комплексное, то получится N/2 пар, или же всего N чисел. Это очень удобно — у нас на входе N чисел и на выходе N чисел. Преобразование можно делать прямо в том же куске памяти, что даёт дополнительное ускорение из-за использования кеша процессора.
Иными словами, цифры являются коэффициентами многочлена
Тут можно добавить, что выражение как конечного, так и бесконечного набора чисел как коэффициентов многочлена - это очень мощный инструмент, а котором в школе даже не упоминают. Здесь важно понимать, что в 
не надо ничего подставлять, он имеет тот же смысл, что и мнимая единица.
Преобразование Фурье, как и другие преобразования (Хартли и т.д.), используют свойства суммы ряда циклической группы, в частности с домножением на коэффициенты. Выгода от использования подобных преобразований появляется именно из-за свойств используемой группы.
Другое дело, как показать эту выгоду без привлечения подобных преобразований. Сейчас быстрое умножение выглядит как некая магия, считаем по каким-то формулам, и почему-то получается быстрее. Почему? Потому что так получается по формулам. А почему так получается по формулам?
Поэтому математику ещё ждёт открытие свойств циклических групп, более наглядно объясняющих, что же там за занавеской из формул на самом-то деле происходит.
Для меня лично демонстрация быстрого умножения через китайскую теорему об остатках оказалась весьма наглядной и убедительной. На каждом шаге длина многочлена увеличивается в два раза. Тут становится совершенно понятно, почему оказывается быстро, и откуда берётся логарифм.
БПФ получилось без китайской теоремы об остатках. И вывод быстрого умножения так же возможен без её привлечения. Хотя, возможно, вам известен вывод БПФ через упомянутую теорему?
И про увеличение длины на каждом шаге не понял. При одном умножении степень многочлена увеличивается на единицу. Какая длина при этом увеличивается вдвое?
Описание использования китайской теоремы в статье так же не дошло до моего мозга. Pn = P mod (многочлен) - здесь два неизвестных, Pn и P, многочлен известен, но получение Pn и P непонятно.
Более того, вы далее описываете способ подбора точек так, что бы они образовали мультипликативную группу. Затем эту группу вы находите в преобразовании Фурье. После чего переходите к рассуждениям о совпадении с Фурье лишь при конкретных значениях. Где здесь связь с шагами, которые дают нам степени двойки на каждом из них?
А китайская теорема всего лишь указывает нам на произведение модулей. Но вот свойства мультипликативной группы как раз и позволяют нам комбинировать и заменять отдельные составляющие в квадратичном по сложности алгоритме, сводя их к линейной сложности с логарифмом за счёт рекурсивного использования.
Может стоит добавить подробностей в статью?
Подробности довольно громоздки, их можно найти в моём трактате, на который я дал ссылку в конце. И я спрятал вычисления с китайской теоремой под спойлер.
Идея в том, что если у нас есть значения многочлена в двух точках, допустим 4 и 5: P(4) = 3500, P(5) = 7667, то мы можем с помощью китайской теоремы об остатках (КТО) восстановить многочлен P(x) mod (x - 4)(x - 5).
P(x) mod (x - 4)(x - 5) = 3500(-1)(x - 5) + 7667(x - 4) = 4167x - 13168
Легко проверить, что многочлен 4167x - 13168 принимает значения 3500 и 7667 в точках 4 и 5. То же самое для точек 2 и 3.
P(x) mod (x - 2)(x - 3) = 937x - 1458
Теперь у нас два многочлена 4167x - 13168 и 937x - 1458. Мы можем восстановить с помощью КТО многочлен третьей степени:
P(x) mod (x - 2)(x - 3)(x - 4)(x - 5) = 135x^3 - 610x^2 + 1422x - 1068
На каждом таком шаге длина многочлена увеличивается в два раза, пока степень не сравняется со степенью результата. И это получается быстрое умножение в натуральных точках, без использования комплексных чисел.
С корнями из единицы этот алгоритм становится чуть быстрее. Обратные многочлены для (x^n ± r) оказываются равны ±1/(2r), и применение КТО превращается в (a + b)/2 + (a - b)/(2r) x^n. Что идентично БПФ.
Спасибо, стало понятнее, что читателю необходимо хорошо помнить детали работы с КТО, которые есть в той же википедии по вашей ссылке, но для понимания текста они заранее должны быть в голове, либо их нужно туда положить, перейдя в википедию во время чтения и усвоив там с пару страниц формул, а потом уже снова переключиться на статью.
Но вы бы сэкономили читателю это время, указав промежуточные шаги вычисления, благо они довольно простые, хотя и занимают место. Ссылка на документ в dropbox предполагает именно отсутствие экономии времени, точнее даже гораздо большие затраты на дополнительную информацию.
Хотя возможность ответа в комментариях, в общем-то, проблему нивелирует.
Ну и до кучи, просто добавив в ваш комментарий указание "как видно из примера, перебирая точки, получаем на одно умножение полином первой степени, на три - третьей, на шесть - шестой, то есть степень полинома (или разрядность числа) растёт пропорционально количеству умножений, а не его квадрату" ваши затраты выросли бы очень незначительно, но ясность изложения была бы заметно улучшена.
Хотя я понимаю, что краткость изложения в привычном математикам стиле требует ещё большего сокращения объёма статьи. Но вы же пишете на популярном ресурсе, что предполагает несколько другую аудиторию.
Я побоялся, что если начну спамить формулами, то потеряю читателя. Поэтому спрятал все промежуточные вычисления под спойлер. Кто хочет, может заглянуть. Но если вы не знакомы с внутренней логикой работы КТО, вам будет трудно понять, откуда берутся промежуточные многочлены. Всё-таки, обратный по модулю многочлен — это довольно хардкорная вещь.
Поэтому я просто сразу привёл результат. В конце концов, основная моя мысль состоит в том, что быстрое умножение — это алгебраический алгоритм, основанный на многочленах и КТО. А то, что он иногда совпадает с БПФ — это почти случайность.
И да, технически, я вывожу БПФ из КТО.
Из представления 1.1:
у каждого возможного значения коэффициента есть свой символ, называемый «цифрой»
целые числа образуют кольцо
тогда целое число - это многочлен по основанию 10 над полем рациональных?
Статья хорошая, но Эйлера я бы постеснялся считать российским математиком, пусть он в России и жил некоторое время. Но, видимо, это дань духу времени.
И жил он в России, и похоронен в России, и его потомки лет сто рулили Российской академией наук, и в конце концов их признали дворянским родом Российской Империи.
https://ru.wikipedia.org/wiki/Эйлеры
Я бы сказал, что очень странно не считать Эйлера российским математиком.
Большие простые числа: преобразование Фурье