Рассмотрим следующую задачу: «Дано {{Задача|definition = Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>, состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю <tex>2</tex>.»}}</noinclude><includeonly>{{#if: {{{neat|}}}|<div style="background-color: #fcfcfc; float:left;"><div style="background-color: #ddd;">'''Задача:'''</div><div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div></div>|<table border="0" width="100%"><tr><td style="background-color: #ddd">'''Задача:'''</td></tr><tr><td style="border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr></table>}}</includeonly>
== Простое решение ==
Если мы будем считать произведение матриц <tex>C = A \cdot B</tex> по определению(<tex dpi=140130>\left(c_{i, j} = \sum\limits_{k = 1}^n a_{i,k}b_{k,j}\right)</tex>), то трудоёмкость сложность работы алгоритма составит <tex>O(n^3)</tex> {{---}} каждый из <tex>n^2</tex> элементов результирующей матрицы <tex>C</tex> вычисляется за время, пропорциональное <tex>n</tex>.
Сейчас будет показано, как немного уменьшить это время.
Аналогично поступим с матрицей <tex>B</tex>, вместо строк деля столбцы. Получим матрицу <tex dpi=140>B'_{\lceil\frac nk\rceil\times n}</tex>.
Теперь, если вместо произведения матриц <tex>A</tex> и <tex>B</tex> считать произведение новых матриц <tex>A'</tex> и <tex>B'</tex>, воспользовавшись посчитанными скалярными произведениями, то каждый элемент матрицы <tex>C</tex> будет получаться уже за время, пропорциональное <tex>\lceil \frac nk dfrac{n}{k} \rceil</tex> вместо <tex>n</tex>, и время произведения матриц сократится с <tex>O(n^3)</tex> до <tex dpi=140>O(n^2 \cdot\frac dfrac nk) = O(\fracdfrac{n^3}{k}) </tex>.
== Оценка трудоёмкости сложности алгоритма и выбор k ==[[Файл:exampleFourRussiansAlgoFinalPicture.png|500px|right]]
Оценим трудоёмкость асимптотику данного алгоритма.
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>.* Перемножение полученных матриц {{---}} <tex dpi>O(\dfrac{n^3}{k})</tex>. Итого: <tex>O(2^{2k}k) + O(\dfrac{n^3}{k})</tex>.Выбрав <tex>k =140\log n </tex>, получаем требуемую асимптотику <tex>O(n^2 \log n) + O(\dfrac{n^3}{\log n}) = O(\fracdfrac{n^3}{k\log n})</tex> == Пример работы алгоритма == Рассмотрим работу алгоритма на примере перемножения двух матриц <tex> A </tex> и <tex> B </tex>, где
Итого: <tex>OA = </tex><tex>\left(2^\begin{2karray}k) + O(\frac{n^3cccc} 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{karray}\right)</tex>.Приведем анализ выбора числа , <tex>kB = </tex><tex>\left(\begin{array}{cccc} 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array}\right)</tex> для получения оптимальной сложности алгоритма.
В силу возрастания функции <tex>f(k) = 2^{2k}k</tex> и убывания функции <tex>g(k) \log_2 n = \frac{n^3}{k}log_2 4 = 2</tex> имеем, что сложность будет оптимальна при таком значении <tex>k</tex>, что <tex>f(k) = g(k)</tex>. Прологарифмируем обе части этого равенствато предподсчитаем все скалярные произведения:
Для удобства каждому битовому вектору будет соответствовать двоичное число с ведущими нулями, т.е. в данном случае имеем числа <tex>k \ln 4 + \ln k= 3 \ln n - \ln k00 </tex>, <tex> 01 </tex>, <tex> 10 </tex>, <tex> 11 </tex>. Ниже приведена таблица, в которой записаны все искомые произведения:
<tex>k = \fracbegin{3 array}{|c|c|c|c|c|} \hline & \textbf{00} & \textbf{01} & \textbf{10} & \textbf{11} \\ \hline \textbf{00} & 0 & 0 & 0 & 0 \\ \hline \textbf{01} & 0 & 1 & 0 & 1 \\ \ln n - 2 hline \ln ktextbf{10}& 0 & 0 & 1 & 1 \\ \hline \textbf{11} & 0 & 1 & 1 & 0\ln 4\ \hline \end{array} </tex>
Согласно соглашению относительно битовых векторов и двоичных чисел получим новые матрицы <tex> k = 3 \log_4 n - 2 \log_4 k A' </tex>и <tex> B' </tex>:
В силу того, что <tex> \log_4 k A' = </tex> пренебрежительно мал по сравнению с <tex> k \left(\begin{array}{cccc} 01 & 11 \\ 01 & 00 \\ 11 & 01 \\ 10 & 01 \end{array}\right)</tex> имеем, что <tex> k B' = </tex> с точностью до константы равен <tex> \left(\begin{array}{cccc} 10 & 00 & 01 & 11 \\ 10 & 01 & 10 & 01 \end{array}\log n right)</tex>
Таким образом, при подстановке <tex>k = \log n</tex>, получаем итоговую трудоёмкость <tex dpi=140>O(n^2 \log n) + O(\frac{n^3}{\log n}) = O(\frac{n^3}{\log n})</tex>== Код алгоритма ==<code>Перемножим эти матрицы по модулю два с использованием нашего предпосчета:
/<tex> C = A' \times B' = </ Предподсчёт скалярных произведенийtex> // Пусть precalc[i][j] - "скалярное произведение для битовых представлений" чисел i и j<tex> int k = ceil\left(log n); //округление вверх\begin{array}{cccc} for i := 0 to ( 1 << k) - & 1 for j := & 0 & 0 to (1 << k) - 1 {\\ int scalmul = 0; for pos := & 0 to k - & 1 & 1\\ if ((( 1 << pos) & i) != 0 1 && ((1 << pos) & j) != 0) { scalmul = (scalmul + 1) % 2; } precalc[i][j] = scalmul; } // Создание сжатых матриц\\ for I = 0 to n - 1 { для всех стартовых позиций start группы из k элементов { Представляем текущую двоичную последовательность в текущей строке I матрицы A как десятичное число. Записываем полученное значение в A'. } } for J = 0 to n - & 1 { для всех стартовых позиций start группы из k элементов { Представляем текущую двоичную последовательность в текущем столбце J матрицы B как десятичное число. Записываем полученное значение в B'. } } //Перемножение полученных матриц for i := & 0 to n - 1 for j := 0 to n - 1 { int curans = & 0; for pos := 0 to m - 1 \end{ curans = (curans + precalc[anew[i][pos]][bnew[pos][j]]array}\right) % 2; } ans[i][j] = curans; }</tex>
Матрица <tex> C </tex> {{---}} искомая.
</code>== Литература Источники информации ==* ''Gregory V. Bard'' — '''Accelerating Cryptanalysis with the Method of Four Russians'''. July 22, 2006. Страница 5
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
[[Категория: Способы оптимизации методов динамического программирования]]
