mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-11-21, 19:35   #23
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

32·19·23 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
just found a logic error 10000 is 0 mod 4 a class you don't want so the first number should be 10002 not 10000 sorry. it still should take about the same though.
I'm not sure I agree with you. I think 10002 (10002%4==2) is the one value I wouldn't want to use (going right back to the footnote in my first post). I can give you a bunch of examples of known factors with k=10000, 10001 or 10003 but none with k=10002.
James Heinrich is offline   Reply With Quote
Old 2012-11-21, 20:17   #24
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
I'm not sure I agree with you. I think 10002 (10002%4==2) is the one value I wouldn't want to use (going right back to the footnote in my first post). I can give you a bunch of examples of known factors with k=10000, 10001 or 10003 but none with k=10002.
oh I see now I forgot that != was not equals , you are correct. now you can use other knowledge to maybe get it down further.

Last fiddled with by science_man_88 on 2012-11-21 at 20:24
science_man_88 is offline   Reply With Quote
Old 2012-11-21, 21:18   #25
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

1111010111012 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
However your forstep change did provide a 10% performance improvement, so that's a good start.
Actually I don't think this is useful. It's faster because it's skipping k values in a way I don't think it should be. If I change
Code:
forstep(k=20000,99999,[1,3],
to
Code:
forstep(k=19999,99999,[1,1,2],
it replicates the functionality of
Code:
if(k%4==2,k++);
but also negates the speed improvement.
James Heinrich is offline   Reply With Quote
Old 2012-11-21, 21:34   #26
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Actually I don't think this is useful. It's faster because it's skipping k values in a way I don't think it should be. If I change
Code:
forstep(k=20000,99999,[1,3],
to
Code:
forstep(k=19999,99999,[1,1,2],
it replicates the functionality of
Code:
if(k%4==2,k++);
but also negates the speed improvement.
the jump values depend on the start value. since 10000 mod 4=0 we want 10000,10001,10004,10005, since 19999 is 3 mod 4 and we get 19999,20000,20001,20003, with the jumps which don't fit 0 or 1 mod 4 we can prove some of these not needed to be checked.
science_man_88 is offline   Reply With Quote
Old 2012-11-21, 21:58   #27
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

32×19×23 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
with the jumps which don't fit 0 or 1 mod 4 we can prove some of these not needed to be checked.
Going back to rcv's post #7 above I see where you're going with your jump values. [1,3] is appropriate for 4294949947 because it's mod4=3, but I would need to swap that to [3,1] if p%4==1, such as for 4294899893:
Code:
// This shows us that if (p mod 4) == 1, then k must equal 0 or 3 (modulo 4).
p=4294899893; forstep(k=10000, 19999, [3,1], q=2*k*p+1; if((q%8==1||q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;));

//                and if (p mod 4) == 3, then k must equal 0 or 1 (modulo 4).
p=4294949947; forstep(k=10000, 19999, [1,3], q=2*k*p+1; if((q%8==1||q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;));
James Heinrich is offline   Reply With Quote
Old 2012-11-21, 22:04   #28
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Going back to rcv's post #7 above I see where you're going with your jump values. [1,3] is appropriate for 4294949947 because it's mod4=3, but I would need to swap that to [3,1] if p%4==1, such as for 4294899893:
Code:
// This shows us that if (p mod 4) == 1, then k must equal 0 or 3 (modulo 4).
p=4294899893; forstep(k=10000, 19999, [3,1], q=2*k*p+1; if((q%8==1||q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;));

//                and if (p mod 4) == 3, then k must equal 0 or 1 (modulo 4).
p=4294949947; forstep(k=10000, 19999, [1,3], q=2*k*p+1; if((q%8==1||q%8==7) && (lift(Mod(2,q)^p) == 1), print("M"p" has a factor: "q); break;));
actually what I was talking about was that since jumping [1,3] repeatedly from 19999 doesn't come to all possible values of k that could lead to a prime q, it doesn't hit all possible factors, so it could miss some factors 19999%4=3 3+1 = 0 mod 4 0+3 = 3 mod 4 so this only hits 0 and 3 mod 4 we need to hit 0 and 1 mod 4 that means to get into the 1,3 we need to jump 2 once and only once first. we need a value that fits the criteria to work the easiest with a forstep any value only works easy with a normal for loop. even with 1,1,2 we get 3,0,1,... repeating mod 4 we test 3/4 values when with we could cut it down to 2/4 ( in fact using mod 120 we can get it as low as 32/120 maybe lower),

Last fiddled with by science_man_88 on 2012-11-21 at 22:11
science_man_88 is offline   Reply With Quote
Old 2012-11-22, 09:52   #29
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

1024610 Posts
Default

@James, a side question, as I am sure you are reading this thread: are you still working on those P-1 assignments on 2M range which are about 40 days overdue? I can see them in the team assignments and I just want to make sure is not some old forgotten task, you may have deleted the worktodo or whatever. [edit: there are also in 1M range about 20 assignments totally, pretty old, that i7-920 should finish everything in one-two days or so]

Last fiddled with by LaurV on 2012-11-22 at 09:55
LaurV is offline   Reply With Quote
Old 2012-11-22, 12:16   #30
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

D5716 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Going back to this thread after some time, I've been playing with my PARI code and trying to incorporate some of the ideas presented here
What is your goal? Do you want to trial factor large mersenne numbers? Then mfactor is pretty fast I think: http://www.mersenneforum.org/showthread.php?t=4939



To speed up you need to trial factor the candidate factors 2kp+1 and only try those that survives.

You can make a binary array of k-values up to some limit say 1e6 or 1e8, and then sieve them up to some limit.

For each sieveprime you find the lowest k-value where 2kp+1 = 0 (mod sieveprime) using Extended Euclidean algorithm.

Here the input is your exponent p and your current sieveprime and output is that lowest k-value where sieveprime is a factor of 2kp+1. Now you can remove all these values from your k-array: k, k+2p, k+4p, k+6p ... since they all have the factor: sieveprime. You run this for all sieveprime up to some limit maybe 10^4 or 10^5 and then you can trial factor 2kp+1 in Mp for the remaining k-values in your array.


a, b, x, y, lastx, lasty, tempx, tempy, quot, rem are all temporary variables.
Code:
a=p; b=sieveprime; lastx=1; lasty=0; x=0; y=1;
if (a%b!=0)
{
	do
	{
		quot=a/b; rem=a%b;
		tempx=lastx-quot*x;
		tempy=lasty-quot*y;
		a=b; b=rem; lastx=x; lasty=y; x=tempx; y=tempy;
	} while(rem!=1);
	x=0-x;
	if (x<0) { x=x+sieveprime; }
	if ((x%2)==1) { x=x+sieveprime; }
	k=x/2;
}
ATH is offline   Reply With Quote
Old 2012-11-22, 14:32   #31
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

D5716 Posts
Default

Quote:
Originally Posted by ATH View Post
Now you can remove all these values from your k-array: k, k+2p, k+4p, k+6p ... since they all have the factor: sieveprime.
Sorry, this is not right, it's of course: k, k+sieveprime, k+2*sieveprime, k+3*sieveprime, .... which can be removed from the k-array.
ATH is offline   Reply With Quote
Old 2012-11-22, 15:27   #32
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

280616 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
LaurV's nice description of primorial class filtering was unfortunately beyond my ability to translate into code.
Well, that is not complicate if you understand the process.

Trial factoring, part 1 of 3 (stating the obvious)

We take advantage of the fact that (1) p is prime, and (2) q is prime, and (3) q is 1 or -1 mod 8, and (4) q=2kp+1. The rest is filtering. If q is 1 or 7 (mod 8), then 2kp must be 0 or 6 (mod 8), so k*p must be 0 or 3 (mod 4). From the fact that p is prime, we have that p is 1 or 3 (mod 4), as it can't be even number. If p is 1 mod 4, then k can only be 0 or 3 mod 4, and if p is 3 mod 4, then k can only be 0 or 1 mod 4, otherwise the condition (3) fails. Let's put this discussion in a table, with a column for each possible p, and a line for each possible k, where the cells in the table are the modularity of q=2kp to 8. For example, if p=1 and k=2 (mod 4), then q=2*(4x+2)*(4y+1)=32xy+8x+16y+5, so q=5 (mod 8). Let's put his in the table, in excel is very simple.

Code:
       1    3
  0    1    1
  1    3    7  
  2    5    5
  3    7    3
Then we mark with gray the unacceptable q's. It is very easy to see that, assuming we start with a k which is a multiple of 4, we do not need to test all k's, and we can "skip" some of them. If p is 1 (mod 4), we first skip 3, then skip 1. If p is 3 (mod 4), we first skip 1, then skip 3.

Let's put this in a piece of pari code:
Code:
/* splitting p in two classes
   p must be a prime and fromk must be 0 (mod 4), no verification done, for speed reasons*/
tf_2c(p,fromk=0,tok=10000)=
{
    if(p%4==1,v=[3,1],
    if(p%4==3,v=[1,3],
    error("p must be odd (prime)")));
    forstep(k=fromk, tok, v, q=2*k*p+1; if(Mod(2,q)^p==1, if(q>1,print("M"p" has a factor: "q); break;)));
}

Last fiddled with by LaurV on 2012-11-22 at 16:03
LaurV is offline   Reply With Quote
Old 2012-11-22, 15:32   #33
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

32·19·23 Posts
Default

Quote:
Originally Posted by ATH View Post
What is your goal? Do you want to trial factor large mersenne numbers? Then mfactor is pretty fast I think: http://www.mersenneforum.org/showthread.php?t=4939
Short-term goal is to continue my pre-factoring project for 1000M-4294M. I've previously taken the range up to k=20000 and eliminated 50-million of 150-million candidates. I know returns will diminish drastically, but 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).

I played briefly with mfactor at your suggestion, but (like most TF programs) it's not optimized for such small runs and the overhead of (initializing each run, checking for savefiles, etc) make the runtime-per-exponent beyond what I'm willing to invest for this purpose right now.

Naturally I'm also running mfaktc, but it's horribly-inefficient on short runtimes (e.g. 5 seconds per candidate), so assuming 10 seconds per 3 candidates, it'll take me (or someone) about 10 years to get through the entire range up to somewhere around 2^66.
James Heinrich 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 11:56.


Mon Dec 5 11:56:20 UTC 2022 up 109 days, 9:24, 0 users, load averages: 0.73, 0.84, 0.85

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔