Изменения

{{Задача|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>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>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> A = </tex><tex>\left(\begin{array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{array}\right)</tex>, <tex> B = </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> k = \log_2 n = \log_2 4 = 2</tex>, то предподсчитаем все скалярные произведения: Для удобства каждому битовому вектору будет соответствовать двоичное число с ведущими нулями, т.е. в данном случае имеем числа <tex> 00 </tex>, <tex> 01 </tex>, <tex> 10 </tex>, <tex> 11 </tex>. Ниже приведена таблица, в которой записаны все искомые произведения:

Итого: <tex>O(2^\begin{array}{|c|c|c|c|c|} \hline & \textbf{00} & \textbf{2k01}k) + O(& \fractextbf{n^310}& \textbf{k11} \\ \hline \textbf{00} & 0 & 0 & 0 & 0 \\ \hline \textbf{01} & 0 & 1 & 0 & 1 \\ \hline \textbf{10} & 0 & 0 & 1 & 1 \\ \hline \textbf{11} & 0 & 1 & 1 & 0\\ \hline \end{array})</tex>.Приведем анализ выбора числа <tex>k</tex> для получения оптимальной сложности алгоритма.

В силу возрастания функции Согласно соглашению относительно битовых векторов и двоичных чисел получим новые матрицы <tex>f(k) = 2^{2k}kA' </tex> и убывания функции <tex>g(k) = \frac{n^3}{k}</tex> имеем, что сложность будет оптимальна при таком значении <tex>k</tex>, что <tex>f(k) = g(k)B' </tex>. Прологарифмируем обе части этого равенства:

<tex>k A' = </tex><tex>\left(\begin{array}{cccc} 01 & 11 \ln 4 + \ln k 01 & 00 \\ 11 & 01 \\ 10 & 01 \end{array}\right)</tex>,<tex> B' = 3 </tex><tex>\left(\begin{array}{cccc} 10 & 00 & 01 & 11 \\ 10 & 01 & 10 & 01 \ln n - end{array}\ln kright)</tex>

<tex> k C = A' \times B' = 3 </tex><tex>\left(\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \log_4 n - 2 end{array}\log_4 k right)</tex>

В силу того, что Матрица <tex> \log_4 k </tex> пренебрежительно мал по сравнению с <tex> k </tex> имеем, что <tex> k </tex> с точностью до константы равен <tex> \log n C </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> int n, cur; vector <vector <int> > a, b, preculc, anew, bnew, ans; int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); cin >> n; a.resize(n); b.resize(n); ans.resize(n); // Чтение матриц for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { cin >> cur; a[i].push_back(cur); } for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { cin >> cur; b[i].push_back(cur); } // Предподсчёт скалярных произведений int k = ceil(log( (double) n)); preculc.resize(1 << k); for (int i = 0; i < (1 << k); i++) for (int j = 0; j < (1 << k); j++) { int scalmul = 0; for (int pos = 0; pos < k; pos++) if (((1 << pos) & i) != 0 && ((1 << pos) & j) != 0) { scalmul = (scalmul + 1) % 2; } preculc[i]* ''Gregory V.push_back(scalmul); } // Создание сжатых матриц int m = ceil(((double) n) / k); anewBard'' — ''Accelerating Cryptanalysis with the Method of Four Russians''.resize(n); bnew.resize(m); for (int i = 0; i < n; i++) { for (int start = 0; start < n; start += k) { int cursuma = 0, cursumb = 0, curpos = startJuly 22, deg = (1 << (k - 1)); while (curpos < start + k && curpos < n) { cursuma += a[i][curpos] * deg; cursumb += b[curpos][i] * deg; deg /= 2; curpos++; } anew[i].push_back(cursuma); bnew[start / k]2006.push_back(cursumb); } } //Перемножение полученных матриц for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { int curans = 0; for (int pos = 0; pos < m; pos++) { curans = (curans + preculc[anew[i][pos]][bnew[pos][j]]) % 2; } ans[i].push_back(curans); } // Вывод ответа for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << ans[i][j] << " "; } cout << endl; } return 0; }</code>== Ссылки ==Страница 5