Algorytm Euklidesa i ułamki łańcuchowe

Równania
a = q*b + r, 0 <= r < b; następna para (b,r); gcd(a,b)=gcd(b,r).
Wlicz ostatnie dzielenie, które daje resztę zero. Zero na wejściu nie wymaga żadnych dzieleń; konwencja gcd(0,0)=0.
Scena porządkuje wartości bezwzględne: high=max(|A|,|B|), low=min(|A|,|B|).
Bézout: gcd(A,B)=x*A+y*B. Każda wyświetlana reszta ma też dokładne współczynniki wyrażone przez pierwotne A,B.
Dla low>0 ilorazy euklidesowe tworzą skończony ułamek łańcuchowy liczby high/low.
355/113=[3;7,16]; 1071/462=[2;3,7]=51/22. Ostatni ułamek zbieżny jest dokładnie równy wejściowej liczbie wymiernej.
Dla ułamka zbieżnego p/q tej liczby wymiernej: error=|high*q-low*p|/(low*q) < 1/q^2.
Ten błąd odnosi się do high/low, a nie do pi. Nie ma tu żadnego twierdzenia o dokładności pi.
Lamé: liczba dzieleń <= 5*(liczba cyfr dziesiętnych mniejszego dodatniego wejścia).
F20=6765, F19=4181 wymagają 18 dzieleń; zgrubne oszacowanie Lamégo wynosi 20 i nie jest osiągnięte.
Kolejne liczby Fibonacciego dają minimalne uporządkowane dodatnie wejścia dla zadanej liczby dzieleń (a>b>0).
Nie są to jedyne pary o tej liczbie: pomnożenie obu wejść przez tę samą dodatnią liczbę całkowitą zachowuje ilorazy.
Dla tego eksperymentu z posortowanymi parami jednostajnymi: empiryczna wartość odniesienia (12 ln 2 / pi^2)*ln N - 0.444.
12 ln 2 / pi^2 = 0.84276591327219452; -0.444 jest dopasowane, nie jest stałą uniwersalną ani twierdzeniem typu skończone-N.
Losujemy obie liczby całkowite niezależnie z 1..N, porządkujemy je do dzielenia, zachowujemy pary równych liczb, liczymy końcowe zero.
Błąd standardowy = odchylenie standardowe z próby / sqrt(liczba prób); skończona próba nie dowodzi prawa asymptotycznego.