FFT explanation for non math guys

[Templus]

Thank you ewmayer for your great explanation , though it's an old topic . I'm astonished with the fact how "easy" it is to calculate in Fourier-space (with your example).

@Citrix:

If the numbers are 3-digit, then let the Vectors A and B of length 6 (2N)

make the 'i'-matrix as:

2N*2N matrix

|+1 +1 +1 +1 +1 +1| |i^0 i^0 i^0 i^0 i^0 i^0|
|+1 +i -1 -i +1 +i|=|i^0 i^1 i^2 i^3 i^4 i^5|
|+1 -1 +1 -1 +1 -1| |i^0 i^2 i^4 i^6 i^8 i^10|
|+1 -i -1 +i +1 -i| |i^0 i^3 i^6 i^9 i^12 i^15|
|+1 +1 +1 +1 +1 +1| |i^0 i^4 i^8 i^12 i^16 i^20|
|+1 +1 +1 -i +1 +i| |i^0 i^5 i^12 i^15 i^20 i^25|

or: M(j,k) = i^(k*j) and begin counting at 0.
j = row-number
k = column-number

And then follow the procedures (and divide by 6, the length of the Vector A (and B))

Am I right ?

[Templus]

some stupid mistakes:
M(5,1) = i^5 = +i
M(5,3) = i^10 = -1

Sorry, I couldn't find how to edit my post...

[ewmayer]

Originally Posted by Templus

Am I right ?

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 |

[xenon]

Can we go one step closer to LL testing using the multiplication methods described above? What is FFT length, eg 1024K, 1792K? What is radix?

[jfollas]

I'm still trying to get my head around multiplying using FFT's, but I have a couple questions that popped up:

As I understand, to multiply using FFT, you need to do a transform, perform the multiplication math, and then do an inverse transform to get the results back into a "real number".

What if I wanted to do repeated squarings? Would I need to perform the inverse transform and then another transform before multiplying the second and sequential times? Or, once I have the number in the frequency domain, can I keep performing the multiplication math for as many squarings as I need, and then do the inverse transform?

Also along the same lines, does Prime95 need to perform the inverse transform before subtracting 2 each iteration of the LLT?

[xenon]

I believe it is very logical to perform the multiplications without inverse transforms in between. But not for addition (or subtractions).

[ColdFury]

You need to do the inverse transform and rounding step each time if you want to keep the precision errors under control.

[jfollas]

Originally Posted by ColdFury

You need to do the inverse transform and rounding step each time if you want to keep the precision errors under control.

Is there a FFT implementation that would be better suited for repeatedly performing the multiplication step while remaining in the transform (i.e., where precision errors are not an issue), or at least not requiring an inverse transformation with every iteration? An Integer FFT perhaps?

[R.D. Silverman]

Originally Posted by jfollas

Is there a FFT implementation that would be better suited for repeatedly performing the multiplication step while remaining in the transform (i.e., where precision errors are not an issue), or at least not requiring an inverse transformation with every iteration? An Integer FFT perhaps?

My integer FFT (actually polynomial convolution) code from
"AN FFT Extension to P-1" did exactly that.

The code won't do anyone much good now; it was written in ALLIANT
Fortran.

[xenon]

Can anyone explain "irrational base" as in IBDWT? I really don't understand the modulo step "for free".

The maths page of mersenne.org has dead links.
Also, I can't find the original paper: Crandall, R. E. and Fagin, B. 1994, Discrete weighted transforms and large-integer arithmetic, Math. Comp., 62, 205, 305-324(January)
Why is it not available for download?

[Guilherme]

This page provides an Excel spreadsheet that shows FFT multiplication:

http://www.gweep.net/%7Eshifty/portf...eet/index.html