mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2011-08-11, 17:23   #34
axn
 
axn's Avatar
 
Jun 2003

10011001001012 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
flaw:

Code:
(13:13)>binary(128)
%15 = [1, 0, 0, 0, 0, 0, 0, 0]
(13:18)>[1,0,0]+[0,0,0]
%16 = [1, 0, 0]
(13:18)>128%7
%17 = 2
(13:19)>2^3-1
%18 = 7
also I don't see how you get the last equation. according to you to do 128 mod (7=2^3-1) I take 100 + 000 = 100 and solve it as 4 but 128 = (2*49) + (4*7) +2 so the correct result is 2.
you should group the bits in 3, starting from the right and working to the left. so the right way is [0,1,0] + [0,0,0] + [0,0,0].

PS:- for LL testing, there will only be two groups of bits -- can you say why?
PPS:- can you relate this to divisibility rule for 9? can you generalize it from this?
axn is offline   Reply With Quote
Old 2011-08-11, 18:03   #35
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by axn View Post
you should group the bits in 3, starting from the right and working to the left. so the right way is [0,1,0] + [0,0,0] + [0,0,0].

PS:- for LL testing, there will only be two groups of bits -- can you say why?
PPS:- can you relate this to divisibility rule for 9? can you generalize it from this?
AXN it's not what they said they said add the lower and higher n bits only.

re:PS:yes because x never gets above p^2 which will have at most 2n bits ?
re:PPS:no to both.

Last fiddled with by science_man_88 on 2011-08-11 at 18:05 Reason: PS was originally no
science_man_88 is offline   Reply With Quote
Old 2011-08-11, 22:52   #36
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

2×5×53 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
re:PPS:no to both.
Yes to both. Minor hint: 9 = 10^1 - 1
ckdo is offline   Reply With Quote
Old 2011-08-12, 00:07   #37
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by ckdo View Post
Yes to both. Minor hint: 9 = 10^1 - 1
so in other words the mersennes follow the same test for all repunits 99=10^2-1 and can be tested with a similar test even though it's clearly a multiple of 9
science_man_88 is offline   Reply With Quote
Old 2011-08-12, 01:48   #38
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

2×5×53 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
also I don't see how you get the last equation. according to you to do 128 mod (7=2^3-1) I take 100 + 000 = 100 and solve it as 4 but 128 = (2*49) + (4*7) +2 so the correct result is 2.
Getting back to the 128 % 7 example:

12810 % 710 = 2008 % 78 = 28 + 08 + 08 = 28 = 210.

Or, if you prefer binary (leading zeroes and spaces added for clarity):

12810 % 710 = 010 000 0002 % 1112 = 0102 + 0002 + 0002 = 0102 = 210.
ckdo is offline   Reply With Quote
Old 2011-08-12, 07:44   #39
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

33×347 Posts
Default

Quote:
Originally Posted by science_man_88 View Post

flaw:

also I don't see how you get the last equation. according to you to do 128 mod (7=2^3-1) I take 100 + 000 = 100 and solve it as 4 but 128 = (2*49) + (4*7) +2 so the correct result is 2.
There is no flaw, please check again your math.
You can write any number x as x=2n*a+b, by separating it in two parts, first n bits (from the right to the middle, somewhere) and the rest of the bits (from the middle to the left - first - most significant bit). This equation you can write like

x=2n*a-a+a+b

Then you group like:

x=(2n-1)*a+a+b

When you do mod m, with m=2^n-1, the paranthesis is gone and what you get left is y=a+b, where b are last n LSBits of x, and a is the rest of the MSBits.

Of course, if the result is bigger then m, you repeat the procedure until you get something smaller or equal to m (that fits on n bits). Please remark the "or equal" part. Because you always add positive numbers from which at least one is not null, you will never get 0. You will always get a number between 1 and m, inclusive, that is on binary (n bits) between 0...001 and 1...111, so in the case you got 1...111 then the modulus is 0. In the other cases, you got the right result.

Now if you do LL tests, as I said in the first post, you always square numbers smaller then m, so you will never get more then 2m bits, that means you have to do the procedure only once.

Examples (don't care where the numbers come from, either LL test, other calculus, my belly, etc):

55%31: 110111%11111=
(group 5 bits from the right)
1 10111 % 11111 =
(add the groups together)
1+10111 % 11111 = 11000
Decimal: 55%31=1+23=24 (mod 31) - the right result

165%15= 1010 0101 % 1111 = 1010+0101 = 1111 so 15 divides 165

961%31= 1111000001%31 = 11110 00001 %31 = 11111 - that is 0, so 31 divides 961

etc.

for your example, what you wrote down is 100 000 that is not 128, but 32 in decimal. Of course, 32 mod 7 makes 4.

Last fiddled with by LaurV on 2011-08-12 at 07:46
LaurV is offline   Reply With Quote
Old 2011-08-12, 08:07   #40
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

33×347 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
so in other words the mersennes follow the same test for all repunits 99=10^2-1 and can be tested with a similar test even though it's clearly a multiple of 9
I don't understand this part. GIMPS does not take any modulo operations in LL tests. P95 uses floating point FFT to square the numbers, which in return (in George's words) "it performs the modulo step for free". (see Math page on mersenne.org)
LaurV is offline   Reply With Quote
Old 2012-08-18, 15:15   #41
Damian
 
Damian's Avatar
 
May 2005
Argentina

2×3×31 Posts
Exclamation How to test your ANDROID cell phone warranty

Good? news! I migrated the old .jar code to android .apk
Now you can "test your android warranty" by downloading the lucas lehmer test from the market !!

I'm currently testing 2^{86243} - 1 on a SGS2, will post statistics when it finishes.

(Warning: use at your own risk, I didn't optimize the code and it is barely tested)
Damian is offline   Reply With Quote
Old 2012-08-18, 17:36   #42
Damian
 
Damian's Avatar
 
May 2005
Argentina

2·3·31 Posts
Default It finished!

Quote:
Originally Posted by henryzz View Post
1802 seconds/30 minutes to test 2^23209-1(M26) on one core of a Samsung Galaxy S II. Anyone ever tested higher?
Yes now:

2^{86243} - 1 is prime!!
Lasted: 9809679 miliseconds
(That is 2hs 43min 30sec, on my Samsung Salaxy S II)
Biggest prime number ever verified on a cell phone?
Anyone brave enough to surpass that record?

For comparison, I also tested 2^{23209} - 1:
2^{23209} - 1 is prime !!
Lasted: 196668 miliseconds
(That is 3 min 17 sec, MUCH faster than the half an hour it lasted on your converted .apk version)

I didn't optimize it, so I'm not sure why it is so much faster now. How do you know it only uses one core? It seems logical, but still I'm not sure.
Damian is offline   Reply With Quote
Old 2012-08-19, 14:35   #43
nucleon
 
nucleon's Avatar
 
Mar 2003
Melbourne

5·103 Posts
Default

ok, found the app on google play.

Tested M23209 on my HTC velocity 4G (1.5 GHz dual core)

197170ms

-- Craig
nucleon is offline   Reply With Quote
Old 2012-08-19, 20:01   #44
Damian
 
Damian's Avatar
 
May 2005
Argentina

18610 Posts
Default

tested m23209
on motorola xt610 lasted 717510ms
on chinese apad lasted 1264250ms
Damian is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cell Phone AstroPhotography Spherical Cow Astronomy 59 2019-01-21 22:47
IRS Phone Scam wblipp Lounge 0 2014-09-09 18:42
Masking a PIN over a phone call. Flatlander Puzzles 35 2013-10-31 10:34
Cell+ tha Hardware 1 2006-09-07 16:24
Prime95 on a cell phone JuanTutors Lounge 5 2004-08-18 08:53

All times are UTC. The time now is 08:48.

Tue Apr 13 08:48:02 UTC 2021 up 5 days, 3:28, 1 user, load averages: 1.43, 1.68, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.