Quote:
Originally Posted by Kevin
I believe for the example given, a FFT size of 2 was used. The general formula uses cos(pi/n)+i sin(pi/n) , which reduces to i for a FFT size of 2.

No, the (n)th complex roots of unity are given by
exp(i*2*pi/n) = cos(2*pi/n)+i*sin(2*pi/n). The reason one sees the i's
in my example is that to DFTmultiply two general length2 numbers, one
must zeropad the input vectors to double the number of input digits, i.e.
one must use a length4 DFT. Note that for
modular multiplication
for certain moduli of special form (which happen to include the Mersenne
numbers), one can use additional clever tricks to avoid the zeropadding.
That's because a lengthn discrete cyclic convolution (working with baseX
inputs, where X need not be 10) is really a polynomial multiplication
modulo X^n  1. That means that in my example, if I had used a length2
DFT instead of length4 (and recall that I was using X = 10), I would have
still obtained the correct result, but only in the sense that it is correct
modulo 10^2  1 = 99. Let's try it:
We again DFTmultiply 12 and 23 using base10 arithmetic,
but this time we don't pad our input vectors with zeros.
Thus, our input vectors are A = (2,1) and B = (3,2), where the
leastsignificant digit of each number is leftmost. The Fourier transform
of a length2 vector (a,b) is given in matrixmultiply form as
[code:1]
+1 +1 a a+b
+1 1*b=ab .
[/code:1]
Doing this for our two input vectors, our transformed vectors are
A^ = (3, 1) and B^ = (5, 1). The Fouriertransformed discrete
convolution of A and B is then simply A^*B^, where the '*' means dyadic
multiply, which gives (15, 1). To get the digits of the product
we're after, we need to inverseFouriertransform this vector. For length2
vectors, the IFT looks just like the FT, but with a factor of onehalf
multiplying the whole thing.
That is, the length2 IFT of our vector (15, 1) has entries (16, 14)/2 = (8, 7).
Since all the output digits happen to be < 10 and nonnegative, we don't
need to do any carry step, and since the outputs are leastsignificant
first, our result (written in normal decimal order) is 78. The exact
(full) product is 12*23 = 276, which indeed == 78 modulo 99.
Ernst