Hi, At 11:02 PM 7/30/2001 +0200, Jeroen wrote: >I just curious. >What is done and how long does it takes when my computer calculates S(n) = >S(n)*S(n) - 2 >Is it something like : > >40% of time - Do a FFT on the big number >10% of time - Do something with the result to multiply it with itself >40% of time - Do an inverse FFT to get a big number > 8% of time - Do a modulo 2^n-1 on the number > 2% of time - Substract 2 from the number > >Or is the modulo done in the FFT pass? Yes. This happens for free using Richard Crandall's discrete weighted transform. >Or do I have completely wrong timings? You're close. >Can somebody explain this a little more to me? The breakdown is roughly (if memory serves me :): 42% of time - Do a FFT on the big number 1% of time - Do something with the result to multiply it with itself 42% of time - Do an inverse FFT to get a big number 15% of time - Carry propogation. 0% of time - Do a modulo 2^n-1 on the number ( 0% of time - Substract 2 from the number Regards, George _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
