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

2012-09-30, 19:35   #56
ewmayer
2ω=0

Sep 2002
República de California

266508 Posts

Quote:
 Originally Posted by axn 2. None of the scripts/program so far are even close to optimal. If you're gonna throw compute power at it, perhaps it'll pay to invest in some upfront programming. I know that Ken_g6 has tackled k*2^n+1 type sieving -- perhaps he can adapt the code for our purpose? [I would anticipate an optimal siever to do a range of 10^12/day/core -- so no real advantage in pushing thru with the current scripts]
I speeded up my hacked-together 2*k*M(p)+1 sieve by 10x over the past few days; am getting ~5e12 per day on p = 43112609 using 1 2GHz i5 core of my macbook.

Currently I am running k = 185 to depth 1e13 on 1 core, and shallower sieving runs for all other k < 1000 which passed my default Mfactor sieve (i.e. primes up to ~1e6) on this exponent.

Last thing I need to do is to add the code needed to start at some user-provided lower bound on small primes (code currently always starts from 0, i.e. primes 3 - [upper_bound]), which will be needed to support ranged (and distributed) sieving; once that's in place (hopefully by tomorrow), will post the code tarball here.

p.s.: Largest factor I ound so far in my depth-1e11 runs: MM(43112609): Q( k = 384 ) has a small factor: 93934458313

p.p.s.: Like the tifosi-themed new improved subforum home for the thread. :)

Last fiddled with by ewmayer on 2012-09-30 at 19:43

 2012-10-01, 11:08 #57 ET_ Banned     "Luigi" Aug 2002 Team Italia 2·41·59 Posts I hope to gather all ranges done... I'm losing you! Luigi
 2012-10-01, 12:22 #58 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 22·2,467 Posts From the tables I posted before, these are gone by raising the khaki rows to 10G: Code: M#39 - k=225 has a factor : 7333051961 M#39 - k=348 has a factor : 2363117143 M#39 - k=368 has a factor : 1726045991 M#39 - k=440 has a factor : 2733515233 M#39 - k=909 has a factor : 6422117551 M#41 - k=285 has a factor : 8224776893 M#41 - k=393 has a factor : 3826927661 M#41 - k=708 has a factor : 1156768079 M#41 - k=833 has a factor : 1765835263 M#41 - k=1017 has a factor : 1530212371 M#42 - k=488 has a factor : 9213085003 M#42 - k=593 has a factor : 7645079803 M#42 - k=597 has a factor : 6131156639 M#42 - k=660 has a factor : 1042419673 M#43 - k=716 has a factor : 2821483351 #41 is completed Last fiddled with by LaurV on 2012-10-01 at 12:24
2012-10-01, 13:42   #59
ET_
Banned

"Luigi"
Aug 2002
Team Italia

113468 Posts

Quote:
 Originally Posted by LaurV From the tables I posted before, these are gone by raising the khaki rows to 10G: Code: M#39 - k=225 has a factor : 7333051961 M#39 - k=348 has a factor : 2363117143 M#39 - k=368 has a factor : 1726045991 M#39 - k=440 has a factor : 2733515233 M#39 - k=909 has a factor : 6422117551 M#41 - k=285 has a factor : 8224776893 M#41 - k=393 has a factor : 3826927661 M#41 - k=708 has a factor : 1156768079 M#41 - k=833 has a factor : 1765835263 M#41 - k=1017 has a factor : 1530212371 M#42 - k=488 has a factor : 9213085003 M#42 - k=593 has a factor : 7645079803 M#42 - k=597 has a factor : 6131156639 M#42 - k=660 has a factor : 1042419673 M#43 - k=716 has a factor : 2821483351 #41 is completed
Thank you LaurV!

Luigi

2012-10-01, 14:03   #60
axn

Jun 2003

10100100101102 Posts

Quote:
 Originally Posted by ewmayer I speeded up my hacked-together 2*k*M(p)+1 sieve by 10x over the past few days; am getting ~5e12 per day on p = 43112609 using 1 2GHz i5 core of my macbook.
You're probably within a factor of two from "optimal", so I guess "good enough" If you're up for some algorithmic challenge, though, I'd suggest to create a siever that can simultaneously test _all_ the MMps.

Quote:
 Originally Posted by ewmayer Currently I am running k = 185 to depth 1e13 on 1 core, and shallower sieving runs for all other k < 1000 which passed my default Mfactor sieve (i.e. primes up to ~1e6) on this exponent.
Is there a reason why you're not sieving all the k's at once?

Quote:
 Originally Posted by ewmayer Last thing I need to do is to add the code needed to start at some user-provided lower bound on small primes (code currently always starts from 0, i.e. primes 3 - [upper_bound]), which will be needed to support ranged (and distributed) sieving; once that's in place (hopefully by tomorrow), will post the code tarball here.
Looking forward to it

2012-10-01, 18:17   #61
ewmayer
2ω=0

Sep 2002
República de California

23×3×487 Posts

Quote:
 Originally Posted by axn You're probably within a factor of two from "optimal", so I guess "good enough" If you're up for some algorithmic challenge, though, I'd suggest to create a siever that can simultaneously test _all_ the MMps.
Different MMp have different k which survive the standard many-k's small-prime sieve using in Mersenne TF. Also, different MMp have different allowable (k%60, p%60) combinations to begin with.

Quote:
 Is there a reason why you're not sieving all the k's at once?
Even for a given MMp, little to be gained by that, since the cost is dominated by the 2*k*M(p)+1 (mod) step, not by the sieve which weeds out candidate divisors which themselves have small prime factors. Also, since I don't want to spend days writing the user interface, I prefer to keep the argument list as simple as possible: one p, one k, and a sieving range.

2012-10-02, 03:30   #62
ewmayer
2ω=0

Sep 2002
República de California

23·3·487 Posts

Code tarball (use tar -xvzf *.tgz to unpack) is attached. This took a few hours longer than anticipated due to a bug discovered late in testing. The fix slows the code down ~10%; once I find a reliable fix which allows the affected code sequence to again be computed via faster floating-point math I'll post it.

1-line build instructions are near the top of the C source, beneath the #includes. After building, PLEASE make sure you can run both of the listed self-tests (which also summarize the argument syntax) before doing any really deep testing.

Have only tested under 64-bit Mac OS X, but most of the components here have built OK under Win32. For Win64 users I suggest using a Linux/GCC emulator like mingw64, so you can enjoy the benefit of the 64-bit inline ASM in the core modmul routine.

The code prints some simple diagnostics for every 2^30 th candidate tried (every few minutes on my system); thus you should run in a dedicated shell or pipe the output to a file if you want to run in background mode. The diagnostics can be used for spot-sanity checking using (say) Pari: The only composites appearing in the output should have only factors > the small-p sieve limit, which I have quasi-optimized for factoring around depths 1e13-1e14, via use of the 100000 smallest odd primes; this gives

Max sieving prime = 1299721

For imax <= the square of this you should only see base-2 PRPs reported in the diagnostics; above that a gradually increasing proportion of composites will appear.

I'll let someone else organize sieving ranges, etc - Note that due the aforementioned bug-find and fix I am currently rerunning my deep sieving of MM(43112609) with k = 185 to depth 1e13 (which will need ~2 days on one 2GHz core); suggest others test ranges which are multiples of that one, e.g. the next such-sized interval:

Let me know about any build or run issues, and enjoy!
./factor_qmmp -k 185 -p 43112609 -imin 10000000000000 -imax 20000000000000
Attached Files
 factor_qmmp.tgz (35.3 KB, 136 views)

Last fiddled with by ewmayer on 2012-10-02 at 19:05 Reason: .tar.gz --> .tgz

 2012-10-02, 06:48 #63 ewmayer ∂2ω=0     Sep 2002 República de California 2DA816 Posts The ( k = 384 ) Example #2 factor in the C source I first posted was a bogus one found due to the same bug I fixed in said source. (I just rechecked the alleged factor, 93934458313, via Pari, and it's bogus.) I have uploaded new source tarball (now with a concatenated .tgz extension, which Mike just added to the allowed attachment types at my request.) No change in function, just an updated example which actually yields a factor (if you already downloaded the earlier tar.gz bundle, just modify the build-related comment with this new example #2): Test #2: This should find the small-prime factor 7450239943 in around 20 GHz-seconds on x86_64: time ./factor_qmmp -p 43112609 -imin 7000000000 -imax 8000000000 -k 665
2012-10-02, 08:50   #64
axn

Jun 2003

122268 Posts

Quote:
 Originally Posted by ewmayer Even for a given MMp, little to be gained by that, since the cost is dominated by the 2*k*M(p)+1 (mod) step, not by the sieve which weeds out candidate divisors which themselves have small prime factors.
You misunderstand (I think).

if 2*k*Mp+1 == 0 (mod f), then k = -(2*Mp)^-1 (mod f).
i.e. for a teensy little cost (of an extra modular inverse), you can figure out the k that f divides, thus turning it into a "all k at a single shot" sieve.

Also, using a addition chain, (Mp mod f) can b calculated for all Mps at a fraction of a cost of calculating them individually.

2012-10-02, 16:28   #65
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2·41·59 Posts

Quote:
 Originally Posted by ewmayer The ( k = 384 ) Example #2 factor in the C source I first posted was a bogus one found due to the same bug I fixed in said source. (I just rechecked the alleged factor, 93934458313, via Pari, and it's bogus.) I have uploaded new source tarball (now with a concatenated .tgz extension, which Mike just added to the allowed attachment types at my request.) No change in function, just an updated example which actually yields a factor (if you already downloaded the earlier tar.gz bundle, just modify the build-related comment with this new example #2): Test #2: This should find the small-prime factor 7450239943 in around 20 GHz-seconds on x86_64: time ./factor_qmmp -p 43112609 -imin 7000000000 -imax 8000000000 -k 665
On Linux you should add the math library. This is the correct command:

Code:
gcc factor_qmmp*.c -Wall -lm -O3 -o factor_qmmp
And these are the results on my Corei5-750:

Code:
$time ./factor_qmmp time ./factor_qmmp -p 43112609 -k 5 -imax 10000000000 Using first 100000 odd primes; max gap = 114 Max sieving prime = 1299721 Searching for small divisors of MM(43112609): Q( k = 5 ) in interval [3, 10000000000]... MM(43112609): Q( k = 5 ) has a small factor: 582994261 Tried 30482628 ints which passed small-p sieve.. real 0m8.556s user 0m8.530s sys 0m0.000s$time ./factor_qmmp -p 43112609 -imin 7000000000 -imax 8000000000 -k 665
Using first 100000 odd primes; max gap = 114
Max sieving prime = 1299721
Searching for small divisors of MM(43112609): Q( k = 665 ) in interval [7000000001, 8000000000]...
MM(43112609): Q( k = 665 ) has a small factor: 7450239943
Tried 19833796 ints which passed small-p sieve..

real	0m5.672s
user	0m5.650s
sys	0m0.000s
luigi@luigi-ubuntu:~/luigi/dm/factor_qmmp\$
Luigi

Last fiddled with by ET_ on 2012-10-02 at 16:31 Reason: Added a red tag and reformatted the output

 2012-10-02, 17:07 #66 ET_ Banned     "Luigi" Aug 2002 Team Italia 12E616 Posts M#47 to 10G Range completed. Reserving M#47 to 1T and don't mind the title... (185 has been done to 10T by Ernst). Luigi Last fiddled with by ET_ on 2012-10-02 at 17:13 Reason: Raising the top...

 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 20:59.

Fri Jan 21 20:59:13 UTC 2022 up 182 days, 15:28, 0 users, load averages: 1.31, 1.55, 1.54