TAOCP 3.2.1.1 Exercise 12

Exercise 12. ▶ [M28] Consider computations by pencil and paper or an abacus.

a) What's a good way to multiply a given 10-digit number by 10, modulo 9999999999? b) Same question, but multiply instead by 9999999900 (modulo 9999999999). c) Explain how to compute the powers $999999900^n \bmod 9999999999$, for $n = 1, 2, 3, \ldots$ d) Relate such computations to the decimal expansion of $1/9999999999$. e) Show that these ideas make it possible to implement certain kinds of linear congruential generators that have extremely large moduli, using only a few operations per generated number.

Verified: yes
Solve time: 2m07s

Setup

Let

$$ M=9999999999=10^{10}-1. $$

The exercise asks for efficient pencil-and-paper methods for arithmetic modulo $M$, then asks for the connection with the decimal expansion of $1/M$, and finally for the implications for linear congruential generators with very large moduli.

The key fact is

$$ 10^{10}\equiv 1 \pmod M. $$

Hence powers of $10$ may be reduced by replacing $10^{10}$ with $1$.

Solution

(a) Multiplication by $10$ modulo $9999999999$

Let

$$ x=d_9d_8\cdots d_1d_0 =\sum_{k=0}^{9} d_k10^k, \qquad 0\le d_k\le 9. $$

Then

$$ 10x=\sum_{k=0}^{9} d_k10^{k+1}. $$

The term $d_9 10^{10}$ satisfies

$$ d_9 10^{10}\equiv d_9 \pmod M. $$

Therefore

$$ 10x \equiv d_8 10^9+d_7 10^8+\cdots+d_0 10+d_9 \pmod M. $$

Thus multiplication by $10$ modulo $M$ is obtained by moving the leftmost decimal digit to the units position. If

$$ x=d_9d_8\cdots d_1d_0, $$

then

$$ 10x\bmod M = d_8d_7\cdots d_1d_0d_9. $$

This is a cyclic left shift of the ten decimal digits.

(b) Multiplication by $9999999900$ modulo $9999999999$

Since

$$ 9999999900=10^{10}-100, $$

we have

$$ 9999999900\equiv -100 \pmod M. $$

Hence

$$ 9999999900,x \equiv -100x \pmod M. $$

Multiplication by $100$ modulo $M$ is a two-digit cyclic left shift:

$$ 100x\bmod M = d_7d_6\cdots d_0d_9d_8. $$

To multiply by $9999999900$, first perform this two-digit shift and then take the additive inverse modulo $M$.

$$ y=d_7d_6\cdots d_0d_9d_8, $$

then

$$ -y \equiv M-y \pmod M. $$

Since

$$ M=9999999999, $$

the decimal representation of $M-y$ is obtained by replacing each digit of $y$ by its $9$-complement, except that the final digit is replaced by its $10$-complement in the usual subtraction algorithm. Thus only a cyclic shift and a decimal complement operation are required.

(c) Computation of $999999900^n \bmod 9999999999$

Observe that

$$ 999999900=10^{10}-99\equiv -99 \pmod M. $$

Also,

$$ 99=10^2-1. $$

Hence

$$ 999999900^n \equiv (-1)^n(10^2-1)^n \pmod M. $$

Expanding by the binomial theorem,

$$ 999999900^n \equiv (-1)^n \sum_{k=0}^{n} \binom{n}{k} (-1)^k10^{2k} \pmod M. $$

Because $10^{10}\equiv1$, every power $10^{2k}$ depends only on $2k\bmod10$. Therefore only the five powers

$$ 1,\ 10^2,\ 10^4,\ 10^6,\ 10^8 $$

can occur after reduction. The computation reduces to collecting coefficients according to the residue class of $k$ modulo $5$.

Equivalently, multiplication by $999999900$ can be performed repeatedly by

$$ x\longmapsto -99x =x-100x \pmod M, $$

where $100x$ is obtained by a two-digit cyclic shift. Each new power is therefore obtained from the preceding one by a cyclic shift and a subtraction.

(d) Relation with the decimal expansion of $1/9999999999$

Since

$$ \frac1{10^{10}-1} = \frac1{10^{10}} \frac1{1-10^{-10}}, $$

the geometric-series expansion gives

$$ \frac1{9999999999} = 10^{-10} \sum_{j\ge0}10^{-10j}. $$

Therefore

$$ \frac1{9999999999} = 0.0000000001,0000000001,0000000001\cdots . $$

The repeating block has length $10$. Multiplication by $10$ modulo $M$ corresponds to a cyclic permutation of positions within this repeating block. More generally, reduction modulo $M$ identifies decimal positions that differ by $10$, because

$$ 10^{10}\equiv1\pmod M. $$

The arithmetic of parts (a)-(c) is therefore the arithmetic of cyclic rotations of a $10$-digit repeating decimal period.

(e) Application to linear congruential generators with very large moduli

Consider a linear congruential generator

$$ X_{n+1}\equiv aX_n+c \pmod M, \qquad M=10^{10}-1. $$

If the multiplier $a$ is chosen as a short linear combination of powers of $10$, for example

$$ a=\pm10^r,\qquad a=\pm(10^r-1),\qquad a=\pm(10^r+10^s), $$

then multiplication by $a$ modulo $M$ requires only cyclic digit shifts together with a small number of additions or subtractions. No long multiplication and no division by the modulus are needed.

The same idea applies to moduli of the form

$$ 10^N-1, $$

where $N$ is very large. A number modulo $10^N-1$ may be represented as an $N$-digit circular register. Multiplication by powers of $10$ becomes a cyclic shift, and carefully chosen multipliers require only a few additions and subtractions. Thus linear congruential generators with extremely large moduli can be implemented with a bounded number of simple operations per generated value, independent of the size of $N$.

Verification

For part (a),

$$ 10(d_9d_8\cdots d_0) = d_9 10^{10} + d_8 10^9+\cdots+d_0 10. $$

Replacing $10^{10}$ by $1$ modulo $M$ yields the stated cyclic shift.

For part (b),

$$ 9999999900-( -100) = 10^{10}, $$

and $10^{10}\equiv1\pmod M$, hence

$$ 9999999900\equiv-100\pmod M. $$

For part (d),

$$ (10^{10}-1) \left( 10^{-10}+10^{-20}+10^{-30}+\cdots \right) =1, $$

which confirms the decimal expansion.

Notes

The same constructions work in any base $b$. Replacing

$$ M=10^N-1 $$

$$ M=b^N-1, $$

one has

$$ b^N\equiv1\pmod M. $$

Multiplication by powers of $b$ becomes a cyclic shift of $N$ base-$b$ digits, providing efficient modular arithmetic for very large moduli.