Ya, I didn't think *that* part through. :)
When n=p (the LL test case with the size of the FFT and other things thrown
in) as opposed to n=2^p (my case), then things are a *lot* different.
> -----Original Message-----
> From: Lucas Wiman [mailto:[EMAIL PROTECTED]]
> Sent: Thursday, July 22, 1999 2:20 PM
> To: [EMAIL PROTECTED]
> Subject: Re: Mersenne: Squaring algorithm...
>
>
> > 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.
>
> Yes, the runtime is proportional to some number, but that
> number is *not*
> the number of digits (as n usually means)! It is the number
> we are squaring!
>
> Unfortunatly, this would be quite inefficient compared even
> with traditional
> multiplying techniques.
>
> -Lucas
> _________________________________________________________________
> Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
> Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
>
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
