mersenneforum.org Sieving freakishly big MMs (was "World record" phone number?)
 Register FAQ Search Today's Posts Mark Forums Read

2012-10-17, 18:47   #122
ewmayer
2ω=0

Sep 2002
República de California

23×3×487 Posts

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
 factor_qmmp_sieve64.c.gz (15.6 KB, 103 views)

 2012-10-17, 19:19 #123 ET_ Banned     "Luigi" Aug 2002 Team Italia 113468 Posts 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
2012-10-17, 19:22   #124
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2×41×59 Posts

Quote:
 Originally Posted by ewmayer 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

2012-10-17, 21:15   #125
ewmayer
2ω=0

Sep 2002
República de California

23×3×487 Posts

Quote:
 Originally Posted by ET_ 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. :)

2012-10-18, 02:32   #126
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

232158 Posts

Quote:
 Originally Posted by ET_ 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

 2012-10-18, 09:55 #127 ET_ Banned     "Luigi" Aug 2002 Team Italia 2×41×59 Posts @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
2012-10-18, 18:50   #128
aketilander

"Åke Tilander"
Apr 2011
Sandviken, Sweden

2×283 Posts
Collecting residues

Quote:
 Originally Posted by LaurV 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.

 2012-10-19, 12:20 #129 ET_ Banned     "Luigi" Aug 2002 Team Italia 12E616 Posts 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
2012-10-20, 11:29   #130
ET_
Banned

"Luigi"
Aug 2002
Team Italia

10010111001102 Posts

@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

2012-10-21, 16:02   #131
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·41·59 Posts
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
 factor_qmmp_bench.txt.zip (2.1 KB, 90 views)

 2012-10-27, 09:58 #132 ET_ Banned     "Luigi" Aug 2002 Team Italia 10010111001102 Posts 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...

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55 LaurV Hobbies 74 2018-07-11 19:33 Batalov Computer Science & Computational Number Theory 40 2013-03-16 09:19 outlnder Soap Box 20 2005-02-03 09:30 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