mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-09-30, 19:35   #56
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2DA816 Posts
Default

Quote:
Originally Posted by axn View Post
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
ewmayer is online now   Reply With Quote
Old 2012-10-01, 11:08   #57
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

483810 Posts
Default

I hope to gather all ranges done... I'm losing you!

Luigi
ET_ is offline   Reply With Quote
Old 2012-10-01, 12:22   #58
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

232158 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2012-10-01, 13:42   #59
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2·41·59 Posts
Default

Quote:
Originally Posted by LaurV View Post
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
ET_ is offline   Reply With Quote
Old 2012-10-01, 14:03   #60
axn
 
axn's Avatar
 
Jun 2003

527210 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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 View Post
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 View Post
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
axn is offline   Reply With Quote
Old 2012-10-01, 18:17   #61
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

23×3×487 Posts
Default

Quote:
Originally Posted by axn View Post
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.
ewmayer is online now   Reply With Quote
Old 2012-10-02, 03:30   #62
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

23×3×487 Posts
Default

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
File Type: tgz factor_qmmp.tgz (35.3 KB, 136 views)

Last fiddled with by ewmayer on 2012-10-02 at 19:05 Reason: .tar.gz --> .tgz
ewmayer is online now   Reply With Quote
Old 2012-10-02, 06:48   #63
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

101101101010002 Posts
Default

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
ewmayer is online now   Reply With Quote
Old 2012-10-02, 08:50   #64
axn
 
axn's Avatar
 
Jun 2003

122308 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
axn is offline   Reply With Quote
Old 2012-10-02, 16:28   #65
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

12E616 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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
ET_ is offline   Reply With Quote
Old 2012-10-02, 17:07   #66
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×41×59 Posts
Default 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...
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:39.


Sat Jan 22 21:39:26 UTC 2022 up 183 days, 16:08, 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.

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