Алгоритм НОД Лемера

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

Алгоритм

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

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

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

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

  и выполнить алгоритм Евклида одновременно на парах ( x + A , y + C ) и ( x + B , y + D ), пока отношения не станут разными. То есть выполните итерацию как внутренний цикл :

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

  • • Если w ₁ ≠ w ₂ , то выходим из внутренней итерации. В противном случае установите w для значение w ₁ (или w ₂ ).
    • Заменить текущую матрицу

    $\textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}$

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

    $\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}}$

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

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

Ссылки

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