FFT explanation for non math guys

[Chaos]

I have written a program that takes (N*log2(N)) bit operations to multiply 2 N digit numbers. My question is that what else does Prime95 use to multiply so fast. Could some one explain how to make the program a bit faster? What are the techniques called, any good resources?

[DJones]

Originally Posted by ewmayer

No, for length-6 DFT-based multiply your fundamental root of unity is not e^(i*2*pi/4) = i but rather e^(i*2*pi/6) = (1 + i*sqrt(3))/2. Call this quantity E and replace all the i's in your matrix by E's and that's the desired DFT matrix. Of course there are several symmetries you can exploit to simplify the the structure of the matrix. If E := e^(i*2*pi/n), then

1) E^j = E^(j%n), e.g. E^25 = E^(25%6) = E^1 = E;
2) E^3 = -1.

Using these, the 6x6 DFT matrix can be written as

| +1   +1   +1  +1   +1   +1 |
| +1    E  E^2  -1   -E -E^2 |
| +1  E^2   -E  +1  E^2   -E |
| +1   -1   +1  -1   +1   -1 |
| +1   -E  E^2  +1   -E  E^2 |
| +1 -E^2   -E  -1  E^2    E |

I'm new to all this and never had the option of studying natural logs, imaginary numbers, and so on - I know what they all are but can't explain them and have no comprehension about how they interact. I'm currently trying to track down good information on the web, but most of it seems to assume that you know all about it already, know what all the symbols they are using actually mean, and just need to be reminded of the formulas again. I will be resorting to getting some decent books at some point, but money's tight. Anyway, back to the point.
Does the above generation of the transform matrix need to be altered for working in a different base, or is it simply a case of converting your decimal number to the desired base and taking the length of the number in the new base as the defining factor* for the size of the transform matrix which in turn is still generated as above?

*If you'll pardon the pun.

[ewmayer]

Originally Posted by DJones

Does the above generation of the transform matrix need to be altered for working in a different base, or is it simply a case of converting your decimal number to the desired base and taking the length of the number in the new base as the defining factor for the size of the transform matrix which in turn is still generated as above?

The transform part of the FFT-based multiply is base-independent . The base appears in the transform-based multiply in two ways:

1) The base appears explicitly in the carry step following the IFFT, and

2) The base appears implicitly in the precision-dependent limits on the sizes of inputs to the FFT.

But the actual core FFT routines are base-independent.

[DJones]

Marvellous, thank you. Now any chance of being pointed at a suitable site / book (preferably the former) which explains why powers of e^(i * 2 * pi / n) work as a Fourier Transform matrix. Yes, I appreciate I could google this and have done so, but mathematical functions and definitions tend to be very flexible on the web, which isn't surprising when you take into account the fact that any idiot can put a webpage up.

I also appreciate I'm coming at this from the wrong end - I stumbled across the Mersenne Primes when looking for a DC project to get involved in, and have tried to backtrack through the proofs and methods so that I understand what's going on. Unfortunately backtracking through proofs, as opposed to building on proofs you already have, is proving to be rather convoluted.

[Prime95]

Originally Posted by DJones

Now any chance of being pointed at a suitable site / book (preferably the former) which explains why powers of e^(i * 2 * pi / n) work as a Fourier Transform matrix. Yes, I appreciate I could google this and have done so, but mathematical functions and definitions tend to be very flexible on the web.

Try googling "roots of unity" instead.

[fetofs]

I tried to use the fft function that came with the matrix package (numpy) of python (If I can't even use a pre-made, how can I write one?). First I made a stupid error, and then I got it to work. I then realized it returned results like:

myfft(987654321, 123456789) -> 121932631112626272
987654321*123456789         -> 121932631112635269

Are the imprecisions normally that big? If so, how do you fix it? Or it just doesn't matter?

[fivemack]

Originally Posted by fetofs

I tried to use the fft function that came with the matrix package (numpy) of python (If I can't even use a pre-made, how can I write one?). First I made a stupid error, and then I got it to work. I then realized it returned results like:

myfft(987654321, 123456789) -> 121932631112626272
987654321*123456789         -> 121932631112635269

Are the imprecisions normally that big? If so, how do you fix it? Or it just doesn't matter?

No, the calculation is generally exact - if any digit in the output ever comes out as further than 0.4 from its nearest integer then you start again with a longer FFT (that is, a smaller base).

I wonder whether you're transforming back from an array of digits to an integer using (double-precision) FP rather than exact integer arithmetic; could you post your code?

You should be doing the FFT on an array of at least eighteen entries if you're working with nine-digit inputs, set up with contents like
[0,0,0,0,0,0,0,0,0,9,8,7,6,5,4,3,2,1]

[science_man_88]

I said i couldn't understand but I've heard of FFT and next thing I know it's not even here. I'd love to learn it but I fear any explanation is above me. This thread shows up 7th for fft explanation on google already.

[science_man_88]

best thing I've found for visually seeing it is http://www.gweep.net/~shifty/portfol...eet/index.html

[ciic]

As Bagels usually have one - a hole - also, I might think, there's one in my own knowledge about the notation of the math.

'Cose: got me two books, first the famous one authored by Richard Crandall & Carl Pomerance: "Prime Numbers - A Computational Perspective" and 2nd a rather old book authored by Bruce, J.W, Giblin P.J., Rippon, P.J "Microcomputers and Mathematics" - with I found rather helpful and interesting.

My problem comes more with the first mentioned book by Crandall et al. it uses mathm. notations which I do not understand, e.g. an "=" with three horizontal lines and sum-signs and pi-signs and brackets...

Could someone please give me a hint, where I probaply could get information on this? Some "search-strings" for an extended google/amazon/wikipedia-search would also be very much helpful to me.

Cheers, ciic.

[axn]

http://en.wikipedia.org/wiki/List_of...atical_symbols

See: congruence, summation, product.