Алгоритм Евклида и цепные дроби

Уравнения
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 (finite-N).
Выбираем оба целых числа независимо из 1..N, сортируем для деления, сохраняем совпадения, считаем завершающий ноль.
Стандартная ошибка = выборочное стандартное отклонение / sqrt(число испытаний); конечная выборка не доказывает асимптотический закон.