TAOCP 3.2.1.1 Exercise 13

Section 3.2.1.1: Choice of Modulus

Exercise 13. [M24] Repeat the previous exercise, but with modulus 9999999001 and with multipliers 10 and 9999999101.

Verified: yes
Solve time: 1m54s

Solution

Let

$m=9999999001=10^{10}-999=10^{10}-31^2.$

The congruence

$$$$

is the fundamental relation. Every computation modulo $m$ can therefore be reduced by replacing a block of ten decimal digits by $999$ times that block.

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

Write

$$$$

where $0\le a\le 9$ is the leading decimal digit and

$$$$

Then

$$ \equiv 999a+10b \pmod m. $$

Thus multiplication by $10$ is performed by moving the leading digit to the end and multiplying it by $999$.

If the decimal representation of $x$ is

$$$$

then

$$= 10(d_2d_3\cdots d_{10})+999a.$$

Only a shift and the addition of $999a$ are required.

(b) Multiplication by $9999999101$ modulo $9999999001$

Since

$$$$

we have

$$$$

Hence it suffices to multiply by $100$.

Write

$$$$

with

$$$$

Then

$$ \equiv999a+100b \pmod m. $$

Therefore multiplication by $9999999101$ is accomplished by moving the first two decimal digits to the end and adding $999$ times those two digits.

(c) Computation of $9999999101^n\bmod9999999001$

Because

$$$$

we seek

$$$$

Since

$$$$

it follows that

$$ \qquad 0\le r<5. $$

Thus powers are generated recursively from

$$$$

For example,

$$$$

and in general

$$$$

The computation requires only repeated multiplication by the small number $999$ together with at most four extra factors of $100$.

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

Since

$$$$

we have

$$= \frac1{10^{10}} \frac1{1-\frac{999}{10^{10}}}.$$

Using the geometric series,

$$ \frac1m = \frac1{10^{10}} \sum_{k\ge0} \left(\frac{999}{10^{10}}\right)^k = \sum_{k\ge0} \frac{999^k}{10^{10(k+1)}}. $$

Hence the decimal expansion is obtained by successive powers of $999$.

Each block of ten decimal digits is determined by $999^k$. Explicitly,

$$ \frac1{9999999001} = 0.0000000001, 0000000999, 0009980010, 9970029990\cdots $$

where the successive ten-digit blocks are the decimal representations of

$$$$

with leading zeros inserted as necessary.

The reduction rule

$$$$

is exactly the arithmetic counterpart of this block structure in the decimal expansion.

(e) Linear congruential generators with extremely large moduli

The preceding parts depend only on the identity

$$$$

with comparatively small $c$.

For such a modulus,

$$$$

$$ \qquad 0\le B<10^N, $$

then

$$$$

Thus reduction modulo $m$ replaces a long $N$-digit block by multiplication with the small constant $c$.

A linear congruential generator

$$$$

can therefore be implemented even when $m$ contains hundreds or thousands of decimal digits, provided that $m=10^N-c$ with small $c$. The product $aX_n+b$ is split into high and low $N$-digit parts, and each reduction step replaces a factor $10^N$ by the small multiplier $c$. Only a few shifts of decimal blocks and a few multiplications by small constants are needed.

Consequently, linear congruential generators with extremely large moduli of the form

$$$$

can be realized using only a bounded number of elementary operations per generated value, despite the enormous size of the modulus.

\boxed{\text{The modulus }9999999001=10^{10}-999\text{ permits reduction by the rule }10^{10}\equiv999\pmod{9999999001},\text{ yielding all parts (a)--(e).}