|
Алгоритм ФюрераАлгоритм Фюрера (англ. Fürer's algorithm), быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером изуниверситета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его предшественник, алгоритм Шёнхаге — Штрассена, опубликованный в 1971 году. Задача быстрого умножения больших чисел представляет большой интерес в области критоанализа открытых систем. Предшественник А.Ф., алгоритм Шёнхаге — Штрассена, использовал быстрое преобразование Фурье для умножения больших чисел за время O(n log n log log n), однако его авторы, Арнольд Шёнхаге (англ. Arnold Schönhage) и Велкель Штрассен (англ. Volker Strassen), сделали предположение о существовании алгоритма, способного решить проблему перемножения больших чисел за O(n log n). А.Ф. заполнил промежуток между этими границами: он может быть использован, чтобы перемножить числа за время , где log * n - итерированный логарифм числа n. Однако разница по времени между алгоритмами становится заметной при очень больших перемножаемых числах (больше 50 000 значащих цифр). В 2008 году Аниндая Де, Шэнден Саха, Пьюш Курур и Рампрасад Саптхариши построили похожий алгоритм, основанный на модульной, а не комплексной арифметике, достигнув при этом такого же времени работы. Допустим, что мы перемножаем числа 123 и 456 в "столбик", однако без выполнения переноса. Результат будет выглядеть так:
Эта последовательность (4, 13, 28, 27, 18) называется ациклической или линейной свёрткой от последовательностей (1,2,3) и (4,5,6). Зная ациклическую свертку двух последовательностей, расчитать произведение несложно: достаточно выполнить перенос (например, в самом правом столбце, мы оставляем 8 и добавляем 1 к столбцу, содержащему 27). В нашем примере это приводит к результату 56088. Есть и другие типы сверток, которые могут быть полезны. Допустим, что входящие последовательности сожержат n элементов (в примере - 3). Тогда результирующая линейная свертка содержит n+n−1 элементов; если мы возьмём самый правый стобец n элементов и добавим самый левый стоблей n−1 ', в результате мы получим циклическую свертку:
Если мы произведём перенос при циклической свертывании, результат будет тот же, что и при произведении чиселe по модулю Bn − 1. В данном примере, 103 − 1 = 999, выполним перенос по (28, 31, 31) и получим 3141, при этом 3141 ≡ 56088 (mod 999). Наоборот, если мы возьмём самый правый столбец n элементов и вычтем самый левый стобец n−1 элементов, то в результате мы получим обратную свертку:
Если мы произведём перенос при обратном свертывании, то результат будет тот же, что и при произведении чисел по модулю Bn + 1. В данном примере, 103 + 1 = 1001, выполним перенос по (28, 23, 5) и получим 3035, при этом 3035 ≡ 56088 (mod 1001). Обратно свертка может содержать отрицательные числа, которые могут быть убраны во время переноса, используя ту же технику, что и при длинных вычитаниях. Как и другие методы, основанные на быстром преобразовании Фурье, алгоритм Фюрера в корне зависит от теоремы о свертке, которая обеспечивает эффективный способ посчитать циклическую свертку двух последовательностей. Её идея состоит в следующем: Циклическая свертка двух векторов может быть найдена через дискретное преобразование Фурье (ДПФ) каждого из них, путём произведения результирующих векторов элемент за элементом, с последующим обратным преобразованием Фурье (ОДПФ). Или через формулы: CyclicConvolution(X, Y) = IDFT(DFT(X) · DFT(Y)), где: CyclicConvolution - циклическая сертка, DFT - дискретное преобразование Фурье, IDFT - обратное дискретное преобразование Фурье. Если мы посчитаем ДПФ и ОДПФ используя быстрое преобразование Фурье и вызовем наш алгоритм перемножения рекурсивно, чтобы перемножить входы(?) преобразованных векторов DFT(X) и DFT(Y), то в результате мы получим эффективный алгоритм для расчёта циклической свёртки. В этом алгоритме, гораздо эффективней считать обратную циклическую свертку; как оказывается, немного модифицированная версия теоремы о свертке может позволить и это. Предположим, что вектора X и Y имеют длину n, и a примитивный корень порядка 2n (это означает, что a2n = 1 и все меньшие степени a не равны 1). Таким образом мы можем определить третий вектор A, называемый вектор веса, обладающий следующими свойствами: A = (aj), 0 ≤ j < n A−1 = (a−j), 0 ≤ j < n Теперь мы можем записать: NegacyclicConvolution(X, Y) = A−1 · IDFT(DFT(A · X) · DFT(A · Y)), где NegacyclicConvolution - Обратная циклическая сертка, DFT - дискретное преобразование Фурье, IDFT - обратное дискретное преобразование Фурье. Другими словами, это то же самое за исключением того, что входящие векторы умножены на A, а результат умножен на A−1. Операция "бабочка" Дискретное преобразование Фурье - абстрактная операция, которая может быть выполнена в любом алгебраическом кольце; обычно оно берётся из поля комплексных чисел, но фактически использовать комплексную арифметику с достаточной точностью, чтобы обеспечить точные результаты медленно и неэффективно. Вместо этого мы можем использовать теоретико-числовое преобразование, которое производит преобразование в поле целых чисел по модулю N для некоторого целого N. Так же как есть примитивные корни единицы любого порядка на комплексной плоскости, при любом заданном n мы можем выбрать подходящее N такое, что b - примитивный корень единицы порядка n в поле целых чисел по модулю N (другими словами, bn ≡ 1 (mod N), и все меньшие степени bне равны 1 mod N). Алгоритм тратит большую часть времени на рекурсивное выполнение произведения меньших чисел; в простом варианте алгоритма это происходит в ряде мест:
Ключевой момент - выбрать N, модуль, равный 2n + 1 для некоторого целого n. У этого способа есть ряд преимуществ в ряде стандартных систем, в которых большие челые числа представлены в двоичном виде:
Главное отличие от предшественника - многократное выполнение компрессии числа, которое даёт вычилительную сложность в отличие от однократного использования в алгоритме Шёнхаге — Штрассена, которое даёт сложность nlog nlog log n Произведение целых чисел Произведение целых чисел по модулю Разложение БПФ Покомпонентное произведение Обратное БПФ Композиция результата |
Loading
|