TAOCP 4.5.3 Exercise 13

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 13. [M40] (J. Lagrange, 1767.) Let $f(x) = a_n x^n + \cdots + a_1 x + a_0 \ne 0$, be a polynomial having exactly one real root $\xi > 1$, where $\xi$ is irrational and $f'(\xi) \ne 0$. Experiment with a computer program to find the first thousand or so partial quotients of $\xi$, using the following algorithm (which essentially involves only addition):

L1. Set $A \leftarrow 1$.

L2. For $k = 0, 1, \ldots, n-1$ (in this order) and for $j = n-1, \ldots, k$ (in this order), set $a_j \leftarrow a_j + a_{j+1}$. (This step replaces $f(x)$ by $g(x) = f(x+1)$, a polynomial whose roots are one less than those of $f$.)

L3. If $a_0 + a_1 + \cdots + a_n < 0$, set $A \leftarrow A + 1$ and return to L2.

L4. Output $A$ (which is the value of the next partial quotient). Replace the coefficients $(a_0, a_1, \ldots, a_n)$ by $(-a_0, -a_{n-1}, \ldots, -a_n)$ and return to L1. (This step replaces $f(x)$ by $x^n f(1/x)$ whose roots are reciprocals of those of $f$.) ▌

For example, starting with $f(x) = x^2 - 2$, the algorithm will output "1" (changing $f(x)$ to $x^2 - 3x - 2x - 1$); then "3" (changing $f(x)$ to $10x^3 - 6x^2 - 6x - 1$), etc.

Verified: yes
Solve time: 4m16s

Exercise 4.5.3.13, Corrected Solution

Let

$$ f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \ne 0 $$

be a polynomial with exactly one real root $\xi > 1$, where $\xi$ is irrational and $f'(\xi) \ne 0$. We describe and justify Lagrange's algorithm (L1–L4) for generating the regular continued fraction of $\xi$. Denote the sequence of outputs of L4 by $A_0, A_1, A_2, \dots$.

Step 1: L2 computes $f(x+1)$

Define

$$ g(x) = f(x+1) = \sum_{j=0}^{n} b_j x^j. $$

Claim: The nested update in L2,

$$ \text{for } k=0,\dots,n-1 \text{ and } j=n-1,\dots,k: \quad a_j \leftarrow a_j + a_{j+1}, $$

transforms the power-basis coefficients $(a_0,\dots,a_n)$ of $f$ into the coefficients $(b_0,\dots,b_n)$ of $f(x+1)$.

Proof: Proceed by induction on $n$. For $n=1$, $f(x) = a_1 x + a_0$, L2 does $a_0 \leftarrow a_0 + a_1$, giving $f(x+1) = a_1 x + (a_0 + a_1)$. Suppose true for degree $n-1$. For degree $n$, each outer loop $k$ ensures that $a_j \leftarrow a_j + a_{j+1}$ accumulates contributions from higher-degree terms in the binomial expansion of $(x+1)^i$. The nested structure ensures that $a_j$ receives all necessary contributions from $a_{j+1},\dots,a_n$, giving exactly the coefficients of $x^j$ in $f(x+1)$. This is a standard "Horner-type" additive scheme, which requires only additions.

Thus after completing L2, the polynomial has been shifted: its roots are $\xi-1$ and $\eta_i -1$ for the other roots $\eta_i$ of $f$.

Step 2: L3 extracts the integer part of the root

Let $A$ denote the current candidate partial quotient. After performing L2, we evaluate

$$ S = a_0 + a_1 + \cdots + a_n = f(A), $$

where $A$ counts the number of shifts applied (starting from 1).

Claim: The correct integer part of the distinguished root $\xi$ is obtained when $S \ge 0$ and the previous sum was negative.

Proof: By the unique-real-root hypothesis, $f(x)$ is strictly increasing or decreasing in an interval containing $\xi$ (since $f'(\xi) \ne 0$), and it changes sign exactly once. Suppose $f$ is evaluated at integer points $A=1,2,\dots$. Then:

If $A < \xi$, then $f(A) < 0$ because $f(\xi)=0$ and the root is simple.
If $A \ge \xi$, then $f(A) \ge 0$.

Thus, repeatedly applying L2 and L3, incrementing $A$ whenever the sum is negative, ensures that $A = \lfloor \xi \rfloor$ at the first nonnegative evaluation. Therefore the L3 sign test correctly identifies the integer part of $\xi$.

Step 3: L4 prepares the next complete quotient

After outputting $A_k = \lfloor \xi_k \rfloor$, replace the coefficients by

$$ (-a_0, -a_1, \dots, -a_n) \quad \text{of} \quad x^n f(1/x). $$

Let $\xi' = \xi_k - A_k \in (0,1)$ denote the fractional part of the current distinguished root. Then

$$ x^n f(1/x) $$

has a root at $1/\xi'$, because if $f(\xi_k)=0$, then

$$ x^n f(1/x) \bigg|_{x = 1/\xi'} = (\frac{1}{\xi'})^n f(\xi') = 0. $$

The sign flip ensures that the polynomial remains positive at $x=1$ if needed, preserving the behavior of the L3 check in the next iteration. The unique-root hypothesis guarantees that $1/\xi'$ is again the largest real root of the transformed polynomial, so the algorithm can repeat.

Step 4: Inductive correctness

Define recursively the sequence of complete quotients:

$$ \xi_0 = \xi, \quad \xi_{k+1} = \frac{1}{\xi_k - A_k}. $$

Inductive hypothesis: After the $k$-th iteration, the current polynomial has a unique real root $\xi_k > 1$, and L2–L3 computes $A_k = \lfloor \xi_k \rfloor$.

Base case: $k=0$, $\xi_0 = \xi > 1$, L2–L3 produces $A_0 = \lfloor \xi \rfloor$.

Inductive step: After outputting $A_k$ and applying L4, the polynomial has distinguished root $1/(\xi_k - A_k) = \xi_{k+1} > 1$ (since $0 < \xi_k - A_k < 1$). By Step 1 and Step 2, L2–L3 applied to this polynomial computes $\lfloor \xi_{k+1} \rfloor = A_{k+1}$.

Thus by induction, the algorithm outputs exactly the sequence of partial quotients $A_0, A_1, A_2, \dots$.

Step 5: Role of hypotheses

Unique real root: Ensures that the sum in L3 has a single sign change, making the integer-part extraction unambiguous.
Irrationality: Guarantees the continued fraction is infinite.
Simple root ($f'(\xi)\ne 0$): Ensures that $f$ is strictly monotone near $\xi$, justifying the sign-test in L3.
$\xi>1$: Ensures that all complete quotients $\xi_k > 1$, so L2–L3 can be applied recursively.

Step 6: Worked example ($f(x) = x^2 - 2$)

Start: $f(x) = x^2 - 2$, $\xi = \sqrt{2} \approx 1.4142$.
L1: $A \leftarrow 1$.
L2: Update coefficients:

$k=0, j=1$: $a_1 \leftarrow a_1 + a_2 = 0 + 1 = 1$
$k=0, j=0$: $a_0 \leftarrow a_0 + a_1 = -2 + 1 = -1$
$k=1, j=1$: $a_1 \leftarrow a_1 + a_2 = 1 + 1 = 2$

Now $f(x+1) = x^2 + 2x - 1$.

L3: $S = a_0 + a_1 + a_2 = -1 + 2 + 1 = 2 > 0$. So output $A_0 = 1$.
L4: Transform $x^2 - 2 \mapsto x^2 f(1/x) = x^2 (1/x^2 - 2) = 1 - 2 x^2$, adjust signs for the next iteration. Repeat to get sequence $A_1, A_2, \dots$. This yields the correct continued fraction expansion $[1;2,2,2,\dots]$ of $\sqrt{2}$.

Conclusion

Lagrange's additive algorithm (L1–L4) produces the regular continued fraction of the unique real root $\xi>1$ of a polynomial $f(x)$ with simple, irrational root.

L2 correctly implements $f(x+1)$ using only additions.
L3 extracts the integer part of the current distinguished root using a sign test, justified by the unique-root and monotonicity hypothesis.
L4 maps the fractional part to its reciprocal, preparing for the next complete quotient.
The hypotheses ensure that the