Řetězový zlomek

O(log min(a, b))

Řetězový zlomek vyjadřuje a/b jako a₀ + 1/(a₁ + 1/(a₂ + …)). Členy najdeš tak, že vezmeš celou část q = ⌊a/b⌋, odečteš ji, převrátíš zbytek a opakuješ — což je přesně posloupnost podílů, které Euklidův algoritmus produkuje při výpočtu gcd(a, b). Pro racionální číslo tedy rozvoj vždy skončí a jeho délka je počet kroků dělení. Řetězové zlomky dávají nejlepší racionální aproximace čísla (zkrácení dříve dává konvergenty) a odhalují strukturu, kterou desetinný zápis skrývá. Každá buňka je jeden člen aᵢ; krok ukazuje dělení a = q·b + r, které ho vytvořilo.

Posloupnost
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Vezmi celou část q = ⌊a/b⌋ jako další člen.
  2. Nahraď a/b zlomkem b/(a mod b).
  3. Opakuj, dokud zbytek není 0.
  4. Členy jsou [a₀; a₁, a₂, …].

Pseudokód

1continuedFraction(a, b):            # O(log min(a,b))2  while b ≠ 0:3    q ← ⌊a / b⌋                      # next term4    emit q5    a, b ← b, a mod b                # same step as gcd