Hello,
I'm trying to squeze a little more out of the L-L test, this
is my approach
(it might have been considert already, but I could not find
anyting in the web):
I basically want to perform two (a^2 - 2) steps at once.
conventional way:
FFT S
MULT S * S save result in F0 (in frequency domain)
IFFT F0
DEC F0, 2 S1 = S^2 - 2
FFT S1
MULT S1 * S1 save result in F1 (in frequency domain)
IFFT F1
DEC F1, 2 = S^4 - 4S^2 - 2
The new way:
I generate the two values:
S^4 and S^2 by
FFT S
MULT S * S save result in F0 (in frequency domain)
MULT F0*F0 save result in F1 (in frequency domain)
IFFT F0 = S^2
IFFT F1 = S^4
SHIFT S^2<<2 = 4*S^2 (bit shift)
DIFF S^4,4S^2
DEC result by 2 --> S^4 - 4S^2 - 2
What do we save compared to the conventional way:
standard | new
FFT 2 | 1
IFFT 2 | 2
MULT 2 | 2
DEC 2 | 1
SHIFT 0 | 1
DIFF 0 | 1
So we would save 1 FFT transform for the expense of a SHIFT(cheap?) and
a DIFF of two numbers with a size of (2^n - 1).
I guess this DIFF should be considerable cheaper than the FFT transform.
Ambitious guess 20% speedup?
Okay, you need the double amount of memory, and maybe an additional MOD
but it might be worth thinking about it.
sl
Martin
--
"Sie haben neue Mails!" - Die GMX Toolbar informiert Sie beim Surfen!
Jetzt aktivieren unter http://www.gmx.net/info
_______________________________________________
Prime mailing list
[EMAIL PROTECTED]
http://hogranch.com/mailman/listinfo/prime
