Euklidův největší společný dělitel

O(log min(a, b))

Euklidův algoritmus najde největšího společného dělitele bez jakéhokoli rozkladu na prvočísla. Představ si obdélník a×b. Odřízni z něj tolik čtverců b×b, kolik se jich vejde podél delší strany — tedy ⌊a/b⌋ kusů — a zůstane menší pruh (a mod b)×b. Největší společný dělitel původního obdélníku je stejný jako dělitel toho pruhu, takže postup zopakuj na něm, a znovu, dokud jedna strana nedělí druhou beze zbytku. Úplně poslední vyříznutý čtverec je největší čtverec dlaždicující celý obdélník a jeho strana je gcd(a, b). Každé vyříznutí je přesně aritmetické gcd(a, b) = gcd(b, a mod b), takže obrázek a algoritmus jsou jedno a totéž. Běží v O(log min(a, b)) krocích — obdélník se zmenšuje rychle, což je i důvod, proč je nejhorším případem dvojice sousedních Fibonacciho čísel.

Dlaždicování obdélníku
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Polož obě čísla jako strany obdélníku.
  2. Odřízni tolik čtverců kratší strany, kolik se jich vejde.
  3. Pokračuj na zbylém pruhu — gcd(a, b) = gcd(b, a mod b).
  4. Skonči, až nic nezbude; strana posledního čtverce je hledaný dělitel.

Pseudokód

1gcd(a, b):                          # O(log min(a, b))2  # geometrically: tile an a×b rectangle with squares3  while b ≠ 0:4    # carve ⌊a/b⌋ squares of side b off the rectangle5    a, b ← b, a mod b                # leftover strip recurses6  return a                           # side of the last square