How many ways can you code an LL test - Page 2

science_man_88 · 2016-01-01, 16:23

Quote:

Originally Posted by xilman

Countably infinite.

okay then what's the absolute fastest way you can code it.

ewmayer · 2016-01-02, 04:14

Quote:

Originally Posted by science_man_88

okay then what's the absolute fastest way you can code it.

If by 'fast' you are referring to execution speed of the tests, several of us have been working on that for many years, and continue to do so. You are welcome to compare timings of your efforts to ours.

If OTOH by 'fast' you mean 'speed of coding it up', then you got us beat, hands-down. (But only if you neglect the coding time others put into the bignum package you are using.)

science_man_88 · 2016-01-02, 12:48

Quote:

Originally Posted by ewmayer

If by 'fast' you are referring to execution speed of the tests, several of us have been working on that for many years, and continue to do so. You are welcome to compare timings of your efforts to ours.

If OTOH by 'fast' you mean 'speed of coding it up', then you got us beat, hands-down. (But only if you neglect the coding time others put into the bignum package you are using.)

mine are all PARI/gp and suck even compared to the lucas example.

science_man_88 · 2016-01-02, 15:51

I've thought about the fact that in the squaring version if $s_n=a{M_n}$ then $s_{n+1}=a^2{M_n}^2-2$ which mod the next mersenne number is $a^22^{n-1}-2$ but that's not all that helpful when a's value is the larger part of that typically and in the $s_n=2{s_{n-1}}^2-1$ version(s) of the test you can find the relation that the next value is also $2{s_{n-1}-1}^2+4{s_{n-1}-1}+1$ which is like the way mersenne numbers that have exponents in a cunningham chain of the first kind follow but I have a hard time finding a useful relationship to use to mod that one.

science_man_88 · 2018-08-22, 18:25

Here's another crappy version:

Code:

LL(p)=my(s=Mod(2,2^p-1));for(x=1,p-2,s=vecprod([2,s-1,s+1])+1);s

ewmayer · 2018-08-22, 21:25

Crappy-performing but functional bc code:

Code:

define lltest(p) {
	auto i,m,r; i = p-2; m = 2^p-1; r = 4;
	while(i--) {
		r = (r^2-2)%m;
	}
	return(r==0);
}

paulunderwood · 2018-08-22, 22:18

In Ruby....

Code:

def LL(p)
  s, n = 4, 2**p-1
  3.upto(p) { s=(s**2-2)%n }
  s==0
end

print "LL exponent : "
p = gets.to_i
puts LL(p)

GP2 · 2018-08-22, 22:34

Earlier in the thread someone mentioned the Rosetta Code page, with dozens of languages. None particularly efficient, though.

http://rosettacode.org/wiki/Lucas-Lehmer_test

paulunderwood · 2018-08-22, 22:47

Quote:

Originally Posted by GP2

Earlier in the thread someone mentioned the Rosetta Code page, with dozens of languages. None particularly efficient, though.

http://rosettacode.org/wiki/Lucas-Lehmer_test

Ah! I did not handle exponent 2. Also (p-2).times maybe neater then 3.upto(p).

I guess the linked page is too small for George's source

ewmayer · 2018-08-23, 23:06

Quote:

Originally Posted by paulunderwood

Ah! I did not handle exponent 2.

No need - LL assumes p an odd prime.

2016-01-02, 15:51	#15
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶·131 Posts	I've thought about the fact that in the squaring version if $s_n=a{M_n}$ then $s_{n+1}=a^2{M_n}^2-2$ which mod the next mersenne number is $a^22^{n-1}-2$ but that's not all that helpful when a's value is the larger part of that typically and in the $s_n=2{s_{n-1}}^2-1$ version(s) of the test you can find the relation that the next value is also $2{s_{n-1}-1}^2+4{s_{n-1}-1}+1$ which is like the way mersenne numbers that have exponents in a cunningham chain of the first kind follow but I have a hard time finding a useful relationship to use to mod that one. Last fiddled with by science_man_88 on 2016-01-02 at 15:53

2018-08-22, 18:25	#16
science_man_88 "Forget I exist" Jul 2009 Dumbassville 2⁶×131 Posts	Here's another crappy version: Code: LL(p)=my(s=Mod(2,2^p-1));for(x=1,p-2,s=vecprod([2,s-1,s+1])+1);s

2018-08-22, 21:25	#17
ewmayer ∂²ω=0 Sep 2002 República de California 19·613 Posts	Crappy-performing but functional bc code: Code: define lltest(p) { auto i,m,r; i = p-2; m = 2^p-1; r = 4; while(i--) { r = (r^2-2)%m; } return(r==0); }

2018-08-22, 22:18	#18
paulunderwood Sep 2002 Database er0rr EB2₁₆ Posts	In Ruby.... Code: def LL(p) s, n = 4, 2p-1 3.upto(p) { s=(s2-2)%n } s==0 end print "LL exponent : " p = gets.to_i puts LL(p) Last fiddled with by paulunderwood on 2018-08-22 at 22:18

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
The Joys of Cracked.com: 5 Ways We Ruined the Occupy Wall Street Generation	Dubslow	Soap Box	17	2012-05-14 08:51
RDS's unique pedagogic ways	R.D. Silverman	Soap Box	137	2012-01-07 07:52
ways to get rid of oil spills	science_man_88	Puzzles	9	2010-07-30 21:22
Help needed to test Athlon64 code	geoff	Programming	7	2006-08-18 12:16
Creative ways to achieve Athlon 64 / Opteron optimization	GP2	Hardware	11	2004-01-21 03:01

2018-08-22, 22:34	#19
GP2 Sep 2003 A19₁₆ Posts	Earlier in the thread someone mentioned the Rosetta Code page, with dozens of languages. None particularly efficient, though. http://rosettacode.org/wiki/Lucas-Lehmer_test