Русская Википедия:Алгоритм НОД Лемера

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Алгоритм НОД Лемера — названный в честь Деррика Генри Лемера быстрый алгоритм по поиску НОД, является улучшением более простого, но более медленного алгоритма Евклида. Он в основном используется для больших целых чисел, которые имеют представление в виде строки цифр относительно некоторой выбранной основы системы счисления, скажем, β = 1000 или β = 2³².

Алгоритм

Лемер отметил, что большинство частных с каждого шага части деления стандартного алгоритма невелики. (Например, Дональд Кнут заметил, что коэффициенты 1, 2 и 3 составляют 67,7% всех коэффициентов.) Эти небольшие частные могут быть идентифицированы только из нескольких начальных цифр. Таким образом, алгоритм начинается с разделения этих начальных цифр и вычисления последовательности частных, пока это правильно.

Скажем, мы хотим получить НОД из двух целых чисел a и b. Пусть a ≥ b.

• Если b содержит только одну цифру (в выбранной системе счисления, скажем, β = 1000 или β = 2³²), используйте какой-то другой метод, такой как алгоритм Евклида, чтобы получить результат.
• Если a и b отличаются по длине цифр, выполните деление так, чтобы a и b были равны по длине с длиной, равной m.
• Внешний цикл: Итерируйте, пока один из a или b не станет равным нулю:
  • Уменьшить m на единицу. Пусть x будет ведущей (самой значимой) цифрой в a, x = a div β ^m и y — начальная цифра в b, y = b div β^m.
  • Инициализируйте 2 на 3 матрицу

  <math>\textstyle

  \begin{bmatrix} A & B & x\\ C & D & y \end{bmatrix}
 </math> к расширенной единичной матрице <math>\textstyle
   \begin{bmatrix} 1 & 0 & x \\ 0 & 1 & y\end{bmatrix},
 </math>

• и выполнить алгоритм Евклида одновременно на парах (x + A, y + C) и (x + B, y + D),

  • Вычислить коэффициенты w₁ длинных делений (x + A) на (y + C) и w₂ (x + B) на (y + D) соответственно. Также пусть w будет (не вычисленным) частным от текущего длинного деления в цепочке длинных делений алгоритма Евклида.

  • • Заменить текущую матрицу

    <math>\textstyle \begin{bmatrix} A & B & x \\ C & D & y \end{bmatrix}</math>

    матричным произведением

    <math>\textstyle

    \begin{bmatrix} 0 & 1 \\ 1 & -w \end{bmatrix}
    \cdot
    \begin{bmatrix} A & B & x \\ C & D & y \end{bmatrix}
    = \begin{bmatrix} C & D &y \\ A - wC & B - wD & x-wy \end{bmatrix}
 </math>

• • согласно матричной формулировке расширенного алгоритма Евклида.

    • Если B ≠ 0, перейти к началу внутреннего цикла.
  • Если B = 0, мы достигли «тупика»; выполните нормальный шаг алгоритма Евклида с помощью a и b и перезапустите внешний цикл.
  • Установите a в aA + bB и b в Ca + Db (снова одновременно). Это применяет шаги евклидова алгоритма, которые были выполнены с начальными цифрами в сжатой форме, к длинным целым числам a и b. Если b ≠ 0, переходите к началу внешнего цикла.

Ссылки

• Капил Хари Параджапе, Алгоритм Лемера