mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-11-22, 15:40   #34
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

3,929 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
Between rcv's post #7 and science_man_88's post #20, I actually (mostly) understand this part. And it's incorporated in my current PARI code quite nicely -- the p%4 decision of [1,3] vs [3,1] is made in the PHP code that pulls the candidates out of the database and generates the PARI code.
James Heinrich is offline   Reply With Quote
Old 2012-11-22, 15:51   #35
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

3·5·683 Posts
Default

Trial factoring, part 2 of 3

Let's introduce 3 into equation. Mod 12 (=4*3), a prime (our p) can only be 1, 5, 7, or 11. Otherwise is not prime. So, let's put this in the table, with all possible 12 classes of k (mod 12). Of course, the cells on the table will contain the modularity of q to 24.

Code:
k\p  1   5   7  11
 0   1   1   1   1
 1   3  11  15  23
 2   5  21   5  21
 3   7   7  19  19
 4   9  17   9  17
 5  11   3  23  15
 6  13  13  13  13
 7  15  23   3  11
 8  17   9  17   9
 9  19  19   7   7
10  21   5  21   5
11  23  15  11   3
Then, same as in the first case, we mark with gray the q's which are 3 or 5 (mod 8) (i.e. 3, 5, 11, 13, 19, 21 (mod 24)) and we mark in blue (just for clarity) values as 9, 15, etc whose gcd with 24 is 3, as they are not prime. Those all are "unwanted" and what is left (black) in the table, we can count. It is very easy to see that, assuming we start with a k which is a multiple of 12, we do not need to test all k's, and we can "skip" some of them. If p is 1 (mod 12), we first skip 3, then skip 5, then skip another 3, then skip 1 (read the first column). If p is 5 (mod 12), we skip to 3, 1, 3, 5.

Let's put this in a piece of pari code:
Code:
/* splitting p in 12 classes 
   p must be a prime and fromk must be 0 (mod 12), no verification done, for speed reasons*/
tf_12c(p,fromk=0,tok=10000)=
{
    if(p%12== 1,v=[3,5,3,1],
    if(p%12== 5,v=[3,1,3,5],
    if(p%12== 7,v=[5,3,1,3],
    if(p%12==11,v=[1,3,5,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;)));
}
Now let's see if we save something...

Code:
(22:15:54) gp > \r tf
(22:44:22) gp > tf_2c(11)
M11 has a factor: 23
(22:44:34) gp > #
   timer = 1 (on)
(22:44:36) gp > tf_2c(67)
time = 3 ms.
(22:44:42) gp > tf_2c(67,,10^10)
M67 has a factor: 193707721
time = 604 ms.
(22:44:53) gp > tf_2c(67,,10^10)
M67 has a factor: 193707721
time = 599 ms.
(22:44:56) gp > tf_12c(67,,10^10)
M67 has a factor: 193707721
time = 412 ms.
(22:45:02) gp > tf_12c(67,,10^10)
M67 has a factor: 193707721
time = 396 ms.
Well, as expected, instead of testing half of the values (two from 4), now we test only a third (4 from 12) for each possible p. The program is 33% faster.

Next step is to put 5 into equation (60 classes), then 7 (420 classes), then 11 (4620 classes) and you have mfaktc. Excepting millions of optimization things

I come later with part 3, 60 classes, let me have some sleep (here 23:00) and need few minutes to make the table in excel tomorrow.

Last fiddled with by LaurV on 2012-11-22 at 16:22 Reason: alignment of the table, still did not get it right, I hate when the forum changes my spacing
LaurV is offline   Reply With Quote
Old 2012-11-22, 17:03   #36
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

3×5×683 Posts
Default

Trial factoring, part 3 of 3

Let's introduce 5 into equation, as I said, mod 60 (=4*3*5), a prime (our p) can be 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59. Otherwise is not prime. Caution for 49, it is not prime, but its gcd with 60 is 1, so a prime CAN be 49 mod 60. Ex: 109, 229, 349, 409, etc.

There are no other possibilities of reminders modulo 60 for a prime, all the other are divisible by either 2, 3, or 5, for p>5.

The table is attached in excel form:

60classes.zip

You have to look for "conditional formatting" formula to see how I grayed the cells (I did not do it by hand, I am nerd, but not SO NERD!). Remind that the cells are (mod 120) (as the q is k*p multiplied by 2), and that is where we get the modularity to 8 being 1 or 7. All numbers 3 or 5 (mod 8) were grayed, and all for which the gcd with 120 is bigger then 1. Caution, this lets into the table values like 49 or 119, even if they are not prime, but a prime can be 49 or 119 mod 120, because their gcd is 1. (same observation for 77, 91, but they are grayed because are 3,5 mod 8).

Let's put this in a piece of pari code:
Code:
/* splitting k in 60 classes 
   p must be a prime>5 and fromk must be 0 (mod 60), no verification done, for speed reasons*/
tf_60c(p,fromk=0,tok=10000)=
{
    if(p%60== 1, v=[3,5,3,4,5,3,1,11,1,3,5,4,3,5,3,1],
    if(p%60== 7, v=[5,3,1,3,5,3,4,5,3,1,11,1,3,5,4,3],
    if(p%60==11, v=[1],
    if(p%60==13, v=[1],
    if(p%60==17, v=[1],
    if(p%60==19, v=[1],
    if(p%60==23, v=[1],
    if(p%60==29, v=[1],
    if(p%60==31, v=[1],
    if(p%60==37, v=[1],
    if(p%60==41, v=[1],
    if(p%60==43, v=[1],
    if(p%60==47, v=[1],
    if(p%60==49, v=[1],
    if(p%60==53, v=[1],
    if(p%60==59, v=[1],
    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;)));
}
Remark that the program works only for p being 1 or 7 (mod 60), for the other you have to look into the table an fill the right vectors, otherwise the program still works, but is testing every k. That is the homework , and it should be easy done in few minutes if you understood the procedure. As a double check, adding all components of each vector v must give 60 (just in case you did not spot this already, as you cycle to 60 every time). And you better check my lines (and the table) too, it is late here and I might have made some mistakes...

Now let's see if we save something... as we are now testing only 16 values of k from 60, we should get the results much faster. Again, we select 67, as it is the most difficult to factor from p<100.

Code:
(23:42:08) gp > \r tf
(23:42:11) gp > #
   timer = 1 (on)
(23:42:18) gp > tf_60c(67,,10^10)
M67 has a factor: 193707721
time = 241 ms.
Well, this is indeed an improvement!

Your homework now is to implement 420 classes (add 7)
Honestly I don't think that adding 11 (4620 classes for k) would speed up more. Due to overhead of the ifs (there will be 960 ifs) it will be in fact slower. Mfaktc does SIEVING of each class of k, and you can't compare interpreted pari with compiled executable cuda...

But anyhow, with a good implementation, as I said in the past many times, this pari will be very efficient in eliminating small factors of big exponents (like from a billion to 10^10, or to 2^32, outside of GIMPS ranges, what James is doing).

Last fiddled with by LaurV on 2012-11-22 at 17:23
LaurV is offline   Reply With Quote
Old 2012-11-22, 20:22   #37
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

3,929 Posts
Default

Quote:
Originally Posted by LaurV View Post
You have to look for "conditional formatting" formula to see how I grayed the cells

Remark that the program works only for p being 1 or 7 (mod 60), for the other you have to look into the table an fill the right vectors, otherwise the program still works, but is testing every k. That is the homework , and it should be easy done in few minutes if you understood the procedure.
I see that. Unfortunately the GCD function is unknown in Excel 2003, so everything show there as blue. But fortunately Google's spreadsheet can read it fine, so I got what I needed. And I have done the homework (part 1):
Code:
/* splitting k in 60 classes 
   p must be a prime>5 and fromk must be 0 (mod 60), no verification done, for speed reasons*/
tf_60c(p,fromk=0,tok=10000)=
{
	if(p%60== 1, v=[3,5,3,4,5,3,1,11,1,3,5,4,3,5,3,1],
	if(p%60== 7, v=[5,3,1,3,5,3,4,5,3,1,11,1,3,5,4,3],
	if(p%60==11, v=[1,3,5,4,3,5,3,1,3,5,3,4,5,3,1,11],
	if(p%60==13, v=[3,5,3,1,3,5,3,4,5,3,1,11,1,3,5,4],
	if(p%60==17, v=[3,1,3,5,3,4,5,3,1,11,1,3,5,4,3,5],
	if(p%60==19, v=[5,4,3,5,3,1,3,5,3,4,5,3,1,11,1,3],
	if(p%60==23, v=[1,11,1,3,5,4,3,5,3,1,3,5,3,4,5,3],
	if(p%60==29, v=[4,3,5,3,1,3,5,3,4,5,3,1,11,1,3,5],
	if(p%60==31, v=[5,3,1,11,1,3,5,4,3,5,3,1,3,5,3,4],
	if(p%60==37, v=[3,5,4,3,5,3,1,3,5,3,4,5,3,1,11,1],
	if(p%60==41, v=[3,1,11,1,3,5,4,3,5,3,1,3,5,3,4,5],
	if(p%60==43, v=[5,3,4,5,3,1,11,1,3,5,4,3,5,3,1,3],
	if(p%60==47, v=[4,5,3,1,11,1,3,5,4,3,5,3,1,3,5,3],
	if(p%60==49, v=[11,1,3,5,4,3,5,3,1,3,5,3,4,5,3,1],
	if(p%60==53, v=[3,4,5,3,1,11,1,3,5,4,3,5,3,1,3,5],
	if(p%60==59, v=[1,3,5,3,4,5,3,1,11,1,3,5,4,3,5,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;)));
}
Quote:
Originally Posted by LaurV View Post
Your homework now is to implement 420 classes (add 7)
Honestly I don't think that adding 11 (4620 classes for k) would speed up more. Due to overhead of the ifs (there will be 960 ifs) it will be in fact slower.
In my particular implementation I can bypass the overhead of the ifs and just define the step list directly into the generated PARI code.
I'm not sure how much of a speedup to expect going from 60 to 420, nor do I trust my newly-found knowledge enough to try it unassisted, but what you've given me here is very useful, thanks!
James Heinrich is offline   Reply With Quote
Old 2012-11-22, 20:50   #38
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 see that. Unfortunately the GCD function is unknown in Excel 2003, so everything show there as blue. But fortunately Google's spreadsheet can read it fine, so I got what I needed. And I have done the homework (part 1):
Code:
/* splitting k in 60 classes 
   p must be a prime>5 and fromk must be 0 (mod 60), no verification done, for speed reasons*/
tf_60c(p,fromk=0,tok=10000)=
{
	if(p%60== 1, v=[3,5,3,4,5,3,1,11,1,3,5,4,3,5,3,1],
	if(p%60== 7, v=[5,3,1,3,5,3,4,5,3,1,11,1,3,5,4,3],
	if(p%60==11, v=[1,3,5,4,3,5,3,1,3,5,3,4,5,3,1,11],
	if(p%60==13, v=[3,5,3,1,3,5,3,4,5,3,1,11,1,3,5,4],
	if(p%60==17, v=[3,1,3,5,3,4,5,3,1,11,1,3,5,4,3,5],
	if(p%60==19, v=[5,4,3,5,3,1,3,5,3,4,5,3,1,11,1,3],
	if(p%60==23, v=[1,11,1,3,5,4,3,5,3,1,3,5,3,4,5,3],
	if(p%60==29, v=[4,3,5,3,1,3,5,3,4,5,3,1,11,1,3,5],
	if(p%60==31, v=[5,3,1,11,1,3,5,4,3,5,3,1,3,5,3,4],
	if(p%60==37, v=[3,5,4,3,5,3,1,3,5,3,4,5,3,1,11,1],
	if(p%60==41, v=[3,1,11,1,3,5,4,3,5,3,1,3,5,3,4,5],
	if(p%60==43, v=[5,3,4,5,3,1,11,1,3,5,4,3,5,3,1,3],
	if(p%60==47, v=[4,5,3,1,11,1,3,5,4,3,5,3,1,3,5,3],
	if(p%60==49, v=[11,1,3,5,4,3,5,3,1,3,5,3,4,5,3,1],
	if(p%60==53, v=[3,4,5,3,1,11,1,3,5,4,3,5,3,1,3,5],
	if(p%60==59, v=[1,3,5,3,4,5,3,1,11,1,3,5,4,3,5,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;)));
}
In my particular implementation I can bypass the overhead of the ifs and just define the step list directly into the generated PARI code.
I'm not sure how much of a speedup to expect going from 60 to 420, nor do I trust my newly-found knowledge enough to try it unassisted, but what you've given me here is very useful, thanks!

this code:

Code:
select(v->gcd(120,v)==1 && (v%8==7 || v%8==1),vector(120,n,n))
shows the values v<120 such that 120*u+v doesn't divide by a factor of 120 that also fit 1 or 7 mod 8, in earlier versions of Pari the argument order reverses. these are the values mod 120 which q can be to be prime and fit other arguments.

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

3·5·683 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
Unfortunately the GCD function is unknown in Excel 2003,
The GCD function should be available from very early versions of Excel, but it come as a separate plugin. You have to install (from the Tools/AdIns menu I think, unfortunately I updated all Office's including at home and work, but you can google for "excel 2003 gcd" or so) the additional package tool for analysis and engineering.

edit: Got it! Click on the first "How" on the text.

Last fiddled with by LaurV on 2012-11-23 at 02:31
LaurV is offline   Reply With Quote
Old 2012-11-23, 02:42   #40
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

392910 Posts
Default

Quote:
Originally Posted by LaurV View Post
The GCD function should be available from very early versions of Excel, but it come as a separate plugin.
Oh, yes, of course, silly me -- I'd forgotten about that. Of course, my Office install CD is cleverly buried away in storage where I won't have access to it for the next year or so, so I'll have to make do without it.
James Heinrich is offline   Reply With Quote
Old 2012-11-24, 14:19   #41
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

5·683 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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.
Why does it matter if it is not optimized for small runs, if it is still much faster? How long are you spending now getting candidates to k=20000? From your pari before it was 32sec for M4294949947?

I tested mfactor on the same exponent 4294949947:
Trialfactor to 2^58 (k=33,554,567): 7 sec
Trialfactor to 2^59 (k=67,109,135): 12 sec
Trialfactor to 2^60 (K=134,218,270): 21 sec

So it's several orders of magnitudes faster.

Last fiddled with by ATH on 2012-11-24 at 14:20
ATH is online now   Reply With Quote
Old 2012-11-24, 15:41   #42
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

3,929 Posts
Default

Quote:
Originally Posted by ATH View Post
From your pari before it was 32sec for M4294949947?
No, that was for a 1000-run time trial. It would actually be 32ms.

Practically I'm currently getting about 30 candidates per second across 6 cores, at about 4.5% factor rate (~1.3 factors per second) on 20000<k<100000 using PARI.

Using mfaktc to TF to 2^65 (k=18,359,596,156 around 1004M) takes about 9 seconds per candidate per instance (running 3 instances), at around 25% success rate (sometimes multiple factors are found per candidate, but that doesn't affect the factor/nofactor success rate) means I get about one factor every 12 seconds using mfaktc.

So while mfaktc is generally very much faster than CPU TF on a given range, and certainly even "fasterer" than equivalent PARI code to TF an exponent to (for example) 2^65, for my particular application (breadth-first TF to very low bitlevels) it turns out that on my machine, PARI can actually clear 15x more candidates per time interval than mfatkc can.

Note the diminishing returns, however -- at even lower levels (e.g. 0<k<10000) it was closer to 100x, and going much above k=100000 will pull efficiency down to 1:1 with mfaktc. There's no point using this PARI approach in the PrimeNet range since TF has universally been done up to 2^65+ already.
James Heinrich is offline   Reply With Quote
Old 2012-11-24, 18:06   #43
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

5×683 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
No, that was for a 1000-run time trial. It would actually be 32ms.
Ok, then I understand it. It's still 50x slower per k but if you want a big range of exponents instead of a deep search then I understand.

Maybe you should make an array of p values from 1000M to 4000M (about 140million primes) and then loop k-values from 1 to 20,000 and for each fixed k, you sieve the p-array up to some low limit, before testing the 2kp+1 that survives the sieve.
ATH is online now   Reply With Quote
Old 2012-11-24, 19:02   #44
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

3,929 Posts
Default

Quote:
Originally Posted by ATH View Post
Maybe you should make an array of p values from 1000M to 4000M (about 140million primes) and then loop k-values from 1 to 20,000 and for each fixed k, you sieve the p-array up to some low limit, before testing the 2kp+1 that survives the sieve.
Explain further, please? I'm currently using approximately the code in post #37 above, except that the generated PARI code has hardcoded jumplist based on p%60 instead of doing that check in PARI.
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 13:04.


Sun Dec 4 13:04:45 UTC 2022 up 108 days, 10:33, 0 users, load averages: 0.54, 0.82, 0.95

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.

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