mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-11-25, 16:17   #45
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

BE216 Posts
Default

As I'm working slowly through the ranges I'm starting to see some odd behaviour. Specifically, some ranges (of 10-million exponents) are finding approximately 15000 factors but other close ranges are only finding about half of that. For example:
Code:
Range   Candidates    Factored    Unfactored   Factors in 20000<k<100000
2130M       464,860     156,532       308,328     15,644 
2140M       465,831     154,327       311,504     13,301 
2150M       465,334     147,582       317,752      7,336 
2160M       465,180     147,187       317,993      7,204
The lack of newly-found factors is not because factors have been previously found, you can see that there is really just fewer candidates factored in some ranges. I thought perhaps my code was misbehaving (which it yet might be), but running in other ranges there has been no dropoff in factor rate:
Code:
Range   Candidates    Factored    Unfactored   Factors in 20000<k<100000
1050M       481,207     169,206       312,001     16,183 
1060M       481,433     164,587       316,846     16,218 
1070M       480,645     164,706       315,939     16,263 
1080M       481,153     164,910       316,243     16,275 
                                    
1590M       471,866     160,013       311,853     15,984 
1600M       471,784     159,748       312,036     16,124 
1610M       471,178     159,317       311,861     15,697 
1620M       471,758     159,554       312,204     15,660
Any ideas why this might be?

edit: the dropoffs are visible in the graph, notably the sharp drop around 2140M as noted above.

Last fiddled with by James Heinrich on 2012-11-25 at 16:39 Reason: fixed: ranges are 10-million, not 1-million
James Heinrich is offline   Reply With Quote
Old 2012-11-25, 16:57   #46
axn
 
axn's Avatar
 
Jun 2003

37×127 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
edit: the dropoffs are visible in the graph, notably the sharp drop around 2140M as noted above.
Just a guess: 2140M ~= 2^31, where things start to overflow 32 bit signed integer. All your factors for exponents above 2^31 are rubbish! Please recheck everything above 2147483648 /Just a Guess

Last fiddled with by axn on 2012-11-25 at 16:59
axn is online now   Reply With Quote
Old 2012-11-25, 18:22   #47
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2×32×132 Posts
Default

Quote:
Originally Posted by axn View Post
Just a guess: 2140M ~= 2^31, where things start to overflow 32 bit signed integer. All your factors for exponents above 2^31 are rubbish! Please recheck everything above 2147483648 /Just a Guess
The cutoff point is suspiciously close to 2^31, but I'd be surprised if PARI (32-bit version notwithstanding) would stumble on that? For what it's worth, I'm using PARI both to generate the factors on my home computer, and then again to verify them upon submission to my server, and no factor has been rejected for being invalid.

As one check, I ran through 100 exponents at 2150M (that had been declared no-factor up to k=99999 by PARI) using mfaktc up to 2^65. I did find one small factor in that range that should have been caught, but for some reason was not. Unfortunately I've deleted the source file that was used to generate that range, but I'm re-creating it now...

<sudden flash of realization> :surprised

I think I may know the source of the problem... as stated elsewhere I'm using PHP to generate the PARI code, and I've moved the selection of jumplist from PARI code to the PHP generating code for a little runtime speedup. Unfortunately, the PHP installation on my server is 32-bit and so when I'm checking p%60 that is where failure enters the scene. For example, the missed factor I found with mfaktc in my test above (M2,150,001,863) should have 2,150,001,863 mod 60 = 23. To get real weird, PHP can fail in 2 different ways:
Code:
echo ('2150001863' % 60); = 7
echo (2150001863 % 60); = -53
I had put a check in to catch unexpected values, and would have caught the -53 version, but it was apparently evaluated as a string input which gave a valid (but incorrect) mod value, resulting in a wrong selection of the jump list.
Fortunately the gmp_mod function is available and will work correctly on any size exponent. So now I can re-generate all the work above 2^31.

So none of the generated factors above 2^31 were wrong, but about half of the factors were missed.
Thanks axn for the kick in the right direction.
James Heinrich is offline   Reply With Quote
Old 2012-11-26, 01:38   #48
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

875710 Posts
Default

If you use some code related to the one in post #37 (with 60 classes split) then you may not use the right starting value for k? (multiple of 60? 20000 is not multiple of 60, you have to start with 19980, or rotate the vectors accordingly) (also just a guess).

edit: sorry, did not see your last post, I posted after axn's post (strange, the forum breaks the page at post #46, and I see post #47 as a new page, I am sure I selected 25 posts on page...)

Last fiddled with by LaurV on 2012-11-26 at 01:44
LaurV is online now   Reply With Quote
Old 2012-11-26, 01:44   #49
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

Quote:
Originally Posted by LaurV View Post
I am sure I selected 25 posts on page...)
No you didn't.
Dubslow is offline   Reply With Quote
Old 2012-11-26, 01:53   #50
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

BE216 Posts
Default

Quote:
Originally Posted by LaurV View Post
If you use some code related to the one in post #37 (with 60 classes split) then you may not use the right starting value for k? (multiple of 60? 20000 is not multiple of 60, you have to start with 19980, or rotate the vectors accordingly) (also just a guess).
No, I got that part right at least. In my generating code I put in my target starting k (e.g. 20000) and then it automatically rounds it down until it's mod60=0 (19980 in this case, as you said).

But I've now regenerated my assignment files and it seems to be happily finding all the factors it was missing before, so I'm happy.
James Heinrich is offline   Reply With Quote
Old 2013-01-02, 03:25   #51
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2×32×132 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
my plan is now to continue this up to k=100000 and squeeze a few more factors out. There's just slightly over 100-million candidates, and so far I'm getting about 4.8% factor rate, so I expect roughly 5-million factors at the end of this run. Candidate processing rate with PARI is approximately 5 candidates per second (per core). At this rate it'll take about 40 days (at 100% CPU and 24h/day, neither of which will actually happen, so probably about 100 real days).
It's done!

My two predictions were remarkably accurate. Today is 40 days after I posted that, and I found 5,099,114 factors using this method.
(disclaimer: that doesn't mean quite that many candidates were eliminated; those "extra" 100k factors probably accounts for the cases where multiple factors were found for k<100000)

Thanks again to everyone who helped me figure out this code.
James Heinrich is offline   Reply With Quote
Old 2014-04-11, 10:07   #52
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

32×7×139 Posts
Default

Sorry that I am waking up this topic. I searched for it in the light of this new discussion, I did not get the right thing I was searching for, but reaching this topic remembers me that I had implemented the "420 classes" not long after this discussion, doing a pari script to generate the vectors. The code might be useful to somebody, so I will include here. It is about 15% faster than the "60 classes" code described in the posts above. It also eliminates the restriction that the starting q be a multiple of 420. The version with 4620 classes would be slower because of overhead (hey! pari is not mfaktc!).

Somebody can use it for understanding how mfaktc works, or for TF-in small exponents which are outside of the mfaktc range (again, there are much faster programs there outside, this is not for "production" purposes).

tf420.gp.txt
[can't insert code, is over 10k characters limit]

Last fiddled with by LaurV on 2014-04-11 at 10:14
LaurV is online now   Reply With Quote
Old 2014-04-11, 11:00   #53
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

2·32·132 Posts
Default

Naysayers suitably ignored...

Thanks for your updated code. Yes, I'm still using your 60-class version even as I type this (taking 2000M-4000M from 251 to 252).
I'll go re-generate my assignment files with the 420-class version -- thanks!
James Heinrich is offline   Reply With Quote
Old 2014-04-23, 20:10   #54
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default same question for double mersenne numbers ?

I know that the form 2*k*p+1 stays the same for p=2^q-1; but if I form MMq into 2*j*(2*l*q+1)+1 the k value for this becomes:

Code:
(2*l + 1/q)*j
which forces j to be a multiple of q I believe , x*q;

converting the k value to:

Code:
(2*q*l + 1)*x
and:

Code:
(2*q*l + 1)*x + l
is the value of k for (2lq+1)*(2xq+1);

is there anything else that should be said about this value.

Last fiddled with by science_man_88 on 2014-04-23 at 20:41
science_man_88 is offline   Reply With Quote
Old 2014-04-23, 21:57   #55
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
...q I believe...
"q I believe" is the new form of Q.E.D.?
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Distribution of Mersenne Factors tapion64 Miscellaneous Math 21 2014-04-18 21:02
Known Mersenne factors CRGreathouse Math 5 2013-06-14 11:44
A strange new (?) fact about Mersenne factors ChriS Math 14 2006-04-12 17:36
Factors of Mersenne Numbers asdf Math 17 2004-07-24 14:00
Factors of Mersenne numbers ? Fusion_power Math 13 2003-10-28 20:52

All times are UTC. The time now is 03:14.

Wed Sep 30 03:14:26 UTC 2020 up 20 days, 25 mins, 0 users, load averages: 2.06, 1.77, 1.64

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.