mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-02-23, 23:58   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

192C16 Posts
Default 109!+1 sieving

The polynomial is (thanks to amphoria!)

Code:
n: 144385958320249358220488210246279753379312820313396029159834075622223337844983482099636001195615259277084033387619818092804737714758384244334160217374720000000000000000000000001
alim: 100000000
rlim: 100000000
mfba: 64
mfbr: 62
lpba: 32
lpbr: 31
rlambda: 2.6
alambda: 2.6
skew: 456282.99
Y1: 5723023480424293549
Y0: -1447147258982995597042473000254365
c5: 22748948520
c4: 131786016342762
c3: -7277355584450508798389
c2: -1506621246064449910835035708
c1: 1545265962793052491208583283946356
c0: 319269318301039358208041771529228054864
Yield is just over 2.1 relations per Q at Q=10^8. Sieve with gnfs-lasieve4I15e on the algebraic side only, 10M to 160M ought to be enough to get a matrix and then we'll see what the trade-off is like. ~200 hours for 1MQ on one core of a 2.5GHz Phenom, this should be quite a bit quicker than 5^421-1 was.

21Apr: Reservations essentially closed: please make only reservations that will finish by 24 April
24Apr: That's 175MQ done, starting filtering

I am giving up whimsy for Lent, so the folder for relations is called bang109.

Reservations:
andi47 10M-11M (done 23Mar)
fivemack 11M-19M (done 06Mar)
bsquared 19M-50M (done 10Mar)
sean 50M-60M (done 22Mar)
amphoria 60M-62M (done 13Mar)
batalov 62M-63M (done 10Mar)
fivemack 63M-64M (done 14Mar)
amphoria 64M-65M (done 22Mar)
Xyzzy 65M-73M (done 25Mar)
bsquared 73M-77M (done 18Mar)
bsquared 77M-80M (done 19Mar)
fivemack 80M-90M (done 30Mar)
fivemack 90M-100M (done 16Mar)
fivemack 100M-110M (done 11Mar)
Xyzzy 110M-120M (done in ten thousand pieces, 13Mar)
Joe_O 120M-125M (done 15Apr)
bsquared 125M-130M (done 23Mar)
amphoria 130M-131M (done 27Mar)
fivemack 131M-140M (done 22Apr)
amphoria 140M-141M (done 01Apr)
fivemack 141M-147M (done 14Apr)
Joe_O 147M-148M (done 23Apr)
sean 148M-150M (done 13Apr)
fivemack 150M-156M (done 22Apr)
bsquared 156M-166M (done 17Apr)
sean 166M-168M (done 21Apr)
bsquared 168M-173M (done 20Apr)
fivemack 173M-177M (done 24Apr)
bsquared 177M-185M (done 22Apr)

Results
andi47 23Mar 10M-11M 1315920 (1163ks, C2/1800)
fivemack 05Mar 11M-12M 1372059 (763ks, K8/2200)
fivemack 05Mar 12M-13M 1435393 (766ks, K8/2200)
fivemack 04Mar 13M-14M 1487651 (652ks, C2/2400)
fivemack 04Mar 14M-15M 1539267 (653ks, C2/2400)
fivemack 06Mar 15M-16M 1597340 (758ks, K8/2200)
fivemack 06Mar 16M-17M 1619859 (752ks, K8/2200)
fivemack 05Mar 17M-18M 1633878 (775ks, K8/2200) <- some badscheds
fivemack 05Mar 18M-19M 1685331 (782ks, K8/2200)
bsquared 10Mar 19M-50M 60334336 (36.4Ms, K8/1400 cluster)
sean 12Mar 50M-53M 6198326 (no timing)
sean 16Mar 53M-57M 8362226 (no timing)
sean 23Mar 57M-58M 2081728 (no timing)
sean 22Mar 58M-60M 4211714 (no timing)
amphoria 13Mar 60M-62M 4205831 (1576ks, C2/2400)
batalov 10Mar 62M-63M 2115556 (555ks, C2/3200)
fivemack 14Mar 63M-64M 2139550 (total 1484ks, 8 threads i7/2800, 189ks wallclock)
amphoria 22Mar 64M-65M 2116114 (786ks, C2/2400)
Xyzzy 25Mar 65M-73M 17085956 (no timing)
bsquared 18Mar 73M-77M 8597605 (3.6Ms, K8/2000 cluster)
bsquared 19Mar 77M-80M 6466259 (2.7Ms, K8/2000 cluster)
fivemack 22Mar 80M-82M 4320471 (total 2773ks, 8 threads i7/2800, 562ks wallclock since I ran a 5.5M linalg on the machine at the same time)
fivemack 27Mar 82M-84M 4314701 (1.7Ms, K8/2200)
fivemack 30Mar 84M-86M 4313224 (1.4Ms, C2/2400)
fivemack 27Mar 86M-88M 4322114 (1.7Ms, K8/2200)
fivemack 16Mar 88M-89M 2167338 (662ks, C2/2666)
fivemack 16Mar 89M-90M 2169375 (total 841ks, 4 cores K8/2400)
fivemack 09Mar 90M-91M 2159878 (total 841ks, 4 cores K8/2400)
fivemack 09Mar 91M-92M 2181945 (664ks, C2/2666)
fivemack 16Mar 92M-93M 2155382 (833ks, K8/2200)
fivemack 16Mar 93M-94M 2167143 (837ks, K8/2200)
fivemack 16Mar 94M-95M 2173231 (862ks, K8/2200)
fivemack 16Mar 95M-96M 2196543 (869ks, K8/2200)
fivemack 16Mar 96M-97M 2171208 (865ks, busy C2/2400)
fivemack 16Mar 97M-98M 2178436 (865ks, busy C2/2400)
fivemack 16Mar 98M-99M 2154631 (725ks, K8/2200)
fivemack 16Mar 99M-100M 2182948 (734ks, K8/2200)
fivemack 04Mar 100M-101M 2175878 (748ks, C2/2400)
fivemack 04Mar 101M-102M 2163357 (743ks, C2/2400)
fivemack 11Mar 102M-110M 17191367 (total 10.8Ms, 8 threads i7/2800, 1363ks wallclock)
Xyzzy 14Mar 110M-120M 20829842 (no timing)
Joe_O 21Mar 120M-121M 2050373 (1696ks, unknown h/w)
Joe_O 21Mar 121M-122M 2050450 (1612ks, unknown h/w)
Joe_O 15Apr 122M-125M 6566653
bsquared 23Mar 125M-130M 10059055 (4.5Ms, K8/2000 cluster)
amphoria 26Mar 130M-131M 2186927 (849ks, C2/2400).
fivemack 28Mar 131M-132M 1989737 (total about 1.3Ms, 8 threads i7/2800)
fivemack 14Apr 132M-134M 3970776 (about 1.8Ms, K8/2200)
fivemack 22Apr 134M-136M (1.75Ms, K8/2200)
fivemack 14Apr 136M-138M 3924807 (about 1.7Ms, K8/2400)
fivemack 14Apr 138M-140M 3912247 (about 1.3Ms, C2/2666)
amphoria 01Apr 140M-141M 2187629
fivemack 14Apr 141M-147M 11584855 (total 4.4Ms across four CPUs of K10/2500)
Joe_O 23Apr 147M-148M 2223045
sean 13Apr 148M-150M 3832907
fivemack 22Apr 150M-156M 11340277 (4.6Ms, various machines)
bsquared 17Apr 156M-166M 18583556 (8.9Ms, K8/2000 cluster)
sean 21Apr 166M-168M 3683268
bsquared 20Apr 168M-173M 9116742 (4.4Ms, K8/2000 cluster)
fivemack 24Apr 173M-177M 7238674 (2.9Ms, K10/2500 and C2Q/2400)
bsquared 22Apr 177M-185M 13991174 (7.8Ms, K8/2000 cluster)

Running the numbers
11/03 2315: 52MQ; 100,694,925 relations; 10,760,185 duplicates; 89,934,740 unique.
28/03 1210: 117MQ; 237,314,550 relations; 39,422,297 duplicates; 197,892,253 unique. Not quite enough to make a matrix yet.
19/04 2115: 146MQ; 294,187,155 relations; 54,490,121 duplicates; 239,697,034 unique. Weight of 14229099 cycles is about 996233938.
24/04 1955: 175MQ; 345,724,586 relations; 68,073,995 duplicates; 277,650,572 unique. Weight of 13105884 cycles is about 917644802 (70.02/cycle)

Last fiddled with by fivemack on 2009-04-25 at 17:10 Reason: another day, another mega-Q
fivemack is offline   Reply With Quote
Old 2009-02-24, 05:29   #2
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

23×7×149 Posts
Default

How much time are you looking for us to spend sieving?

We will take 110-120M.
Xyzzy is offline   Reply With Quote
Old 2009-02-24, 06:48   #3
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

1001101100102 Posts
Default

I will try to start running 10.0-11.0M tomorrow or thursday to see if it still fits in my office PC whithout slowing it down to much.
Andi47 is offline   Reply With Quote
Old 2009-02-24, 08:42   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

644410 Posts
Default

I'd expect the sieving to take about 30,000 CPU-hours, which usually means between three and six weeks. I would be surprised if it finished inside three weeks, so feel free to start jobs which won't finish until say 15 March.
fivemack is offline   Reply With Quote
Old 2009-02-24, 16:37   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3·1,193 Posts
Default

I'll take 19M-50M. Should take roughly 13 days.
bsquared is offline   Reply With Quote
Old 2009-02-24, 17:17   #6
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default

Quote:
Originally Posted by fivemack View Post
I'd expect the sieving to take about 30,000 CPU-hours, which usually means between three and six weeks. I would be surprised if it finished inside three weeks, so feel free to start jobs which won't finish until say 15 March.
When I start my range tomorrow, I will not be able to collect and upload the relations before march 18th: I don't expect my range to be finished by march 5th, and than I will be away on business until march 17th. Should I start anyway?
Andi47 is offline   Reply With Quote
Old 2009-02-24, 18:59   #7
sean
 
sean's Avatar
 
Aug 2004
New Zealand

32×52 Posts
Default

Can someone tell me what implementation of the siever I should be using for this project. It is almost certainly not what I'm using now
sean is offline   Reply With Quote
Old 2009-02-25, 00:04   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22·32·179 Posts
Default

sean: I'm using the (64-bit Linux) version linked to from http://www.mersenneforum.org/showpos...6&postcount=23

10metreh: I've just finished hosting a pancake party which got through fifteen eggs, a bag of flour, six pints of milk and a multitude of lemons ...

andi47: yes, a reservation which doesn't finish until say 20 March is fine.

bsquared: 32 cores, eh?
fivemack is offline   Reply With Quote
Old 2009-02-25, 02:31   #9
sean
 
sean's Avatar
 
Aug 2004
New Zealand

111000012 Posts
Default

Quote:
Originally Posted by fivemack View Post
sean: I'm using the (64-bit Linux) version linked to from http://www.mersenneforum.org/showpos...6&postcount=23
Ok, thanks.

Next question: Does M in 10M etc. actually mean 10^7 rather than 10^6 for this project? I didn't think you could sieve below the factor bound of 10^8.
sean is offline   Reply With Quote
Old 2009-02-25, 03:16   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

67738 Posts
Default

Quote:
Originally Posted by sean View Post
Ok, thanks.

Next question: Does M in 10M etc. actually mean 10^7 rather than 10^6 for this project? I didn't think you could sieve below the factor bound of 10^8.
M is shorthand for e6 or X000000. You're right, so when we say we're sieving a range starting at 19M, say, it means we lower the alim for that range to 19e6. I believe the 64 bit linux binary pointed to by fivemack does that reduction automatically (with a printed warning), so you don't have to hand edit the .poly file for every range. Doing it this way means there is some advantage to breaking up a range into smaller chunks and raising alim for every incremented chunk, but over the size of the entire project I think 1M chunks are reasonable. That is what I am doing (with my 32 cores... nice estimate Tom :) ).

- ben.
bsquared is offline   Reply With Quote
Old 2009-02-25, 05:37   #11
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

209816 Posts
Default

Code:
e2396ee3232c5b5eea53d785d4f89cb2  gnfs-lasieve4I15e
Attached Files
File Type: bz2 gnfs-lasieve4I15e.bz2 (366.7 KB, 148 views)
Xyzzy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NFS sieving? Dubslow Factoring 8 2012-09-28 06:47
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
10^420 + 1 sieving juno1369 Factoring 20 2010-04-28 01:11
Sieving OmbooHankvald Prime Sierpinski Project 4 2005-06-30 07:51
Sieving robert44444uk Sierpinski/Riesel Base 5 8 2005-04-02 22:30

All times are UTC. The time now is 11:59.


Sat Nov 27 11:59:21 UTC 2021 up 127 days, 6:28, 0 users, load averages: 1.29, 1.28, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.