Изменения

{{Задача|definition = Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,

Если мы будем считать произведение матриц <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>.

* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>.* Перемножение полученных матриц {{---}} <tex dpi=140>O(\fracdfrac{n^3}{k})</tex>.

Итого: <tex>O(2^{2k}k) + O(\fracdfrac{n^3}{k})</tex>.Выбрав <tex>k = \log n </tex>, получаем требуемую асимптотику <tex>O(n^2 \log n) + O(\dfrac{n^3}{\log n}) = O(\dfrac{n^3}{\log n})</tex>

== Код Рассмотрим работу алгоритма на примере перемножения двух матриц <tex> A </tex> и <tex> B </tex>, где  <tex> A ==</tex><codetex> // Чтение матриц\left(\begin{array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ for i := 1 & 1 & 0 to n - & 1\\ for j := 1 & 0 & 0 to n - & 1 \end{array}\right) read(cur);</tex> a[i][j] , <tex> B = cur;</tex> <tex>\left(\begin{array} {cccc} for i := 1 & 0 & 0 to n - & 1\\ for j := 0 & 0 to n - & 1 & 1 {\\ read(cur); 1 & 0 & 1 & 0 \\ b[i][j] = cur; 0 & 1 & 0 & 1 \end{array} \right)</tex> <tex> k = \log_2 n = \log_2 4 = 2<// Предподсчёт скалярных произведенийtex>, то предподсчитаем все скалярные произведения:  Для удобства каждому битовому вектору будет соответствовать двоичное число с ведущими нулями, т.е. в данном случае имеем числа <tex> 00 </tex>, <tex> 01 </ Пусть preСalc[i][j] - "скалярное произведение для битовых представлений" чисел i и j tex>, <tex> 10 </tex>, <tex> 11 </ "&" - битовый and; "**" - возведение tex>. Ниже приведена таблица, в степень.которой записаны все искомые произведения: <tex> int k = ceil(log2(n)); //округление вверх\begin{array}{|c|c|c|c|c|} for i := 0 to (2 ** k) - 1 \hline for j := 0 to (2 ** k) - 1 & \textbf{00} & \textbf{01} & \textbf{10} & \textbf{11} \\ int scalMul = \hline \textbf{00} & 0 & 0 & 0 & 0; \\ for pos := \hline \textbf{01} & 0 & 1 & 0 to k - & 1\\ if (((2 ** pos) \hline \textbf{10} & i) != 0 and ((2 ** pos) & j) != 0) { & 1 & 1 \\ scalMul = (scalMul + 1) mod 2; \hline \textbf{11}& 0 & 1 & 1 & 0\\ preСalc[i][j] = scalMul;\hline \end{array} </tex>  Согласно соглашению относительно битовых векторов и двоичных чисел получим новые матрицы <tex> A' </tex> и <tex> B' </ Создание сжатых матриц anew, bnewtex>:  for i :<tex> A' = 0 to n - 1 {</tex> while (start < n) {tex> int curSumA = 0, curSumB = 0, curPos = start, deg = \left(2 ** (k - 1)); while (curPos < start + k and curPos < n) \begin{array}{cccc} curSumA = curSumA + a[i][curPos] * deg; 01 & 11 \\ curSumB = curSumB + b[curPos][i] * deg; 01 & 00 \\ deg = deg div 2; 11 & 01 \\ curPos = curPos + 1; 10 & 01 \end{array}\right) anew[i][start div k] = curSumA;</tex>, bnew[start div k][i] <tex> B' = curSumB;</tex> start = start + k;<tex> \left(\begin{array}{cccc} 10 & 00 & 01 & 11 \\ 10 & 01 & 10 & 01 \end{array}\right) </tex> //Перемножение полученных матриц for i Перемножим эти матрицы по модулю два с использованием нашего предпосчета:= 0 to n - 1 for j :<tex> C = 0 to n - 1 { int curAns A' \times B' = 0;</tex> for pos := 0 to m - 1 {<tex> curAns = \left(curAns + preСalc[anew[i][pos]][bnew[pos][j]]) mod 2; \begin{array} ans[i][j] = curAns; {cccc} 1 & 1 & 0 & 0 \\ // Вывод ответа 0 & 0 & 1 & 1 \\ for i := 0 to n - 1 & 1 & 1 & 1\\ for j := 1 & 1 & 0 & 0 to n - 1 \end{ write(ans[i][j]array}\right); }</tex> writeln(); Матрица <tex> C </tex> {{---}}искомая.

</code>== Литература Источники информации ==* ''Gregory V. Bard'' — '''Accelerating Cryptanalysis with the Method of Four Russians'''. July 22, 2006. Страница 5