Войти  |  Регистрация
Авторизация

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



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

Алгоритм

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

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

  • Если 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 матрицу
    [ A B x C D y ] {displaystyle extstyle {egin{bmatrix}A&B&xC&D&yend{bmatrix}}} к расширенной единичной матрице [ 1 0 x 0 1 y ] , {displaystyle extstyle {egin{bmatrix}1&0&x&1&yend{bmatrix}},} и выполнить алгоритм Евклида одновременно на парах (x + A, y + C) и (x + B, y + D),
    • Вычислить коэффициенты w1 длинных делений (x + A) на (y + C) и w2 (x + B) на (y + D) соответственно. Также пусть w будет (не вычисленным) частным от текущего длинного деления в цепочке длинных делений алгоритма Евклида.
      • Заменить текущую матрицу
      [ A B x C D y ] {displaystyle extstyle {egin{bmatrix}A&B&xC&D&yend{bmatrix}}} матричным произведением [ 0 1 1 − w ] ⋅ [ A B x C D y ] = [ C D y A − w C B − w D x − w y ] {displaystyle extstyle {egin{bmatrix}0&11&-wend{bmatrix}}cdot {egin{bmatrix}A&B&xC&D&yend{bmatrix}}={egin{bmatrix}C&D&yA-wC&B-wD&x-wyend{bmatrix}}} согласно матричной формулировке расширенного алгоритма Евклида.
      • Если B ≠ 0, перейти к началу внутреннего цикла.
    • Если B = 0, мы достигли «тупика»; выполните нормальный шаг алгоритма Евклида с помощью a и b и перезапустите внешний цикл.
    • Установите a в aA + bB и b в Ca + Db (снова одновременно). Это применяет шаги евклидова алгоритма, которые были выполнены с начальными цифрами в сжатой форме, к длинным целым числам a и b. Если b ≠ 0, переходите к началу внешнего цикла.

Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent