Just was thinking the other day about this... Forgive me if its been
discussed before etc.
Aren't there other "better" algorithms for finding the square of a number
besides using an FFT? Sure an FFT is great for multiplying two different
numbers, but for squaring a number isn't the case a little different. Plus,
going off what I've read on FFT's, it runs in O(n log n) time.
So wouldn't a summation algorithm work better.
For example, to find the square of a number k take the sum of n=1 to n=k of
2n-1.
So 3**2 is 1+3+5 = 9
4**2 is 1+3+5+7 = 16
etc...
So the sqaure performs in O(n) time. Plus, you could already throw in the
sub 2 by starting at -1 instead of 1. And figuring out the mod is just as
easy.
k is the sum of n=2**p-1 to n=k of 2n-1 (This would give k**2 - 2**p-1).
The only hassle is adding *big* numbers up, but I'm not sure how the
ramifications of doing carries across boundaries and such would factor into
the equation etc.
Just a thought.
-Jeremy
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
