mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-02-06, 11:28   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

DB116 Posts
Default 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?
paulunderwood is offline   Reply With Quote
Old 2016-02-06, 13:30   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
science_man_88 is offline   Reply With Quote
Old 2016-02-06, 13:40   #3
axn
 
axn's Avatar
 
Jun 2003

4,789 Posts
Default

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.
axn is offline   Reply With Quote
Old 2016-02-06, 13:43   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

DB116 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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
paulunderwood is offline   Reply With Quote
Old 2016-02-06, 13:49   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
science_man_88 is offline   Reply With Quote
Old 2016-02-06, 13:57   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default

Quote:
Originally Posted by axn View Post
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.
paulunderwood is offline   Reply With Quote
Old 2016-02-06, 14:40   #7
axn
 
axn's Avatar
 
Jun 2003

4,789 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
axn is offline   Reply With Quote
Old 2016-02-06, 14:46   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

66618 Posts
Default

Quote:
Originally Posted by axn View Post
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
paulunderwood is offline   Reply With Quote
Old 2016-02-06, 15:12   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 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
Old 2016-02-06, 17:34   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2016-02-06, 17:44   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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,
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is it faster to run 1 worker or many? arbiter21 Information & Answers 17 2016-02-05 05:04
My CPU is getting faster and faster ;-) lidocorc Software 2 2008-11-08 09:26
3-PRP faster than LL for GIMPS? bearnol Math 35 2005-10-12 14:33
Faster way to do LLT? 1260 Miscellaneous Math 23 2005-09-04 07:12
Faster than LL? clowns789 Miscellaneous Math 3 2004-05-27 23:39

All times are UTC. The time now is 11:42.

Fri Dec 4 11:42:06 UTC 2020 up 1 day, 7:53, 0 users, load averages: 2.01, 1.67, 1.56

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.