Lehmers GCD algoritmi - Lehmers GCD algorithm - Wikipedia

Lehmerning GCD algoritminomi bilan nomlangan Derrik Genri Lemmer, ro'za GCD algoritm, soddalashtirilgan, ammo sekinroq yaxshilanish Evklid algoritmi. Bu asosan ba'zi tanlangan raqamlar tizimiga nisbatan raqamlar qatori sifatida ifodalanadigan katta butun sonlar uchun ishlatiladi tayanch, demoq β = 1000 yoki β = 2³².

Algoritm

Lehmer ta'kidlashicha, ularning aksariyati takliflar standart algoritmning bo'linish qismining har bir bosqichidan kichik. (Masalan, Knuth 1, 2 va 3 kvotentsiyalar barcha kvotentsiyalarning 67,7 foizini tashkil etganini kuzatdi.^[1]) Ushbu kichik kotirovkalarni faqat bir nechta etakchi raqamlardan aniqlash mumkin. Shunday qilib, algoritm ushbu etakchi raqamlarni ajratishdan va kvotentlar ketma-ketligini hisoblashdan boshlanadi.

Ikkita butun sonning GCD-ni olishni istaymiz a va b. Ruxsat bering a ≥ b.

• Agar b faqat bitta raqamni o'z ichiga oladi (tanlanganida) tayanch, demoq β = 1000 yoki β = 2³²) kabi boshqa usullardan foydalaning, masalan Evklid algoritmi, natijani olish uchun.
• Agar a va b raqamlar uzunligidan farq qiladi, bo'linishni shunday bajaring a va b uzunligi teng, uzunligi bilan teng m.
• Tashqi tsikl: Bittasiga qadar takrorlang a yoki b nolga teng:
  • Kamaytirish m bittadan. Ruxsat bering x ichida etakchi (eng muhim) raqam bo'ling a, x = a div β ^m va y etakchi raqam b, y = b div β ^m.
  • 2 dan 3 gacha boshlang matritsa

  ${ displaystyle textstyle { begin {bmatrix} A & B & x C & D & y end {bmatrix}}}$ kengaytirilgan identifikatsiya matritsasi ${ displaystyle textstyle { begin {bmatrix} 1 & 0 & x 0 & 1 & y end {bmatrix}},}$

  va evklid algoritmini bir vaqtning o'zida juftlarga bajaring (x + A, y + C) va (x + B, y + D.), takliflar farq qilguncha. Ya'ni, sifatida takrorlang ichki halqa:

  • Takliflarni hisoblang w₁ ning uzoq bo'linmalaridan (x + A) tomonidan (y + C) va w₂ ning (x + B) tomonidan (y + D.) mos ravishda. Shuningdek, ruxsat bering w evklid algoritmining uzoq bo'linishlari zanjiridagi hozirgi uzoq bo'linishdan (hisoblanmagan) miqdor bo'ling.

  • • Agar w₁ ≠ w₂, keyin ichki iteratsiyadan chiqing. Boshqa to'plam w ga w₁ (yoki w₂).
    • Joriy matritsani almashtiring

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

    matritsa mahsuloti bilan

    ${ displaystyle 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}}}$

    kengaytirilgan evklid algoritmining matritsali formulasiga muvofiq.

    • Agar B ≠ 0, ichki tsiklning boshlanishiga o'ting.
  • Agar B = 0, biz a ga erishdik boshi berk; bilan evklid algoritmining oddiy qadamini bajaring a va bva tashqi tsiklni qayta ishga tushiring.
  • O'rnatish a ga aA + bB va b ga Ca + Db (yana bir vaqtning o'zida). Bu siqilgan shaklda etakchi raqamlarda bajarilgan evklid algoritmining qadamlarini uzun butun sonlarga qo'llaydi a va b. Agar b ≠ 0 tashqi tsiklning boshlanishiga.

Adabiyotlar

• Kapil Paranjape, Lexmer algoritmi