>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?
It is not stupid, it is in fact the normal way of squaring a small number. The
reason humongous numbers are squared with FFT is that shift-and-add takes
O(n^2) bit operations, where n is the number of bits in the number being
squared, whereas FFT takes O(n*ln(n)*ln(ln(n))), which is a lot
faster. The FFT of n floats takes log_2(n) stages, each of which runs through
the array once which takes n operations; the ln(ln(n)) term (please correct me
if this term is wrong) is because the more bits there are in the number you are
squaring, the more precisely you need to compute the floats in the FFT.
phma
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
