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

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

Скажем, мы хотим получить НОД из двух целых чисел a и b. Пусть a ≥ b. Если b содержит только одну цифру (в выбранной системе счисления, скажем, β = 1000 или β = 232), используйте какой-то другой метод, такой как алгоритм Евклида, чтобы получить результат. Если a и b отличаются по длине цифр, выполните деление так, чтобы a и b были равны по длине с длиной, равной m. Внешний цикл: Итерируйте, пока один из a или b не станет равным нулю: Уменьшить m на единицу. Пусть x будет ведущей (самой значимой) цифрой в a, x = a div β m и y — начальная цифра в b, y = b div βm. Инициализируйте 2 на 3 матрицу к расширенной единичной матрице и выполнить алгоритм Евклида одновременно на парах (x + A, y + C) и (x + B, y + D), Вычислить коэффициенты w1 длинных делений (x + A) на (y + C) и w2 (x + B) на (y + D) соответственно. Также пусть w будет (не вычисленным) частным от текущего длинного деления в цепочке длинных делений алгоритма Евклида. Заменить текущую матрицу

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

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

Примечания

Ссылки Капил Хари Параджапе, Алгоритм Лемера

Категория:Теоретико-числовые алгоритмы