Изменения

Сейчас будет показано, как немного уменьшить это время.

== Сжатие матриц ==

Возьмём первую матрицу. разделим каждую её строку на куски размера <tex>k</tex>. Для каждого куска определим номер двоичного вектора, который соответствует числам, находящимся на этом куске. Если кусок получился неравным по длине <tex>k</tex>(последний кусок строки), то будем считать, что в конце в нём идут не влияющие на умножение нули. Получим матрицу <tex dpi=140>A'_{n \times \lceil\frac{n}{k} \rceil}</tex>.

* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.

* Перемножение полученных матриц {{---}} <tex dpi=140>O(\frac{n^3}{k})</tex>