Изменения

{{Задача|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>

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>\begin{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 \\ \hline \textbf{10} & 0 & 0 & 1 & 1 \\ \ hline \textbf{11} & 0 & 1 & 1 & 0 \\ \hline \end{array} </tex> Согласно соглашению относительно битовых векторов и двоичных чисел получим новые матрицы <tex> A' </tex> и <tex> B' </tex>: <tex> A' = </tex><tex>\left(\begin{array}{cccc} 01 & 0 11 \\ 01 & 00 \\ 11 & 01 \\ 10 & 01 \end{array}\right)</tex>,<tex> B' = </tex><tex>\left(\begin{array}{cccc} 10 & 00 & 01 & 11 \\ 10 & 01 & 10 & 1 01

Перемножим эти матрицы по модулю два с использованием нашего предпосчета: <tex> k C = log_2 n A' \times B' = log_2 4 = 2</tex>, то предподсчитаем все скалярные произведения:<tex>\left(\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array}\right)</tex>

== Код алгоритма ==Матрица <codetex> C <// Чтение матриц for i := 0 to n - 1 for j := 0 to n - 1 tex> { read(cur); a[i][j] = cur; } for i := 0 to n - 1 for j := 0 to n - 1 { read(cur); b[i][j] = cur; } // Предподсчёт скалярных произведений // Пусть preСalc[i][j] - "скалярное произведение для битовых представлений" чисел i и j // "&" - битовый and; "**" - возведение в степень. int k = ceil(log2(n)); //округление вверх for i := 0 to (2 ** k) - 1 for j := 0 to (2 ** k) - 1 { int scalMul = 0; for pos := 0 to k - 1 if (((2 ** pos) & i) != 0 and ((2 ** pos) & j) != 0) { scalMul = (scalMul + 1) mod 2; } preСalc[i][j] = scalMul; } // Создание сжатых матриц anew, bnew for i := 0 to n - 1 { while (start < n) { int curSumA = 0, curSumB = 0, curPos = start, deg = (2 ** (k - 1)); while (curPos < start + k and curPos < n) { curSumA = curSumA + a[i][curPos] * deg; curSumB = curSumB + b[curPos][i] * deg; deg = deg div 2; curPos = curPos + 1; } anew[i][start div k] = curSumA; bnew[start div k][i] = curSumB; start = start + k; } } //Перемножение полученных матриц for i := 0 to n - 1 for j := 0 to n - 1 { int curAns = 0; for pos := 0 to m - 1 { curAns = (curAns + preСalc[anew[i][pos]][bnew[pos][j]]) mod 2; } ans[i][j] = curAns; } // Вывод ответа for i := 0 to n - 1 for j := 0 to n - 1 { write(ans[i][j]); } writeln(); }искомая.

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