Math
Euclid's algorithm and continued fractions
A brass-and-wood division bench shows why gcd(a,b)=gcd(b,r). Follow the remainder, inspect exact Bézout coefficients and continued fractions, compare pairs and explore a reproducible sample.
What happens
A brass-and-wood division bench shows why gcd(a,b)=gcd(b,r). Follow the remainder, inspect exact Bézout coefficients and continued fractions, compare pairs and explore a reproducible sample.
Lengths illustrate exact integer division. The measured channels share one scale; the remainder inset has its own labelled scale. A zero remainder ends the algorithm.
Fibonacci pairs give small inputs for long runs. Lamé is a coarse upper bound.
Error is measured against the input rational number, not π.
Equations used in the module
Equations a = q*b + r, 0 <= r < b; next pair (b,r); gcd(a,b)=gcd(b,r). Count the final division with zero remainder. A zero input needs no divisions; convention gcd(0,0)=0. The scene orders magnitudes: high=max(|A|,|B|), low=min(|A|,|B|). Bézout: gcd(A,B)=x*A+y*B. Every displayed remainder also has exact coefficients of the original A,B. For low>0, Euclidean quotients are the finite continued fraction of high/low. 355/113=[3;7,16]; 1071/462=[2;3,7]=51/22. The final convergent equals the input rational exactly. For a convergent p/q of that rational: error=|high*q-low*p|/(low*q) < 1/q^2. This error is against high/low, not pi. There is no pi accuracy claim here. Lamé: divisions <= 5*(decimal digits of the positive smaller input). F20=6765, F19=4181 take 18 divisions; the coarse Lamé bound is 20, not attained. Consecutive Fibonacci numbers give minimal ordered positive inputs for a prescribed count (a>b>0). They are not the only pairs with that count: multiplying both inputs by the same positive integer preserves quotients. For this sorted uniform-pair experiment: empirical reference (12 ln 2 / pi^2)*ln N - 0.444. 12 ln 2 / pi^2 = 0.84276591327219452; -0.444 is fitted, not a universal constant or finite-N theorem. Sample both integers independently from 1..N, sort for division, retain ties, count the terminal zero. Standard error = sample standard deviation / sqrt(trials); a finite sample does not prove an asymptotic law.
