Lehmers GCD-algoritm

Lehmers GCD-algoritm , uppkallad efter Derrick Henry Lehmer , är en snabb GCD- algoritm , en förbättring av den enklare men långsammare euklidiska algoritmen . Det används främst för stora heltal som har en representation som en sträng av siffror i förhållande till någon vald siffersystembas, säg β = 1000 eller β = 2 ³² .

Algoritm

Lehmer noterade att de flesta av kvoterna från varje steg i divisionsdelen av standardalgoritmen är små. (Till exempel Knuth att kvoterna 1, 2 och 3 utgör 67,7 % av alla kvoter.) Dessa små kvoter kan identifieras från endast några få ledande siffror. Algoritmen börjar alltså med att dela av de inledande siffrorna och beräkna sekvensen av kvoter så länge den är korrekt.

Säg att vi vill erhålla GCD för de två heltalen a och b . Låt a ≥ b .

• Om b bara innehåller en siffra (i den valda basen , säg β = 1000 eller β = 2 ³² ), använd någon annan metod, såsom den euklidiska algoritmen , för att få resultatet.
• Om a och b skiljer sig åt i längden på siffrorna, gör en division så att a och b är lika långa, med längden lika med m .
• Yttre slinga: Iterera tills en av a eller b är noll:
  • Minska m med ett. Låt x vara den inledande (mest signifikanta) siffran i a , x = a div β ^m och y den inledande siffran i b , y = b div β ^m .
  • Initiera en 2 x 3 matris

  $\textstyle {\begin{bmatrix}A&B&x\\C&D&y\end{bmatrix}}$ till en utökad identitetsmatris $\textstyle {\begin {bmatrix}1&0&x\\0&1&y\end{bmatrix}},$

  och utför den euklidiska algoritmen samtidigt på paren ( x + A , y + C ) och ( x + B , y + D ), tills kvoterna skiljer sig åt. Det vill säga, iterera som en inre slinga :

  • Beräkna kvoterna w ₁ av de långa divisionerna av ( x + A ) med ( y + C ) respektive w ₂ av ( x + B ) med ( y + D ). Låt också w vara den (ej beräknade) kvoten från den aktuella långa divisionen i kedjan av långa divisioner av den euklidiska algoritmen.

  • • Om w ₁ ≠ w ₂ , bryt ut ur den inre iterationen. Ställ annars w till w ₁ (eller w ₂ ).
    • Byt ut den nuvarande matrisen

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

    med matrisprodukten

    ${\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}}} enligt matrisformuleringen av den utökade euklidiska algoritmen$

    .

    • Om B ≠ 0, gå till början av den inre slingan.
  • Om B = 0 har vi nått ett dödläge ; utför ett normalt steg i den euklidiska algoritmen med a och b , och starta om den yttre slingan.
  • Ställ in a till aA + bB och b till Ca + Db (igen samtidigt). Detta tillämpar stegen i den euklidiska algoritmen som utfördes på de inledande siffrorna i komprimerad form på de långa heltalen a och b . Om b ≠ 0 gå till början av den yttre slingan.

• Kapil Paranjape , Lehmers algoritm