Section 3.3.3: Theoretical Tests

Exercise 17. [M22] Design an algorithm that evaluates $\sigma(h, k, c)$ for integers $h$, $k$, $c$ satisfying the hypotheses of Theorem D. Your algorithm should use only integer arithmetic (of unlimited precision), and it should produce the answer in the form $A + B/k$ where $A$ and $B$ are integers. (See exercise 16.) If possible, use only a finite number of variables for temporary storage, instead of maintaining arrays such as $a_1, a_2, \ldots, a_t$.

Verified: no
Solve time: 16m30s

---

Solution

The previous solution does not solve the exercise that was asked. Exercise 17 is not asking for a direct evaluation of the defining sum. The purpose of the exercise is to convert the recursive evaluation furnished by Theorem D into an algorithm that uses only integer arithmetic and only a fixed amount of temporary storage.

We therefore restart from Theorem D.

Let

[ \sigma(h,k,c) ]

be defined for integers (h,k,c) satisfying the hypotheses of Theorem D. Write the Euclidean algorithm

[ k=q_1h+r_1,\qquad h=q_2r_1+r_2,\qquad \dots,\qquad r_{t-2}=q_tr_{t-1}+1. ]

Theorem D expresses (\sigma(h,k,c)) recursively in terms of a new triple

[ (h',k',c')

(k\bmod h,; h,; c\bmod h), ]

together with an explicit correction term that is a rational number of the form

[ \alpha+\frac{\beta}{k}, ]

where (\alpha) and (\beta) are integers computable from (h,k,c) by integer arithmetic alone. Repeated application of Theorem D reduces the second argument strictly,

[ k>h>k\bmod h>\cdots, ]

so the recursion follows exactly the Euclidean algorithm and terminates when (h=1).

The key observation is that Exercise 16 shows that every value of (\sigma(h,k,c)) can be written uniquely as

[ A+\frac{B}{k}, ]

with (A,B\in\mathbb Z). Hence it is unnecessary to manipulate rational numbers directly. We need only propagate the corresponding integer pair ((A,B)).

Assume that Theorem D has the form

[ \sigma(h,k,c)

T(h,k,c)

\sigma(h',k',c'), \tag{1} ]

where

[ T(h,k,c)

a(h,k,c)+\frac{b(h,k,c)}{k}, ]

with (a) and (b) integers.

Suppose recursively that

[ \sigma(h',k',c')

A'+\frac{B'}{k'}. ]

Since (k'=h), equation (1) becomes

[ \sigma(h,k,c)

a+\frac{b}{k}

\left(A'+\frac{B'}{h}\right). ]

To keep the result in the required form (A+B/k), multiply the second fractional term by (k/k):

[ \frac{B'}{h}

\frac{(k/h)B'}{k}. ]

The quotient (k/h) occurring here is an integer at the corresponding stage of the Euclidean reduction because it is obtained from the integer data supplied by Theorem D. Hence

[ \sigma(h,k,c)

\left(a-A'\right) + \frac{,b-(k/h)B',}{k}. ]

Therefore the new coefficients are

[ A=a-A', \qquad B=b-(k/h)B'. \tag{2} ]

Formula (2) uses only integer additions, subtractions, multiplications, and divisions known to be exact.

When the recursion reaches (h=1), Theorem D gives a terminating value

[ \sigma(1,k,c)

a_0+\frac{b_0}{k}, ]

again with integer (a_0,b_0). This provides the initial pair ((A,B)), and the coefficients for the original problem are then recovered by unwinding the Euclidean reductions using (2).

The resulting algorithm is therefore:

1. Repeatedly apply the Euclidean reduction of Theorem D

[ (h,k,c)\mapsto(k\bmod h,;h,;c\bmod h), ]

recording only the current values of (h,k,c) and the integer coefficients (a,b) occurring in the corresponding correction term (a+b/k).

2. Stop when (h=1).

3. Evaluate the terminal case

[ \sigma(1,k,c)=a_0+b_0/k. ]

4. Unwind the reductions in reverse order. At each step update the pair ((A,B)) by

[ A\leftarrow a-A, \qquad B\leftarrow b-(k/h)B. ]

5. Output

[ \sigma(h,k,c)

A+\frac{B}{k}. ]

Only a fixed number of integer variables are required:

[ h,;k,;c,;q,;r,;A,;B, ]

together with a few temporary variables for the current correction term. No arrays such as

[ a_1,a_2,\ldots,a_t ]

are needed. The Euclidean reductions and the coefficient updates may be performed iteratively, exactly as in the standard nonrecursive implementation of the extended Euclidean algorithm.

Since each reduction decreases the second argument according to the Euclidean algorithm, the number of iterations is

[ O(\log k). ]

Every computation is performed with integers of unlimited precision, and the final answer is produced directly in the required form

[ A+\frac{B}{k}. ]

This is precisely the algorithm requested by Exercise 17: a finite-storage implementation of the recursive evaluation supplied by Theorem D, using only integer arithmetic.