Алгоритм Евкліда і ланцюгові дроби

Рівняння
a = q*b + r, 0 <= r < b; наступна пара (b,r); gcd(a,b)=gcd(b,r).
Враховуйте останнє ділення з нульовою остачею. Нульове вхідне значення не потребує жодного ділення; за домовленістю gcd(0,0)=0.
Сцена впорядковує модулі: high=max(|A|,|B|), low=min(|A|,|B|).
Безу: gcd(A,B)=x*A+y*B. Кожна показана остача також виражається через початкові A,B із точними коефіцієнтами.
Для low>0 частки алгоритму Евкліда утворюють скінченний ланцюговий дріб числа high/low.
355/113=[3;7,16]; 1071/462=[2;3,7]=51/22. Останній підхідний дріб точно дорівнює вхідному раціональному числу.
Для підхідного дробу p/q цього раціонального числа: error=|high*q-low*p|/(low*q) < 1/q^2.
Ця похибка обчислена щодо high/low, а не щодо pi. Тут немає жодних тверджень про точність pi.
Ламе: кількість ділень <= 5*(кількість десяткових цифр меншого додатного входу).
F20=6765, F19=4181 потребують 18 ділень; груба межа Ламе дорівнює 20 і не досягається.
Послідовні числа Фібоначчі дають мінімальні впорядковані додатні входи для заданої кількості ділень (a>b>0).
Це не єдині пари з такою кількістю: множення обох входів на те саме додатне ціле число зберігає частки.
Для цього експерименту з відсортованими рівномірними парами: емпіричний орієнтир (12 ln 2 / pi^2)*ln N - 0.444.
12 ln 2 / pi^2 = 0.84276591327219452; -0.444 підібрано, це не універсальна стала й не теорема скінченного-N.
Обираємо обидва цілі числа незалежно з 1..N, сортуємо для ділення, зберігаємо рівні пари, враховуємо кінцевий нуль.
Стандартна похибка = вибіркове стандартне відхилення / sqrt(кількість випробувань); скінченна вибірка не доводить асимптотичного закону.