Редактирование: Метод четырёх русских для умножения матриц

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
−
{{Задача
+
Рассмотрим следующую задачу: «Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,  
−
|definition = Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,  
+
состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю <tex>2</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=130>\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>C = A \cdot B</tex> по определению(<tex dpi=140>c_{i, j} = \sum\limits_{k = 1}^n a_{i,k}b_{k,j}</tex>), то трудоёмкость алгоритма составит <tex>O(n^3)</tex> {{---}} каждый из <tex>n^2</tex> элементов результирующей матрицы <tex>C</tex> вычисляется за время, пропорциональное <tex>n</tex>.
  
 
Сейчас будет показано, как немного уменьшить это время.
 
Сейчас будет показано, как немного уменьшить это время.
Строка 28: Строка 16:
 
Аналогично поступим с матрицей <tex>B</tex>, вместо строк деля столбцы. Получим матрицу <tex dpi=140>B'_{\lceil\frac nk\rceil\times 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 \dfrac{n}{k} \rceil</tex> вместо <tex>n</tex>, и время произведения матриц сократится с <tex>O(n^3)</tex> до <tex>O(n^2 \cdot\dfrac nk) = O(\dfrac{n^3}{k}) </tex>.
+
Теперь, если вместо произведения матриц <tex>A</tex> и <tex>B</tex> считать произведение новых матриц <tex>A'</tex> и <tex>B'</tex>, воспользовавшись посчитанными скалярными произведениями, то каждый элемент матрицы <tex>C</tex> будет получаться уже за время, пропорциональное <tex>\lceil \frac nk \rceil</tex> вместо <tex>n</tex>, и время произведения матриц сократится с <tex>O(n^3)</tex> до <tex dpi=140>O(n^2 \cdot\frac nk) = O(\frac{n^3}{k}) </tex>.
  
−
== Оценка сложности алгоритма и выбор k ==
+
== Оценка трудоёмкости и выбор k ==
−
[[Файл:exampleFourRussiansAlgoFinalPicture.png|500px|right]]
 
  
−
Оценим асимптотику данного алгоритма.
+
Оценим трудоёмкость данного алгоритма.
  
 
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
 
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
−
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>.
+
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>
−
* Перемножение полученных матриц {{---}} <tex>O(\dfrac{n^3}{k})</tex>.
+
* Перемножение полученных матриц {{---}} <tex dpi=140>O(\frac{n^3}{k})</tex>
−
 
 
−
Итого: <tex>O(2^{2k}k) + O(\dfrac{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>
+
Итого: <tex>O(2^{2k}k) + O(\frac{n^3}{k})</tex>.
−
<tex>
+
Приведем анализ выбора числа <tex>k</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>f(k) = 2^{2k}k</tex> и убывания функции <tex>g(k) = \frac{n^3}{k}</tex> имеем, что сложность будет оптимальна при таком значении <tex>k</tex>, что <tex>f(k) = g(k)</tex>. Прологарифмируем обе части этого равенства:
  
−
Для удобства каждому битовому вектору будет соответствовать двоичное число с ведущими нулями, т.е. в данном случае имеем числа <tex> 00 </tex>, <tex> 01 </tex>, <tex> 10 </tex>, <tex> 11 </tex>. Ниже приведена таблица, в которой записаны все искомые произведения:
+
<tex>k \ln 4 + \ln k= 3 \ln n - \ln k</tex>
  
−
<tex>
+
<tex>k = \frac{3 \ln n - 2 \ln k}{\ln 4} </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> k  = 3 \log_4 n - 2 \log_4 k </tex>
  
−
<tex> A' = </tex>
+
В силу того, что <tex> \log_4 k </tex> пренебрежительно мал по сравнению с <tex> k </tex> имеем, что <tex> k </tex> с точностью до константы равен <tex> \log n </tex>
−
<tex>
 
−
\left(\begin{array}{cccc} 
 
−
          01 & 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 & 01
 
−
        \end{array}\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>
+
  // Предподсчёт скалярных произведений
−
<tex>
+
  // Пусть precalc[i][j] - "скалярное произведение для битовых представлений" чисел i и j
−
\left(\begin{array}{cccc} 
+
  // "&" - битовый and; "<<" - битовый сдвиг влево.
−
          1 & 1 & 0 & 0 \\  
+
  int k = ceil(log n); //округление вверх
−
          0 & 0 & 1 & 1 \\ 
+
  for i := 0 to (1 << k) - 1
−
          1 & 1 & 1 & 1 \\ 
+
      for j := 0 to (1 << k) - 1 {
−
          1 & 1 & 0 & 0  
+
        int scalmul = 0;
−
        \end{array}\right)
+
        for pos := 0 to k - 1
−
</tex>
+
            if (((1 << pos) & i) != 0 and ((1 << pos) & j) != 0) {  
 +
              scalmul = (scalmul + 1) mod 2;
 +
            }
 +
        precalc[i][j] = scalmul;
 +
      }
 +
 
 +
  // Создание сжатых матриц anew, bnew
 +
  for i := 0 to n - 1 {
 +
      while (start < n) {
 +
        int cursuma = 0, cursumb = 0, curpos = start, deg = (1 << (k - 1));
 +
        while (curpos < start + k and curpos < n) {
 +
            cursuma += a[i][curpos] * deg;
 +
            cursumb += b[curpos][i] * deg;
 +
            deg /= 2;
 +
            curpos++;
 +
        }
 +
        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 + precalc[anew[i][pos]][bnew[pos][j]]) % 2;
 +
        }
 +
        ans[i][j] = curans;
 +
  }
  
−
Матрица <tex> C </tex> {{---}} искомая.
 
  
−
== Источники информации ==
+
</code>
−
* ''Gregory V. Bard'' — ''Accelerating Cryptanalysis with the Method of Four Russians''. July 22, 2006. Страница 5
+
== Литература ==
 +
* ''Gregory V. Bard'' — '''Accelerating Cryptanalysis with the Method of Four Russians'''
  
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Динамическое программирование]]
 
[[Категория: Динамическое программирование]]
−
[[Категория: Способы оптимизации методов динамического программирования]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице:

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Метод_четырёх_русских_для_умножения_матриц»