mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operazione Doppi Mersennes

Reply
 
Thread Tools
Old 2012-10-17, 18:47   #122
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

23×3×487 Posts
Default

Updated source (just the main-program .c file - headers same as before) attached to this message.

By way of clarification: For those doing deep sieving, since the code uses both stdout and stderr for output, you'll want to do redirect-to-file by e.g. appending " &> err.log" to the command line. (The & causes all ostreams to get redirected to the target of the > ).

(You can further append " &" to put into bg mode immediately, or do ctrl+z / bg after invocation to accomplish the same thing).

Only changes to the source are slightly improved help-diagnostics (try invoking the executable with no args, for example) and a fix for the bug I mentioned running into leading up to the first release, which allows me to get rid of the slow workaround and gain ~5% more speed. As always, let me know of any issues and suggestions for future versions.

Cheers,
-Ernst
Attached Files
File Type: gz factor_qmmp_sieve64.c.gz (15.6 KB, 103 views)
ewmayer is offline   Reply With Quote
Old 2012-10-17, 19:19   #123
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

113468 Posts
Default

On post #74 Ernst gave us the tables of the candidates for this deep sieving project.

On post #118 I asked for information about some ks that should have been sieved out, since the limits on Will Edgington's page were higher. I would like to avoid duplication of work, but can't find the factors that eliminate those ks.

Is there anyone that has them? Maybe Will (I will ask him by email)? Or Phil? Or have they all just been ruled out by PRP?

On post #120 LaurV told us that "2*92*M1257787+1 does not divide MM1257787": was he referring to a PRP test he did?

I'm sorry to ask so many questions, but as I have take the task of centralize information on double Mersenne numbers on one site (maybe too) seriously, now I am worried of losing bits of data...

Thank you for your patience...

Luigi
ET_ is offline   Reply With Quote
Old 2012-10-17, 19:22   #124
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×41×59 Posts
Default

Quote:
Originally Posted by ewmayer View Post
Updated source (just the main-program .c file - headers same as before) attached to this message.
[...]
Cheers,
-Ernst
Thank you Ernst!

Have you done any tests on the threshold of NUM_SIEVING_PRIME for sieving above 1T?

Luigi
ET_ is offline   Reply With Quote
Old 2012-10-17, 21:15   #125
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

23×3×487 Posts
Default

Quote:
Originally Posted by ET_ View Post
Have you done any tests on the threshold of NUM_SIEVING_PRIME for sieving above 1T?
Not above 1T ... here is the small table I generated while searching for near-optimal params for runs around 1T:
Code:
Timing tests in 3 different ranges vs #sieve_prime, all with p = 43112609
(all run with full-time LL test on other CPU):

Command-line arguments			    #prime:   1e3   1e5   1e5   1e6
------------------------------------------------    ----------------------------
                     -imax     1000000000 -k   5    11.4s 11.6s 12.4s 21.3s
-imin     7000000000 -imax     8000000000 -k 665     9.3s  8.0s  9.2s 18.2s
-imin 10007000000000 -imax 10008000000000 -k 665    20.7s 19.2s 18.1s 28.7s
								***** <<< optimize for this ***
The last row is around 1T; a bit of finer-grained testing led me to take NUM_SIEVING_PRIME = 2e5, as seen in the current source. You are welcome to experiment with this - with more data perhaps we can put together some kind of simple curve-fit which could be incorporated into the code setting NUM_SIEVING_PRIME dynamically at runtime, based on the user's desired sieving range. I have other projects I need to attend to, so leave it to my loyal user base to do such data-gathering. :)
ewmayer is offline   Reply With Quote
Old 2012-10-18, 02:32   #126
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

232158 Posts
Default

Quote:
Originally Posted by ET_ View Post
On post #120 LaurV told us that "( q= ) 2*92*M1257787+1 does not divide ( m= ) MM1257787": was he referring to a PRP test he did?
Yes, I did Trial Factoring test (i.e. exponentiation, squaring and test if final residue is 2, this is not a PRP test, because I did not test if q is prime or not, I only tested if q divides m, and the answer is not. So the "history value" of k=91 can be raised to k=92. The k=93 is under test. I can collect the residue, but I don't think it matters.

For things related to your post #118, I don't think that somebody has factors for those. Re-visiting the post now, I see those k's are the starting values on each row, those which were grayed in my initial table (because they were under the watermark, i.e. the historical "k" was higher). I believe those k's were eliminated by trial factoring, same as I did in the paragraph above. You should ask Toni, or the persons involved.

Last fiddled with by LaurV on 2012-10-18 at 02:34
LaurV is offline   Reply With Quote
Old 2012-10-18, 09:55   #127
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×41×59 Posts
Default

@Ernst: I will do some tests during the weekend and post my results.

@LaurV: Thank you for the answer, I will contact Tony Forbes hoping to have some more data to integrate.

Luigi
ET_ is offline   Reply With Quote
Old 2012-10-18, 18:50   #128
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2×283 Posts
Default Collecting residues

Quote:
Originally Posted by LaurV View Post
I can collect the residue, but I don't think it matters.
There will never ever be anyone who would be able to do a LL on these large MMs, so I think it would be very, very important thing to collect the residues since sooner or later somebody would like to do a double-check.
aketilander is offline   Reply With Quote
Old 2012-10-19, 12:20   #129
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

12E616 Posts
Thumbs up Tony Forbes answered.

Now I have all data relative to MM34 and MM35.

Tony did his sieving work for MM34 and MM35 up to 20G for k<500,000, so we just double-checked his work for k < 1,000.

The "Deep Sieving" pages have been reworked, while I am still in process of inserting Tony's new k. It won't be an high-priority task.

Meanwhile, I'd like to know the process of selecting ks, should I decide to raise them.

Must they only be 0 or 1 mod 4, and 2kp+1 mod 120 = {16 known values over 60 possible}?

Luigi

Last fiddled with by ET_ on 2012-10-19 at 14:06
ET_ is offline   Reply With Quote
Old 2012-10-20, 11:29   #130
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

10010111001102 Posts
Default

@Ernst.

On post 74 you said:

Quote:
These (k)were all sieved to p <= 32452867 (i.e. the first 2 million odd primes). These are for k < 1000 (let me know if you need larger k-ranges for any cases) and sorted by ascending k.
It is not urgent, nor imperative, but with time on your side, I might extend our tables from MM36 to MM47 and 1,000 < k < 500.000 to integrate Tony Forbes' results. Initially I would keep k<1,000 to help visualization, and add more fields as we sieve out smaller ks.

Meanwhile, I started some benchmarking on factor_qmmp to optimize NUM_SIEVING_PRIME.

Luigi
ET_ is offline   Reply With Quote
Old 2012-10-21, 16:02   #131
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2·41·59 Posts
Default factor_qnnp optimzation tables

I ran some benchmarks on factor_qmmp, varying the following parameters:

- The NUM:SIEVING_PRIME parameter
- The exponent of the double Mersenne number
- The range computed
- The sieve position where the range was taken

The results have been uploaded here.

Considerations:

1 - It would not be hard designing a regression line to grant each exponent/range the correct NUM_SIEVE_PRIMES
2 - Changing k from 8 to 1000 won't affect performance
3 - We have a limitation for k higher than (say) 100,000, and must wait a 64-bit version of the siever
4 - Note to Ernst: sieving ranges of 1G starting from k=500T produces a strange shrink of more than 10% in the calculation time, Did the program loose a loop or get a wrong exit flag?

Apart from this, the best NUM_SIEVING_PRIMES value for each range is evident from the first and last table (those with range = 10G).

Enjoy!

Luigi
Attached Files
File Type: zip factor_qmmp_bench.txt.zip (2.1 KB, 90 views)
ET_ is offline   Reply With Quote
Old 2012-10-27, 09:58   #132
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

10010111001102 Posts
Cool First one kocked down!

MM(32582657): k=20 has a factor: 665316631883
Next k=60

Luigi

BTW, is anybody else testing/sieving? I had MM(1257787), k=93 reserved by LaurV...

Last fiddled with by ET_ on 2012-10-27 at 10:00 Reason: I just noticed that I can't edit the title, evidently wrong...
ET_ is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is CEMPLLA 1.5 "the only software in the world capable of discovering" something? Not really. CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55
Official "World cup 2014/2018" teat LaurV Hobbies 74 2018-07-11 19:33
Problem E7 of Richard Guy's "Unsolved problems in number theory" Batalov Computer Science & Computational Number Theory 40 2013-03-16 09:19
Is the USA the "new" peacekeeper of the world?? outlnder Soap Box 20 2005-02-03 09:30
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 21:38.


Sat Jan 22 21:38:23 UTC 2022 up 183 days, 16:07, 0 users, load averages: 1.37, 1.36, 1.31

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.

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