mersenneforum.org faster than LL?
 Register FAQ Search Today's Posts Mark Forums Read

 2016-02-06, 11:28 #1 paulunderwood     Sep 2002 Database er0rr 2×1,723 Posts faster than LL? Code: ? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^N);gettime() 6132 Code: ? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^q);gettime() 6125 The result of Mod(3,n)^q is a power of 2 less than 2^p-1 -- but only for Prime Mp?
2016-02-06, 13:30   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

202618 Posts

Quote:
 Originally Posted by paulunderwood Code: ? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^N);gettime() 6132 Code: ? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^q);gettime() 6125 The result of Mod(3,n)^q is a power of 2 less than 2^p-1 -- but only for Prime Mp?
it will depend on which version or coding of the LL test you use to test it against on my system for exponent 110503 your code runs for 1min, 29,975 ms. the lucas example takes about 2min, 17,097 ms. and the code from http://mersenneforum.org/showpost.ph...86&postcount=2 runs in under 29 seconds.

 2016-02-06, 13:40 #3 axn     Jun 2003 126C16 Posts Code: gp > p=44497; gp > N=2^p-1; gp > q=(N-1)/p; gp > r=N+1; gp > # timer = 1 (on) gp > lift(Mod(3,N)^N); time = 18,095 ms. gp > lift(Mod(3,N)^q); time = 18,032 ms. gp > lift(Mod(3,N)^r); time = 17,986 ms. gp > lift(Mod(3,N)^(N+1)) is, of course, 9, for primes.
2016-02-06, 13:43   #4
paulunderwood

Sep 2002
Database er0rr

1101011101102 Posts

Quote:
 Originally Posted by science_man_88 it will depend on which version or coding of the LL test you use to test it against on my system for exponent 110503 your code runs for 1min, 29,975 ms. the lucas example takes about 2min, 17,097 ms. and the code from http://mersenneforum.org/showpost.ph...86&postcount=2 runs in under 29 seconds.
29 seconds is because of the special mod 2^p==1 has been used. Try applying that to my fractional power Fermat PRP test!

The LL tests uses p-2 squarings and subtractions by 2 all mod 2^p-1. The test I give requires fewer squarings and some multiplications by 3 all mod 2^p-1.

Last fiddled with by paulunderwood on 2016-02-06 at 13:51

2016-02-06, 13:49   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts

Quote:
 Originally Posted by paulunderwood 29 seconds is because of the special mod 2^p==1 has been used. Try applying that to my fractional power Fermat PRP test! The LL tests uses p-2 squarings and subtractions by 2 all mod 2^p-1. The test I give requires fewer squarings and some multiplications by 3 all mod 2^p-1.
other than the fact I know x%(2^p-1) = x/(2^p)+x%(2^p) until there's at most p bits I'm not sure how to best do that here. edit: all I can think of is a loop like it's done for the LL code however if N is prime eulerphi(N) =N-1 so the exponent can be reduced to 1 I think as it's usually done mod eulerph if I remember correctly.

Last fiddled with by science_man_88 on 2016-02-06 at 13:57

2016-02-06, 13:57   #6
paulunderwood

Sep 2002
Database er0rr

D7616 Posts

Quote:
 Originally Posted by axn Code: gp > p=44497; gp > N=2^p-1; gp > q=(N-1)/p; gp > r=N+1; gp > # timer = 1 (on) gp > lift(Mod(3,N)^N); time = 18,095 ms. gp > lift(Mod(3,N)^q); time = 18,032 ms. gp > lift(Mod(3,N)^r); time = 17,986 ms. gp > lift(Mod(3,N)^(N+1)) is, of course, 9, for primes.
Yes. All squarings. Pari maybe is not the best program to use to see the true differences.

2016-02-06, 14:40   #7
axn

Jun 2003

22×32×131 Posts

Quote:
 Originally Posted by paulunderwood Yes. All squarings. Pari maybe is not the best program to use to see the true differences.
Yes. But even in a properly optimized program (like P95 or PFGW), all squaring will be slightly faster than modular exponentiation with exponents containing lots of 1 bits (I think). Also, all the tests are still probable-primality only (unlike LL test). And the saving of log(p) bits (about 25 bits at current GIMPS LL tests) is just rounding error in the grand scheme of things. One extra OS interrupt, and you won't be able to tell the difference.

EDIT:- Not to mention the cost of computing q=(N-1)/p.

Last fiddled with by axn on 2016-02-06 at 14:42

2016-02-06, 14:46   #8
paulunderwood

Sep 2002
Database er0rr

2·1,723 Posts

Quote:
 Originally Posted by axn Yes. But even in a properly optimized program (like P95 or PFGW), all squaring will be slightly faster than modular exponentiation with exponents containing lots of 1 bits (I think). Also, all the tests are still probable-primality only (unlike LL test). And the saving of log(p) bits (about 25 bits at current GIMPS LL tests) is just rounding error in the grand scheme of things. One extra OS interrupt, and you won't be able to tell the difference. EDIT:- Not to mention the cost of computing q=(N-1)/p.
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

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

 2016-02-06, 17:34 #10 science_man_88     "Forget I exist" Jul 2009 Dumbassville 8,369 Posts okay I may have been testing with a virus scanner going that may explain things somewhat but I still get mine as faster with just chrome going. okay maybe I just think this is faster for some reason. never midn I quit I am never really helpful too many ways to play with codes. Last fiddled with by science_man_88 on 2016-02-06 at 17:36
2016-02-06, 17:44   #11
paulunderwood

Sep 2002
Database er0rr

2·1,723 Posts

Quote:
 Originally Posted by science_man_88 okay I may have been testing with a virus scanner going that may explain things somewhat but I still get mine as faster with just chrome going. okay maybe I just think this is faster for some reason. never midn I quit I am never really helpful too many ways to play with codes.
Your's is marginally faster, modulo system activity,

 Similar Threads Thread Thread Starter Forum Replies Last Post arbiter21 Information & Answers 17 2016-02-05 05:04 lidocorc Software 2 2008-11-08 09:26 bearnol Math 35 2005-10-12 14:33 1260 Miscellaneous Math 23 2005-09-04 07:12 clowns789 Miscellaneous Math 3 2004-05-27 23:39

All times are UTC. The time now is 05:23.

Wed Oct 28 05:23:30 UTC 2020 up 48 days, 2:34, 2 users, load averages: 1.74, 1.77, 1.58