UNREASONABLE EFFECTIVENESS OF NUMBER THEORY

17

11. Chinese remainders feed fast algorithm

In the computation of discrete circular convolutions

M

h(n) = £ f(k)g(n - k)modM, n = 1,2, ... M , (9)

k = l

a pervasive task in numerous numerical applications [6], the number of

arithmetical "operations" (multiplications and additions) is

M2,

where M is

the period of the involved sequences. It is easy to show [7] that if M has

r 1 coprime factors

M = m^m2 ... mr ,

then the one-dimensional convolution (9) can be converted into an r-

dimensional convolution by expressing the summating index n in the Sino

notation:

n = 2 niNiM/mj mod M ,

i

where ni is least positive remainders of n modulo mi, and Nj is given by the

congruence

NiM/nii = 1 mod mj

The necessary summations over the n^ require a total of MEm^ operations,

which can be considerably smaller than

M2.

For example, for

M = 1 007 760 = 13 • 15 • 16 • 17 • 19, the number of operations drops

by a factor M/Em^ = 12 597 - a very substantial saving, comparable to the

economy offered by the Fast Fourier Transform (FFT), which also converts a

one-dimensional operation into a multi-dimensional one. In fact, the fast

Chinese convolution [7] described here complements nicely the FFT which

works most efficiently if all factors m^ of M equal 2 rather than being

coprime.

12. Epilogue

It is clear that only a sprinkling of the numerous applications of number

theory outside mathematics proper could be mentioned here. Among the