Thread: faster than LL?
View Single Post
Old 2016-02-06, 15:12   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I see. Thanks for your analysis.

I coded it up by hacking Robert's script:

Code:
myfermat(p)=mp=2^p-1;q=(mp-1)/p;res=3;len=length(binary(q));forstep(i=len-2,0,-1,res=sqr(res);hi=shift(res,-p);lo=bitand(res,mp);res=lo+hi;if(bittest(q,i),res*=3);while(res>=mp,res-=mp);while(res<0,res+=mp))
Code:
? gettime();myfermat(110503);gettime()
time = 18,232 ms.
18232
? gettime();mylucas(110503);gettime()
time = 18,096 ms.
18096
see on my machine your code starts out at 33 seconds but I have been able to shave that to roughly <30 using some of the things I also posted in that LL thread I made ( at least on my system).

Code:
myfermat(p)=mp=2^p-1;q=mp\p;res=3;len=length(binary(q));forstep(i=len-2,0,-1,res=sqr(res);hi=res>>p;lo=bitand(res,mp);res=lo+hi;if(bittest(q,i),res*=3);while(res>=mp,res-=mp);while(res<0,res+=mp))

Last fiddled with by science_man_88 on 2016-02-06 at 15:12
science_man_88 is offline   Reply With Quote