LL and FFT question - Page 2

ewmayer · 2011-05-05, 16:51

I should add one caveat to my assertions above: If one spends a significant time of a transform-based squaring in the DWT-weighting and output-normalization steps, then there might indeed be a modest savings from doing a longer FFT with smaller input words which allow for 2 or more dyadic multiplies in a row.

I haven't donw precise timings in a while but I seem to recall the typical overhead for the DWT-weight/unweight and normalize-and-propagate-carries is 10-20% of the overall modmul time.

For my Mlucas code, there is a roughly 10% additional overhead in Mersenne-mod mode due to "wrapper step" needed around the dyadic-mul, to convert the outputs of the fundamentally complex-input FFT I use to ones reflective of a real-vector FFT. (I didn't want to code 2 separate FFTs for e.g. Fermat-mod and Mersenne-mod arithmetic...Fermat-mod uses a straight complex FFT if one uses the right-angle-transform weighting trick).

cheesehead · 2011-05-05, 17:07

Quote:

Originally Posted by ewmayer

Fermat-mod uses a straight complex FFT if one uses the right-angle-transform weighting trick).

Careful! GIMPS may lose a lot of Republicans if that comment gets out!

2011-05-05, 16:51	#12
ewmayer ∂²ω=0 Sep 2002 República de California 19×613 Posts	I should add one caveat to my assertions above: If one spends a significant time of a transform-based squaring in the DWT-weighting and output-normalization steps, then there might indeed be a modest savings from doing a longer FFT with smaller input words which allow for 2 or more dyadic multiplies in a row. I haven't donw precise timings in a while but I seem to recall the typical overhead for the DWT-weight/unweight and normalize-and-propagate-carries is 10-20% of the overall modmul time. For my Mlucas code, there is a roughly 10% additional overhead in Mersenne-mod mode due to "wrapper step" needed around the dyadic-mul, to convert the outputs of the fundamentally complex-input FFT I use to ones reflective of a real-vector FFT. (I didn't want to code 2 separate FFTs for e.g. Fermat-mod and Mersenne-mod arithmetic...Fermat-mod uses a straight complex FFT if one uses the right-angle-transform weighting trick).