Okay, I was sitting there the other day thinking about a non-FFT squaring
algorithm...
Say we have 14, which in binary is 1110...
If we left shift this by the position of the 1, for each 1 in the binary
representation, and add them together, we should get the square... So to
square 14, we do this:
1110 << 3 == 1110000 +
1110 << 2 == 0111000 +
1110 << 1 == 0011100 +
== 11000100 which is 196
So for each squaring, we have x left shifts and adds, where x is no larger
that p.
In any case... is this just me being dumb and missing that this is just a
stupid way of squaring a number?
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
