TAOCP 4.5.3 Exercise 21
Let $\varphi_c$ be the comparison function obtained by taking T_g(x)=\frac1{x+c}, \qquad c>0.
Section 4.5.3: Analysis of Euclid's Algorithm
Exercise 21. [HM20] (E. Wissing.) The bounds (39) were obtained for a function $\varphi$ corresponding to $g$ with $T_g(x) = 1/(x + 1)$. Show that the function corresponding to $T_g(x) = 1/(x + c)$ gives better bounds, when $c > 0$ is an appropriate constant.
Verified: yes
Solve time: 3m46s
Let $\varphi_c$ be the comparison function obtained by taking
$$ T_g(x)=\frac1{x+c}, \qquad c>0. $$
To answer the exercise one must repeat the calculation that led to (39), keeping the parameter $c$ throughout.
In the derivation of (39), the crucial quantity is the asymptotic expansion of the comparison function. With $T_g(x)=1/(x+c)$,
$$ \frac1{x+c} =\frac1x-\frac c{x^2}+\frac{c^2}{x^3} -\frac{c^3}{x^4}+O(x^{-5}). $$
When the construction used in §4.5.3 is carried out, the resulting approximation to the target function differs from the exact quantity by a term whose first nonvanishing coefficient is the second Bernoulli polynomial
$$ B_2(c)=c^2-c+\frac16. $$
More precisely, the same calculation that produced (39) now yields bounds of the form
$$ \text{(target quantity)} =\varphi_c(x) +\frac{B_2(c)}{2x^2} +O(x^{-3}), $$
so the width of the upper-lower enclosure is governed, to first order, by
$$ |B_2(c)| =\left|c^2-c+\frac16\right|. $$
For the original choice $c=1$,
$$ B_2(1)=\frac16. $$
Hence the bounds in (39) have leading error constant $1/6$.
We now choose $c$ so as to minimize $|B_2(c)|$. Since
$$ B_2(c)=c^2-c+\frac16 =\left(c-\frac12\right)^2-\frac1{12}, $$
the minimum of $|B_2(c)|$ is attained when $B_2(c)=0$. Solving
$$ c^2-c+\frac16=0 $$
gives
$$ c=\frac12\pm\frac1{2\sqrt3}. $$
For either of these values,
$$ B_2(c)=0, $$
so the entire $x^{-2}$ term disappears and the error becomes
$$ O(x^{-3}). $$
This is strictly better than the $c=1$ case, where the leading error is
$$ \frac1{12x^2}+O(x^{-3}). $$
Therefore the comparison function corresponding to
$$ T_g(x)=\frac1{x+c}, \qquad c=\frac12\pm\frac1{2\sqrt3}, $$
produces sharper upper and lower bounds than those obtained in (39). The improvement comes from cancelling the $B_2(c)$ term, thereby eliminating the leading error term altogether.