On Thu, 22 Jul 1999, Blosser, Jeremy wrote:
> 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.
It runs in O(n log n) time where n is the number of digits in the number being
squared, not the number being squared itself.
Given any algorithm for squaring, there is an algorithm for multiplying that
runs at the same speed to within a constant factor, and vice versa. Squaring is
multiplying a number by itself, and multiplying can be done by subtracting the
square of the difference from the square of the sum and dividing by 4.
phma
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
