 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   faster than LL? (https://www.mersenneforum.org/showthread.php?t=20967)

 paulunderwood 2016-02-06 11:28

faster than LL?

[CODE]? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^N);gettime()
6132[/CODE]

[CODE]? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^q);gettime()
6125[/CODE]

The result of Mod(3,n)^q is a power of 2 less than 2^p-1 -- but only for Prime Mp? :smile:

 science_man_88 2016-02-06 13:30

[QUOTE=paulunderwood;425445][CODE]? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^N);gettime()
6132[/CODE]

[CODE]? gettime();p=44497;N=2^p-1;q=(N-1)/p;lift(Mod(3,N)^q);gettime()
6125[/CODE]

The result of Mod(3,n)^q is a power of 2 less than 2^p-1 -- but only for Prime Mp? :smile:[/QUOTE]

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 [url]http://mersenneforum.org/showpost.php?p=420686&postcount=2[/url] runs in under 29 seconds.

 axn 2016-02-06 13:40

[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 >[/CODE]

lift(Mod(3,N)^(N+1)) is, of course, 9, for primes.

 paulunderwood 2016-02-06 13:43

[QUOTE=science_man_88;425456]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 [url]http://mersenneforum.org/showpost.php?p=420686&postcount=2[/url] runs in under 29 seconds.[/QUOTE]

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.

 science_man_88 2016-02-06 13:49

[QUOTE=paulunderwood;425459]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. :smile:[/QUOTE]

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.

 paulunderwood 2016-02-06 13:57

[QUOTE=axn;425457][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 >[/CODE]

lift(Mod(3,N)^(N+1)) is, of course, 9, for primes.[/QUOTE]

Yes. All squarings. Pari maybe is not the best program to use to see the true differences.

 axn 2016-02-06 14:40

[QUOTE=paulunderwood;425462]Yes. All squarings. Pari maybe is not the best program to use to see the true differences.[/QUOTE]

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.

 paulunderwood 2016-02-06 14:46

[QUOTE=axn;425463]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.[/QUOTE]

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]

[CODE]? gettime();myfermat(110503);gettime()
time = 18,232 ms.
18232
? gettime();mylucas(110503);gettime()
time = 18,096 ms.
18096
[/CODE]

 science_man_88 2016-02-06 15:12

[QUOTE=paulunderwood;425464]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]

[CODE]? gettime();myfermat(110503);gettime()
time = 18,232 ms.
18232
? gettime();mylucas(110503);gettime()
time = 18,096 ms.
18096
[/CODE][/QUOTE]

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))[/CODE]

 science_man_88 2016-02-06 17:34

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.

 paulunderwood 2016-02-06 17:44

[QUOTE=science_man_88;425477]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.[/QUOTE]

Your's is marginally faster, modulo system activity, :smile:

All times are UTC. The time now is 07:56.