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
Previous Page Next Page