Fourier transform for LL test

[drew]

Hey All,

I'm contemplating trying my hand at implementing an LL algorithm on an FPGA, but I need a little bit better understanding of what the correct mathematical approach should be.

I have a good understanding of how a 'run-of-the-mill' FFT is implemented, but I understand there are optimizations that specifically apply to this type of testing, such as irrational bases and the math section of the GIMPS page mentions an 'all-integer weighted transform'?

Can you point me in the right direction in trying to understand what this refers to? I assume an all-integer approach is better suited to an FPGA than the floating point implementation Prime95 uses. But what's a 'weighted' transform, and how does this speed up the process? I tried searching online and didn't find anything very descriptive.

If anyone can offer some direction or let me know what an appropriate approach would be is, I'd really appreciate it.

Thanks,
Drew

[jasonp]

Originally Posted by drew

Can you point me in the right direction in trying to understand what this refers to? I assume an all-integer approach is better suited to an FPGA than the floating point implementation Prime95 uses. But what's a 'weighted' transform, and how does this speed up the process? I tried searching online and didn't find anything very descriptive.

google

The paper by Crandall and Fagin (on the wikipedia page) goes into a lot of detail. Basically, multiplication mod a mersenne number involves wrapping the high half of the product around to the low half. Ordinary convolution does that for free if you don't zero-pad, *if* the size to be convolved is the size of the Mersenne number. A weighted transform lets you do the same wrapping around for free, but lets you choose the size of the convolution for maximum efficiency.

jasonp

[drew]

Originally Posted by jasonp

google

The paper by Crandall and Fagin (on the wikipedia page) goes into a lot of detail. Basically, multiplication mod a mersenne number involves wrapping the high half of the product around to the low half. Ordinary convolution does that for free if you don't zero-pad, *if* the size to be convolved is the size of the Mersenne number. A weighted transform lets you do the same wrapping around for free, but lets you choose the size of the convolution for maximum efficiency.

jasonp

Thanks for that...I didn't notice the link at the bottom to that .pdf last time I saw that page.

Drew