Questions on coding my FFT&LLR implementation

[ewmayer]

Originally Posted by nuggetprime

The prev.code is totally broken. Sorry. Will attatch a new one probably tomorrow.

--Nuggetprime

Don't take this the wrong way, but do you think it's worth anyone's time to look at some little code you wrote that uses a guaranteed-to-be-horribly-slow implementation?

Until you teach yourself the rudiments of the FFT and actually code one up and then write at least an old-style LL test around it which zero-pads the inputs [i.e. doesn't require the DWT], there's no point whatsoever in asking the experts to look at your code - YOU'RE the one who needs to look at your code, unless you've got some highly specific coding or build issue you need advice on.

[nuggetprime]

You are completely right Ernst.And it's hard to insult me, so don't worry
I found a page on the web telling me for FFT i don't have to break off 1 time, but so many times that fftlen=2 and then recombine. That is the point I've forgotten.

Thanks,
nuggetprime

[nuggetprime]

I've now managed to code an FFT out of my DFT. It takes me ~0.5 seconds to do a length 8192-fft(with IFFT ~1 second). Still a very bad time. I don't ask to look at my code,but what is important to get normal speeds(at least ~0.3 ms/fft). That's a factor of 3000, so I'm sure I'm doing something pretty wrong. If I get asked, I can also post the code.

thanks,
nuggetprime

[ewmayer]

Originally Posted by nuggetprime

I've now managed to code an FFT out of my DFT. It takes me ~0.5 seconds to do a length 8192-fft(with IFFT ~1 second). Still a very bad time. I don't ask to look at my code,but what is important to get normal speeds(at least ~0.3 ms/fft). That's a factor of 3000, so I'm sure I'm doing something pretty wrong. If I get asked, I can also post the code.

thanks,
nuggetprime

Suggest you also get hold of the Numerical Recipes FFT code and compare the timings of that with yours. Don't worry about real-vs-complex FFT for now, you only want to get some gross order-of-magnitude timing comparisons.

[nuggetprime]

I got(probably) the right code. It's less than 50 lines, so i could probably understand it. But how to use it?(small example).

Thanks,
nugget

[ewmayer]

Specifically, you want the section titled "FFT of Single Real Function", i.e. the realft() code, and the functions called by that. That allows you to do both forward and inverse FFTs, so the general outline for a non-DWT-based LL test using this is;

0. Set a reasonable wordsize for DP-based arithmetic, say w = 16 bits per word.

1. Pick your real-double residue vector length. For a Mersenne exponent p and a power-of-2-length FFT implementation, this will be n = 2*2^ceiling[log2(p/w)], e.g. for p = 607 and w = 16, this gives n = 2*2^6 = 128. The leading multiply-by-2 here is to effect the zero-padding required by a non-DWT method.

2. Initialize your residue vector to have 4 in the lowest-order slot and zeros elsewhere.

3. Do a forward real-vector FFT.

4. Do a dyadic (a.k.a. pointwise) squaring of the forward FFT outputs

5. Do an inverse real-vector FFT.

6. Normalize the outputs of (5) by dividing each [call it x_i] by w, carrying y = nint(x_i/w) into x_i+1, and replacing x_i with w*[x_i - y)]. Add any carry out of the highest-order vector element back into x₀ and also subtract 2 form x₀.

7. Perform steps 3-6 precisely (p-2) times. If the result is the zero vector, 2^p-1 is prime, otherwise it's composite.

[nuggetprime]

After some time, I finally got a FFT working that's about 3 times as slow as gwnum.
I can understand the split-radix fft, but not how a real-data fft works. I've not found any explanatory material except of hard-to-read code. Can you please provide an explanation and a small example?

Thanks,
--nuggetprime

[cheesehead]

Originally Posted by nuggetprime

I can understand the split-radix fft, but not how a real-data fft works. I've not found any explanatory material except of hard-to-read code. Can you please provide an explanation and a small example?

So, you need more explanation and example than the "FFT explanation for non math guys" thread provides?

[nuggetprime]

Originally Posted by cheesehead

So, you need more explanation and example than the "FFT explanation for non math guys" thread provides?

The "FFT explanation for non math guys" thread doesn't provide an explanation about real-data fft.

--nuggetprime

[ewmayer]

Originally Posted by nuggetprime

I can understand the split-radix fft, but not how a real-data fft works. I've not found any explanatory material except of hard-to-read code.

Originally Posted by ewmayer

Specifically, you want the section titled "FFT of Single Real Function", i.e. the realft() code

The explanatory material you require is all in that section of NR.

[cheesehead]

Originally Posted by ewmayer

Specifically, you want the section titled "FFT of Single Real Function", i.e. the realft() code

Ernst, could you add either a link to, or a summary or an explanation of what nuggetprime needed to the "FFT explanation for non math guys" thread?