TAOCP 4.5.3 Exercise 30
Let u=qv+r,\qquad 0\le r<v .
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 30. ▶ [HM22] The following "greedy" variant of Euclid's algorithm is often suggested: Instead of replacing $v$ by $u \bmod v$ during the division step, replace it by $|(u \bmod v) - v|$ if $u \bmod v > \frac{1}{2}v$. For example, if $u = 26$ and $v = 7$, we have $\gcd(26, 7) = \gcd(-2, 7) = \gcd(2, 7)$. Compare this procedure with Euclid's algorithm; estimate the number of division steps this method saves, on the average.
Verified: yes
Solve time: 9m16s
Solution
Let
$$ u=qv+r,\qquad 0\le r<v . $$
The modified algorithm replaces the ordinary remainder $r$ by the least absolute remainder
$$ r^{*}= \begin{cases} r,& r\le v/2,\ v-r,& r>v/2. \end{cases} $$
Equivalently,
$$ u=q^{}v+\varepsilon r^{}, \qquad -\frac12v<\varepsilon r^{*}\le \frac12v, $$
where $q^{*}$ is the nearest integer to $u/v$ and
$\varepsilon=\pm1$.
Hence the algorithm is not a new gcd method at all; it is Euclid's algorithm performed with nearest-integer quotients rather than floor quotients. The associated continued-fraction expansion is the nearest-integer continued fraction.
Correctness
Since
$$ u-q^{}v=\pm r^{}, $$
we have
$$ \gcd(u,v)=\gcd(v,u-q^{}v) =\gcd(v,r^{}), $$
so every step preserves the gcd.
Comparison with ordinary Euclid
For ordinary Euclid, the number $E(N)$ of division steps required for integers of size at most $N$ satisfies
$$ E(N)\sim \frac{12\ln 2}{\pi^{2}}\ln N, $$
a classical result of Heilbronn, Dixon, Knuth, and others.
The modified algorithm corresponds to the dynamical system
$$ T(x)=\left|\frac1x-\operatorname{nint}!\left(\frac1x\right)\right|, \qquad 0<x\le \frac12, $$
where $\operatorname{nint}$ denotes the nearest integer. This is the nearest-integer continued-fraction map. Its metric entropy is
$$ h=\frac{\pi^{2}}{6\ln(1+\sqrt2)}. $$
For Euclid-type algorithms, the average number of quotient digits is the reciprocal of the entropy constant, hence
$$ E^{*}(N) \sim \frac{6\ln(1+\sqrt2)}{\pi^{2}} \ln N . $$
Therefore
$$ \frac{E^{*}(N)}{E(N)} = \frac{\dfrac{6\ln(1+\sqrt2)}{\pi^{2}}} {\dfrac{12\ln2}{\pi^{2}}} = \frac{\ln(1+\sqrt2)} {2\ln2} \approx 0.635 . $$
Thus the modified algorithm uses only about $63.5%$ as many division steps as ordinary Euclid.
The average saving is therefore
$$ 1-0.635\approx 0.365 . $$
So the greedy method saves about
$$ 36.5% $$
of the division steps, not $50%$.
Example
For $(u,v)=(26,7)$,
$$ 26=4\cdot7-2. $$
The nearest-integer quotient is $4$, giving remainder $2$. Hence
$$ (26,7)\to(7,2)\to(2,1)\to(1,0), $$
which takes $3$ divisions.
Ordinary Euclid gives
$$ (26,7)\to(7,5)\to(5,2)\to(2,1)\to(1,0), $$
which takes $4$ divisions.
Conclusion
The "greedy" algorithm is Euclid's algorithm with least absolute remainders, equivalently with nearest-integer quotients. Its average number of division steps is
$$ \boxed{ E^{*}(N)\sim \frac{6\ln(1+\sqrt2)}{\pi^{2}}\ln N } $$
compared with
$$ \boxed{ E(N)\sim \frac{12\ln2}{\pi^{2}}\ln N } $$
for ordinary Euclid. Therefore
$$ \boxed{ \frac{E^{*}(N)}{E(N)} = \frac{\ln(1+\sqrt2)}{2\ln2} \approx 0.635 } $$
and the average saving is
$$ \boxed{ 1-\frac{\ln(1+\sqrt2)}{2\ln2} \approx 0.365. } $$
So the greedy variant saves approximately $36%$ of the division steps on average.