Метод умножения Шёнхаге — Штрассена - История изменений

Turbo в 10:35, 21 апреля 2014

2014-04-21T10:35:47Z

Turbo в 13:14, 19 августа 2013

2013-08-19T13:14:55Z

Turbo в 13:14, 19 августа 2013

2013-08-19T13:14:31Z

Turbo в 05:50, 29 июля 2013

2013-07-29T05:50:32Z

Turbo в 05:29, 29 июля 2013

2013-07-29T05:29:57Z

Turbo в 05:20, 29 июля 2013

2013-07-29T05:20:43Z

Turbo в 14:27, 24 июля 2013

2013-07-24T14:27:06Z

Turbo: Новая страница: «[http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm Основные подробности] === Пример === Положим задано…»

2013-07-24T14:23:14Z

Новая страница: «[http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm Основные подробности] === Пример === Положим задано…»

Новая страница

[http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm Основные подробности]

=== Пример ===
Положим задано два числа: X и Y, каждое длиной 512 бит. Требуется найти значение RES = (X*Y) mod 2N+1
# Этап 1: len1 = 512, len2 = 512, N = 1024, 2k ~ sqrt(N) = 32, k = 5, n >= 2*N/2k+k = (2048/32)+5 = 69. Поскольку n должно делиться на 2k, то можно выбрать n = 128.
# Этап 2 (возникает на умножении DFT(X)*DFT(Y) mod 2128+1): len1 = 129, len2 = 129, N = 128, 2k ~ (sqrt(N) = 11.3). Выберем k = 4. n >= 2*N/2k+k = (256/16)+4 = 20. Поскольку n должно делиться на 2k, то можно выбрать n = 32.
# Этап 3 (возникает на умножении DFT(X)*DFT(Y) mod 232+1): это умножение можно делать аппаратно, не углубляюсь в рекурсию.

@@ Строка 1: / Строка 1: @@
-[http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm Основные подробности]
+'''Алгоритм Шёнхаге - Штрассена''' - асимптотически быстрый алгоритм умножения больших чисел. Он был разработан Арнольдом Шёнхаге и Фолькером Штрассеном в 1971. Сложность алгоритма в нотации "О - большого" составляет O(''N''&nbsp;log&nbsp;''N''&nbsp;log&nbsp;log&nbsp;''N''). Алгоритм
 == Теория ==
 === Свертка ===
@@ Строка 26: / Строка 35: @@
 Эта последовательность (4, 13, 28, 27, 18) называется ''ациклической'' или ''линейной свёрткой'' от последовательностей (1,2,3) и (4,5,6). Зная ациклическую свёртку двух последовательностей, рассчитать произведение несложно: достаточно выполнить перенос (например, в самом правом столбце, мы оставляем 8 и добавляем 1 к столбцу, содержащему 27). В нашем примере это приводит к результату 56088.
-Есть и другие типы свёрток, которые могут быть полезны. Допустим, что входящие последовательности содержат ''n'' элементов (в примере — 3). Тогда результирующая линейная свёртка содержит ''n'' + ''n'' &minus; 1 элементов; если мы возьмём самый правый столбец ''n'' элементов и добавим самый левый стоблец ''n'' &minus; 1 ', в результате мы получим циклическую свёртку:
+Есть и другие типы свёрток, которые могут быть полезны. Допустим, что входящие последовательности содержат ''n'' элементов (в примере — 3). Тогда результирующая линейная свёртка содержит ''n'' + ''n'' &minus; 1 элементов; если мы возьмём самый правый столбец ''n'' элементов и добавим самый левый столбец ''n'' &minus; 1 ', в результате мы получим циклическую свёртку:
 {|width=300
@@ Строка 56: / Строка 65: @@
 === Теорема о свёртке ===
-Как и другие методы, основанные на быстром преобразовании Фурье, алгоритм Фюрера в корне зависит от теоремы о свёртке, которая обеспечивает эффективный способ посчитать циклическую свёртку двух последовательностей. Её идея состоит в следующем:
+Как и другие методы, основанные на быстром преобразовании Фурье, алгоритм Шёнхаге - Штрассена в корне зависит от теоремы о свёртке, которая обеспечивает эффективный способ посчитать циклическую свёртку двух последовательностей. Её идея состоит в следующем:
 : Циклическая свёртка двух векторов может быть найдена через [[дискретное преобразование Фурье]] (ДПФ) каждого из них, путём произведения результирующих векторов элемент за элементом, с последующим обратным преобразованием Фурье (ОДПФ).
@@ Строка 78: / Строка 87: @@
 : NegacyclicConvolution(''X'', ''Y'') = ''A''<sup>&minus;1</sup> &middot; IDFT(DFT(''A'' &middot; ''X'') &middot; DFT(''A'' &middot; ''Y'')), где
-:: NegacyclicConvolution — ''Обратная циклическая сертка'',
+:: NegacyclicConvolution — ''Обратная циклическая свертка'',
 :: DFT — ''дискретное преобразование Фурье'',
 :: IDFT — ''обратное дискретное преобразование Фурье''.
@@ Строка 104: / Строка 113: @@
 === Пример ===
-Положим задано два числа: X и Y, каждое длиной 512 бит. Требуется найти значение RES = (X*Y) mod 2<sup>N</sup>+1
+Следующий пример иллюстрирует работу алгоритма.
-* Этап 1. Основные параметры алгоритма:
+Положим задано два числа: X и Y, каждое длиной 8 бит. Требуется найти значение RES = (X*Y) mod 2<sup>N</sup>+1
-** len1 = 512
+Возьмём для определённости X = Y = 129<sub>10</sub> = 1000 0001<sub>2</sub>.
-** len2 = 512
+Выберем N = 8 + 8 = 16.
-** N = 1024
+* Этап 1. Разбиение чисел на K = 4 слов длины M = 4 бита:
-** 2<sup>k</sup> ~ sqrt(N) = 32, k = 5
+**Дополним числа нулями до длины N = 16 и разобьём на слова. Получим две последовательности (в данном примере идентичные): {0001, 1000, 0000, 0000}. Или в десятичном виде: {3, 8, 0, 0} (слова расположены в порядке от младших бит к старшим). Все операции далее выполняются по модулю 2<sup>n</sup>+1, где n выбирается из условия n >= 2*M + log2(K) и является степенью двойки, то есть в нашем случае n >= 2*4 + 2 = 10, n = 16.
-** n >= 2*N/2<sup>k</sup>+k = (2048/32)+5 = 69. Поскольку n должно делиться на 2<sup>k</sup>, то можно выбрать n = 128.
-* Этап 2 (возникает на умножении DFT(X)*DFT(Y) mod 2<sup>128</sup>+1):
+* Этап 2. Вычисление свёртки двух последовательностей:
-** len1 = 129
+** Этап 2.1 Умножение последовательностей на весовые коэффициенты. 2K-ый корень из единицы в кольце из 2<sup>n</sup>+1 элементов равен 2<sup>2n/2K</sup> = 2<sup>4</sup> = 16. Результат умножения на вектор весовых коэффициентов в десятичном виде: {1, 128, 0, 0}.
-** len2 = 129
+**Этап 2.2 Прямое преобразование Фурье над кольцом из 2<sup>n</sup> элементов. K-ый корень из единицы в кольце вычетов по модулю 2<sup>n</sup>+1 равен 2<sup>2n/2K</sup> = 2<sup>4</sup> = 256. Формула преобразования: <math>b_i = \sum^{K-1}_{j=0}{a_j\omega^{ij}}</math>, <math> \omega </math> - К-тый корень из единицы в кольце вычетов по модулю 2<sup>n</sup>+1. Результат: {129, 32769, 65410, 32770}.
-** N = 128
+**Этап 2.3 Покомпонентное произведение последовательностей в кольце из 2<sup>n</sup> элементов. Результат: {16641, 49153, 16129, 49155}.
-** 2<sup>k</sup> ~ (sqrt(N) = 11.3). Выберем k = 4.
+**Этап 2.4 Обратное преобразование Фурье над кольцом из 2<sup>n</sup> элементов. Формула обратного преобразования: <math>b_i = \frac {1}{K} \sum^{K-1}_{j=0}{a_j\omega^{ij}}</math>, <math> \frac {1}{K} </math> - обратный к <math>K</math> по модулю 2<sup>n</sup>+1. Результат: {1, 256, 16384, 0}.
-** n >= 2*N/2<sup>k</sup>+k = (256/16)+4 = 20. Поскольку n должно делиться на 2<sup>k</sup>, то можно выбрать n = 32.
+**Этап 2.5 Умножение последовательностей на коэффициенты, обратные к используемым в 2.1. Результат: {1, 16, 64, 0}.
-* Этап 3 (возникает на умножении DFT(X)*DFT(Y) mod 2<sup>32</sup>+1):
+* Этап 3. Выполнение операции переноса. Результат: {1, 0, 1, 4}. В двоичном виде: {0001, 0000, 0001, 0100}
-** len1 = 33
+* Этап 5. "Склейка" полученной последовательности, окончательный результат: 1010000001000<sub>2</sub> = 16641 = 129 * 129.
-** len2 = 33
+* Этап 5. Вычисление остатка по модулю 2<sup>N</sup>+1. В данном случае 16641 = 16641 mod 2<sup>16</sup>+1
-это умножение можно делать аппаратно, не углубляюсь в рекурсию.
 === Описание ===
@@ Строка 129: / Строка 137: @@
 === Исходники ===
 [http://www.ginac.de/CLN/cln.git/?p=cln.git;a=blob;f=src/base/digitseq/cl_DS_mul_fftm.h;h=a984802ce039e8179a26fda2681a2e133dba6fbd;hb=refs/heads/master CLN - Class Library for Numbers]

@@ Строка 1: / Строка 1: @@
 [http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm Основные подробности]
 == Теория ==
@@ Строка 119: / Строка 100: @@
 * Любое число может быть быстро уменьшено по модулю 2<sup>''n''</sup>&nbsp;+&nbsp;1 используя только сдвиг и сложение.
 * Любые примитивные корни единицы в этом кольце могут быть записаны в форме 2<sup>''k''</sup>; соответственно мы можем умножать или делить любое число на корень из единицы используя сдвиг.
-* Поэлементное рекурсивное перемножение преобразованный векторов может быть выполнено, используя обратную свёртку, которая работает быстрее, чем ациклическая свёртка, и в которой уже есть уменьшение результата по модулю 2<sup>''n''</sup>&nbsp;+&nbsp;1.
+* Поэлементное рекурсивное перемножение преобразованный векторов может быть выполнено, используя обратную свёртку, которая работает быстрее, чем ациклическая свёртка, и в которой уже есть уменьшение результата
 === Описание ===

@@ Строка 19: / Строка 19: @@
 ** len2 = 33
 это умножение можно делать аппаратно, не углубляюсь в рекурсию.
 === Описание ===

@@ Строка 21: / Строка 21: @@
 === Описание ===
-[http://gmplib.org/manual/FFT-Multiplication.html#FFT-Multiplication Документация GMP LIB]
+* [http://gmplib.org/manual/FFT-Multiplication.html#FFT-Multiplication Документация GMP LIB]
 === Исходники ===
 [http://www.ginac.de/CLN/cln.git/?p=cln.git;a=blob;f=src/base/digitseq/cl_DS_mul_fftm.h;h=a984802ce039e8179a26fda2681a2e133dba6fbd;hb=refs/heads/master CLN - Class Library for Numbers]

@@ Строка 19: / Строка 19: @@
 ** len2 = 33
 это умножение можно делать аппаратно, не углубляюсь в рекурсию.
 === Исходники ===
 [http://www.ginac.de/CLN/cln.git/?p=cln.git;a=blob;f=src/base/digitseq/cl_DS_mul_fftm.h;h=a984802ce039e8179a26fda2681a2e133dba6fbd;hb=refs/heads/master CLN - Class Library for Numbers]

← Предыдущая		Версия 05:20, 29 июля 2013
Строка 19:		Строка 19:
	** len2 = 33		** len2 = 33
	это умножение можно делать аппаратно, не углубляюсь в рекурсию.		это умножение можно делать аппаратно, не углубляюсь в рекурсию.
		+
		+	=== Исходники ===
		+	[http://www.ginac.de/CLN/cln.git/?p=cln.git;a=blob;f=src/base/digitseq/cl_DS_mul_fftm.h;h=a984802ce039e8179a26fda2681a2e133dba6fbd;hb=refs/heads/master CLN - Class Library for Numbers]