Thread: faster than LL? View Single Post
2016-02-06, 15:12   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by paulunderwood 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