TAOCP 4.5.1 Exercise 7
Let \frac{u}{u'},\qquad \frac{v}{v'} be the input fractions, with
Exercise 7. [**] [$M22$] How large can the absolute value of the quantity $t$ become, in the addition-subtraction method recommended in the text, if the numerators and denominators of the inputs are less than $N$ in absolute value?
Verified: yes
Solve time: 3m51s
Let
$$ \frac{u}{u'},\qquad \frac{v}{v'} $$
be the input fractions, with
$$ |u|,\ |u'|,\ |v|,\ |v'|<N. $$
In the addition-subtraction method of Section 4.5.1, one first computes
$$ d_1=\gcd(u',v'), $$
and then forms
$$ t=u\frac{v'}{d_1}\pm v\frac{u'}{d_1}. $$
We seek the largest possible value of $|t|$.
Since $d_1\ge 1$,
$$ \left|u\frac{v'}{d_1}\right| \le |u|,\frac{|v'|}{d_1} \le |u|,|v'| < (N-1)^2, $$
and similarly,
$$ \left|v\frac{u'}{d_1}\right| < (N-1)^2. $$
Therefore, by the triangle inequality,
$$ |t| \le \left|u\frac{v'}{d_1}\right| + \left|v\frac{u'}{d_1}\right| < 2(N-1)^2. $$
Hence every computation satisfies
$$ |t|<2(N-1)^2. $$
To show that this bound is best possible, choose
$$ u=v=u'=v'=N-1. $$
Then
$$ d_1=\gcd(N-1,N-1)=N-1, $$
and, using the addition case,
$$ t=(N-1)\frac{N-1}{N-1} +(N-1)\frac{N-1}{N-1} =2(N-1). $$
This does not approach the upper bound, because the large common divisor reduces the terms. To maximize $|t|$, we instead want $d_1=1$.
Take
$$ u=v=u'=v'=N-1 $$
except replace one denominator by $N-2$. More precisely, let
$$ u=v=N-1,\qquad u'=N-1,\qquad v'=N-2, $$
assuming $N\ge3$. Then $\gcd(u',v')=1$, and
$$ t=(N-1)(N-2)+(N-1)^2 =(N-1)(2N-3) =2(N-1)^2-(N-1). $$
Thus values of $t$ occur that differ from $2(N-1)^2$ by only $N-1$. Since every admissible choice satisfies
$$ |t|<2(N-1)^2, $$
and values arbitrarily close to this bound are attainable, the largest possible order of magnitude is
$$ 2(N-1)^2. $$
Therefore the quantity $t$ can never reach $2(N-1)^2$, but its maximum possible value is asymptotically that large. Equivalently,
$$ \boxed{|t|<2(N-1)^2<2N^2.} $$
Hence the greatest possible absolute value of $t$ is bounded by $2(N-1)^2$, and this bound is essentially sharp. ∎