So, HOW many more relations does it want?

Andi47 · 2008-12-07, 11:09

I am currently factoring hp548.74 c136, using this polynomial:

Code:

n: 2413298084812301955827350157306090317107421594242820489329309691540441783341150939643595560171399904625373615742310794643702469421900171
skew: 493321.72
c5  78120
c4  97232750889
c3 -42204187935206811
c2  59549894608656842891647
c1  4036065248257193572094637906
c0 -8667206126007101355663250669442776
Y0 -125305093374170894034075909
Y1  1184872132155583
rlim: 8000000
alim: 6000000
lpbr: 28
lpba: 28
rlambda: 2.55
alambda: 2.55
mfbr: 55
mfba: 55

After collecting ~12.5M relations I made a postprocessing attempt (msieve 1.39beta2 - should be the same as 1.39 final) to see how many more relations I need:

Code:

Sat Dec 06 11:49:50 2008  Msieve v. 1.39
Sat Dec 06 11:49:50 2008  random seeds: d84701f4 651a71ec
Sat Dec 06 11:49:50 2008  factoring 2413298084812301955827350157306090317107421594242820489329309691540441783341150939643595560171399904625373615742310794643702469421900171 (136 digits)
Sat Dec 06 11:49:52 2008  searching for 15-digit factors
Sat Dec 06 11:49:54 2008  commencing number field sieve (136-digit input)
Sat Dec 06 11:49:55 2008  R0: -153175532962819282953807122
Sat Dec 06 11:49:55 2008  R1:  863922264641669
Sat Dec 06 11:49:55 2008  A0: -63922911265972837908420983912147859
Sat Dec 06 11:49:55 2008  A1:  151059602958393608146940595699
Sat Dec 06 11:49:55 2008  A2:  149596136381437136431267
Sat Dec 06 11:49:55 2008  A3: -223841202629128035
Sat Dec 06 11:49:55 2008  A4: -66150837492
Sat Dec 06 11:49:55 2008  A5:  28620
Sat Dec 06 11:49:55 2008  skew 1087899.77, size 3.393933e-014, alpha -7.240297, combined = 3.791784e-013
Sat Dec 06 11:49:55 2008  
Sat Dec 06 11:49:55 2008  commencing relation filtering
Sat Dec 06 11:49:55 2008  commencing duplicate removal, pass 1
Sat Dec 06 11:52:44 2008  found 877418 hash collisions in 12484329 relations
Sat Dec 06 11:54:01 2008  added 117291 free relations
Sat Dec 06 11:54:01 2008  commencing duplicate removal, pass 2
Sat Dec 06 11:54:56 2008  found 665717 duplicates and 11935902 unique relations
Sat Dec 06 11:54:56 2008  memory use: 50.6 MB
Sat Dec 06 11:54:56 2008  reading rational ideals above 8978432
Sat Dec 06 11:54:56 2008  reading algebraic ideals above 8978432
Sat Dec 06 11:54:56 2008  commencing singleton removal, pass 1
Sat Dec 06 11:57:51 2008  relations with 0 large ideals: 141043
Sat Dec 06 11:57:51 2008  relations with 1 large ideals: 1065898
Sat Dec 06 11:57:51 2008  relations with 2 large ideals: 3351811
Sat Dec 06 11:57:51 2008  relations with 3 large ideals: 4701487
Sat Dec 06 11:57:51 2008  relations with 4 large ideals: 2544125
Sat Dec 06 11:57:51 2008  relations with 5 large ideals: 19180
Sat Dec 06 11:57:51 2008  relations with 6 large ideals: 112358
Sat Dec 06 11:57:51 2008  relations with 7+ large ideals: 0
Sat Dec 06 11:57:51 2008  11935902 relations and about 15081713 large ideals
Sat Dec 06 11:57:51 2008  commencing singleton removal, pass 2
Sat Dec 06 12:00:45 2008  found 6845218 singletons
Sat Dec 06 12:00:45 2008  current dataset: 5090684 relations and about 5690129 large ideals
Sat Dec 06 12:00:45 2008  commencing singleton removal, pass 3
Sat Dec 06 12:02:37 2008  found 2269420 singletons
Sat Dec 06 12:02:37 2008  current dataset: 2821264 relations and about 2894602 large ideals
Sat Dec 06 12:02:37 2008  commencing singleton removal, pass 4
Sat Dec 06 12:04:12 2008  found 1027168 singletons
Sat Dec 06 12:04:12 2008  current dataset: 1794096 relations and about 1685132 large ideals
Sat Dec 06 12:04:12 2008  commencing singleton removal, pass 5
Sat Dec 06 12:05:31 2008  found 546112 singletons
Sat Dec 06 12:05:31 2008  current dataset: 1247984 relations and about 1060782 large ideals
Sat Dec 06 12:05:31 2008  commencing singleton removal, pass 6
Sat Dec 06 12:06:50 2008  found 309003 singletons
Sat Dec 06 12:06:50 2008  current dataset: 938981 relations and about 717228 large ideals
Sat Dec 06 12:06:50 2008  commencing singleton removal, final pass
Sat Dec 06 12:08:09 2008  memory use: 22.6 MB
Sat Dec 06 12:08:09 2008  commencing in-memory singleton removal
Sat Dec 06 12:08:09 2008  begin with 938981 relations and 777602 unique ideals
Sat Dec 06 12:08:09 2008  reduce to 399431 relations and 177193 ideals in 15 passes
Sat Dec 06 12:08:09 2008  max relations containing the same ideal: 8
Sat Dec 06 12:08:10 2008  reading rational ideals above 720000
Sat Dec 06 12:08:10 2008  reading algebraic ideals above 720000
Sat Dec 06 12:08:10 2008  commencing singleton removal, final pass
Sat Dec 06 12:09:08 2008  keeping 1600051 ideals with weight <= 20, new excess is 116171
Sat Dec 06 12:09:08 2008  memory use: 37.3 MB
Sat Dec 06 12:09:08 2008  commencing in-memory singleton removal
Sat Dec 06 12:09:08 2008  begin with 504913 relations and 1600051 unique ideals
Sat Dec 06 12:09:08 2008  reduce to 474 relations and 1 ideals in 5 passes <-- LOL
Sat Dec 06 12:09:08 2008  max relations containing the same ideal: 2
Sat Dec 06 12:09:08 2008  filtering wants 402855 more relations
Sat Dec 06 12:09:08 2008  elapsed time 00:19:18

I sieved for ~800k more relations and started msieve again:

Code:

Sat Dec 06 19:52:14 2008  Msieve v. 1.39
Sat Dec 06 19:52:14 2008  random seeds: 0f6d66b0 5b666a44
Sat Dec 06 19:52:14 2008  factoring 2413298084812301955827350157306090317107421594242820489329309691540441783341150939643595560171399904625373615742310794643702469421900171 (136 digits)
Sat Dec 06 19:52:15 2008  searching for 15-digit factors
Sat Dec 06 19:52:18 2008  commencing number field sieve (136-digit input)
Sat Dec 06 19:52:18 2008  R0: -153175532962819282953807122
Sat Dec 06 19:52:18 2008  R1:  863922264641669
Sat Dec 06 19:52:18 2008  A0: -63922911265972837908420983912147859
Sat Dec 06 19:52:18 2008  A1:  151059602958393608146940595699
Sat Dec 06 19:52:18 2008  A2:  149596136381437136431267
Sat Dec 06 19:52:18 2008  A3: -223841202629128035
Sat Dec 06 19:52:18 2008  A4: -66150837492
Sat Dec 06 19:52:18 2008  A5:  28620
Sat Dec 06 19:52:18 2008  skew 1087899.77, size 3.393933e-014, alpha -7.240297, combined = 3.791784e-013
Sat Dec 06 19:52:18 2008  
Sat Dec 06 19:52:18 2008  commencing relation filtering
Sat Dec 06 19:52:18 2008  commencing duplicate removal, pass 1
Sat Dec 06 19:55:18 2008  found 983233 hash collisions in 13306075 relations
Sat Dec 06 19:56:37 2008  added 118020 free relations
Sat Dec 06 19:56:37 2008  commencing duplicate removal, pass 2
Sat Dec 06 19:57:17 2008  found 746445 duplicates and 12677650 unique relations
Sat Dec 06 19:57:17 2008  memory use: 50.6 MB
Sat Dec 06 19:57:17 2008  reading rational ideals above 9109504
Sat Dec 06 19:57:17 2008  reading algebraic ideals above 9109504
Sat Dec 06 19:57:17 2008  commencing singleton removal, pass 1
Sat Dec 06 20:00:24 2008  relations with 0 large ideals: 149386
Sat Dec 06 20:00:24 2008  relations with 1 large ideals: 1127500
Sat Dec 06 20:00:24 2008  relations with 2 large ideals: 3531612
Sat Dec 06 20:00:24 2008  relations with 3 large ideals: 4955076
Sat Dec 06 20:00:24 2008  relations with 4 large ideals: 2722468
Sat Dec 06 20:00:24 2008  relations with 5 large ideals: 78576
Sat Dec 06 20:00:24 2008  relations with 6 large ideals: 113032
Sat Dec 06 20:00:24 2008  relations with 7+ large ideals: 0
Sat Dec 06 20:00:24 2008  12677650 relations and about 15511490 large ideals
Sat Dec 06 20:00:24 2008  commencing singleton removal, pass 2
Sat Dec 06 20:03:29 2008  found 6938656 singletons
Sat Dec 06 20:03:29 2008  current dataset: 5738994 relations and about 6190709 large ideals
Sat Dec 06 20:03:29 2008  commencing singleton removal, pass 3
Sat Dec 06 20:05:21 2008  found 2303879 singletons
Sat Dec 06 20:05:21 2008  current dataset: 3435115 relations and about 3425562 large ideals
Sat Dec 06 20:05:21 2008  commencing singleton removal, pass 4
Sat Dec 06 20:06:55 2008  found 1054116 singletons
Sat Dec 06 20:06:55 2008  current dataset: 2380999 relations and about 2221206 large ideals
Sat Dec 06 20:06:55 2008  commencing singleton removal, pass 5
Sat Dec 06 20:08:25 2008  found 584039 singletons
Sat Dec 06 20:08:25 2008  current dataset: 1796960 relations and about 1573255 large ideals
Sat Dec 06 20:08:25 2008  commencing singleton removal, pass 6
Sat Dec 06 20:09:39 2008  found 357537 singletons
Sat Dec 06 20:09:39 2008  current dataset: 1439423 relations and about 1185019 large ideals
Sat Dec 06 20:09:39 2008  commencing singleton removal, final pass
Sat Dec 06 20:10:38 2008  memory use: 37.3 MB
Sat Dec 06 20:10:38 2008  commencing in-memory singleton removal
Sat Dec 06 20:10:38 2008  begin with 1439423 relations and 1291807 unique ideals
Sat Dec 06 20:10:38 2008  reduce to 501575 relations and 250393 ideals in 20 passes
Sat Dec 06 20:10:38 2008  max relations containing the same ideal: 11
Sat Dec 06 20:10:39 2008  reading rational ideals above 720000
Sat Dec 06 20:10:39 2008  reading algebraic ideals above 720000
Sat Dec 06 20:10:39 2008  commencing singleton removal, final pass
Sat Dec 06 20:11:14 2008  keeping 1704122 ideals with weight <= 20, new excess is 116171
Sat Dec 06 20:11:15 2008  memory use: 37.3 MB
Sat Dec 06 20:11:15 2008  commencing in-memory singleton removal
Sat Dec 06 20:11:15 2008  begin with 600537 relations and 1704122 unique ideals
Sat Dec 06 20:11:15 2008  reduce to 475 relations and 1 ideals in 5 passes <--ROTFL
Sat Dec 06 20:11:15 2008  max relations containing the same ideal: 2
Sat Dec 06 20:11:15 2008  filtering wants 402852 more relations
Sat Dec 06 20:11:15 2008  elapsed time 00:19:01

Hmmm... still wants 402.8k more relations...

Sieving for 1.6M more relations results in:

Code:

Sun Dec 07 11:26:11 2008  Msieve v. 1.39
Sun Dec 07 11:26:11 2008  random seeds: af4453c0 abf03944
Sun Dec 07 11:26:11 2008  factoring 2413298084812301955827350157306090317107421594242820489329309691540441783341150939643595560171399904625373615742310794643702469421900171 (136 digits)
Sun Dec 07 11:26:12 2008  searching for 15-digit factors
Sun Dec 07 11:26:15 2008  commencing number field sieve (136-digit input)
Sun Dec 07 11:26:15 2008  R0: -153175532962819282953807122
Sun Dec 07 11:26:15 2008  R1:  863922264641669
Sun Dec 07 11:26:15 2008  A0: -63922911265972837908420983912147859
Sun Dec 07 11:26:15 2008  A1:  151059602958393608146940595699
Sun Dec 07 11:26:15 2008  A2:  149596136381437136431267
Sun Dec 07 11:26:15 2008  A3: -223841202629128035
Sun Dec 07 11:26:15 2008  A4: -66150837492
Sun Dec 07 11:26:15 2008  A5:  28620
Sun Dec 07 11:26:15 2008  skew 1087899.77, size 3.393933e-014, alpha -7.240297, combined = 3.791784e-013
Sun Dec 07 11:26:15 2008  
Sun Dec 07 11:26:15 2008  commencing relation filtering
Sun Dec 07 11:26:15 2008  commencing duplicate removal, pass 1
Sun Dec 07 11:29:42 2008  found 1207022 hash collisions in 14931207 relations
Sun Dec 07 11:31:03 2008  added 119139 free relations
Sun Dec 07 11:31:03 2008  commencing duplicate removal, pass 2
Sun Dec 07 11:32:00 2008  found 918685 duplicates and 14131660 unique relations
Sun Dec 07 11:32:00 2008  memory use: 65.3 MB
Sun Dec 07 11:32:00 2008  reading rational ideals above 9502720
Sun Dec 07 11:32:00 2008  reading algebraic ideals above 9502720
Sun Dec 07 11:32:00 2008  commencing singleton removal, pass 1
Sun Dec 07 11:35:26 2008  relations with 0 large ideals: 176278
Sun Dec 07 11:35:26 2008  relations with 1 large ideals: 1310946
Sun Dec 07 11:35:26 2008  relations with 2 large ideals: 4016330
Sun Dec 07 11:35:26 2008  relations with 3 large ideals: 5499585
Sun Dec 07 11:35:26 2008  relations with 4 large ideals: 2935192
Sun Dec 07 11:35:26 2008  relations with 5 large ideals: 79377
Sun Dec 07 11:35:26 2008  relations with 6 large ideals: 113952
Sun Dec 07 11:35:26 2008  relations with 7+ large ideals: 0
Sun Dec 07 11:35:26 2008  14131660 relations and about 16264938 large ideals
Sun Dec 07 11:35:26 2008  commencing singleton removal, pass 2
Sun Dec 07 11:38:51 2008  found 7053842 singletons
Sun Dec 07 11:38:51 2008  current dataset: 7077818 relations and about 7128882 large ideals
Sun Dec 07 11:38:51 2008  commencing singleton removal, pass 3
Sun Dec 07 11:41:06 2008  found 2298036 singletons
Sun Dec 07 11:41:06 2008  current dataset: 4779782 relations and about 4481622 large ideals
Sun Dec 07 11:41:06 2008  commencing singleton removal, pass 4
Sun Dec 07 11:42:58 2008  found 1012186 singletons
Sun Dec 07 11:42:58 2008  current dataset: 3767596 relations and about 3376115 large ideals
Sun Dec 07 11:42:58 2008  commencing singleton removal, pass 5
Sun Dec 07 11:44:27 2008  found 540572 singletons
Sun Dec 07 11:44:27 2008  current dataset: 3227024 relations and about 2803287 large ideals
Sun Dec 07 11:44:27 2008  commencing singleton removal, pass 6
Sun Dec 07 11:45:49 2008  found 325166 singletons
Sun Dec 07 11:45:49 2008  current dataset: 2901858 relations and about 2464916 large ideals
Sun Dec 07 11:45:49 2008  commencing singleton removal, final pass
Sun Dec 07 11:47:09 2008  memory use: 66.6 MB
Sun Dec 07 11:47:09 2008  commencing in-memory singleton removal
Sun Dec 07 11:47:09 2008  begin with 2901858 relations and 2715217 unique ideals
Sun Dec 07 11:47:12 2008  reduce to 916231 relations and 572708 ideals in 29 passes
Sun Dec 07 11:47:12 2008  max relations containing the same ideal: 14
Sun Dec 07 11:47:12 2008  reading rational ideals above 720000
Sun Dec 07 11:47:12 2008  reading algebraic ideals above 720000
Sun Dec 07 11:47:12 2008  commencing singleton removal, final pass
Sun Dec 07 11:48:05 2008  keeping 2133470 ideals with weight <= 20, new excess is 116363
Sun Dec 07 11:48:07 2008  memory use: 49.1 MB
Sun Dec 07 11:48:07 2008  commencing in-memory singleton removal
Sun Dec 07 11:48:07 2008  begin with 1006041 relations and 2133470 unique ideals
Sun Dec 07 11:48:07 2008  reduce to 474 relations and 1 ideals in 6 passes
Sun Dec 07 11:48:07 2008  max relations containing the same ideal: 2
Sun Dec 07 11:48:07 2008  filtering wants 403524 more relations
Sun Dec 07 11:48:07 2008  elapsed time 00:21:56

STILL wanting 403.5k more relations - so HOW many does it really want?

Batalov · 2008-12-07, 11:21

A ballpark for a 28-bit project, you'd need 20-25M relns. So everything goes as planned so far (seriously). Your log fragments look fairly normal.

It doesn't estimate well how many it wants -- until the last stage.
The reported wanted number will stay at ~400K, then it will spike up (capped at 1,000,000), and then, on the way down it will be quite precise. Before the spike, never mind the number.

All will be fine, right now you are ~ halfway done.

Andi47 · 2008-12-07, 12:04

Quote:

Originally Posted by Batalov

A ballpark for a 28-bit project, you'd need 20-25M relns. So everything goes as planned so far (seriously). Your log fragments look fairly normal.

It doesn't estimate well how many it wants -- until the last stage.
The reported wanted number will stay at ~400K, then it will spike up (capped at 1,000,000), and then, on the way down it will be quite precise. Before the spike, never mind the number.

All will be fine, right now you are ~ halfway done.

Thanks - and I hope my 32-bit Windows XP pro is able to handle a >2GB relations file.

jasonp · 2008-12-07, 14:35

There used to be a 2GB file limit (Microsoft's C runtime library has a bug), but that limit was worked around long ago. You should be more worried about having enough memory for the postprocessing to complete (I'd estimate a C136 needs 1-1.5GB)

Andi47 · 2008-12-07, 14:40

Quote:

Originally Posted by jasonp

There used to be a 2GB file limit (Microsoft's C runtime library has a bug), but that limit was worked around long ago. You should be more worried about having enough memory for the postprocessing to complete (I'd estimate a C136 needs 1-1.5GB)

1-1.5 GB RAM looks OK as my laptop has 2 GB.

Andi47 · 2008-12-11, 11:04

After collecting a total of 21.25M relations, msieve succeeded:

Code:

Thu Dec 11 02:30:26 2008  
Thu Dec 11 02:30:26 2008  
Thu Dec 11 02:30:26 2008  Msieve v. 1.39
Thu Dec 11 02:30:26 2008  random seeds: 31c77ab8 bedf4580
Thu Dec 11 02:30:26 2008  factoring 2413298084812301955827350157306090317107421594242820489329309691540441783341150939643595560171399904625373615742310794643702469421900171 (136 digits)
Thu Dec 11 02:30:28 2008  searching for 15-digit factors
Thu Dec 11 02:30:30 2008  commencing number field sieve (136-digit input)
Thu Dec 11 02:30:30 2008  R0: -153175532962819282953807122
Thu Dec 11 02:30:30 2008  R1:  863922264641669
Thu Dec 11 02:30:30 2008  A0: -63922911265972837908420983912147859
Thu Dec 11 02:30:30 2008  A1:  151059602958393608146940595699
Thu Dec 11 02:30:30 2008  A2:  149596136381437136431267
Thu Dec 11 02:30:30 2008  A3: -223841202629128035
Thu Dec 11 02:30:30 2008  A4: -66150837492
Thu Dec 11 02:30:30 2008  A5:  28620
Thu Dec 11 02:30:30 2008  skew 1087899.77, size 3.393933e-014, alpha -7.240297, combined = 3.791784e-013
Thu Dec 11 02:30:30 2008  
Thu Dec 11 02:30:30 2008  commencing relation filtering
Thu Dec 11 02:30:30 2008  commencing duplicate removal, pass 1
Thu Dec 11 02:35:17 2008  found 2257584 hash collisions in 21254791 relations
Thu Dec 11 02:36:47 2008  added 120999 free relations
Thu Dec 11 02:36:48 2008  commencing duplicate removal, pass 2
Thu Dec 11 02:38:10 2008  found 1747808 duplicates and 19627981 unique relations
Thu Dec 11 02:38:10 2008  memory use: 94.6 MB
Thu Dec 11 02:38:10 2008  reading rational ideals above 11075584
Thu Dec 11 02:38:10 2008  reading algebraic ideals above 11075584
Thu Dec 11 02:38:10 2008  commencing singleton removal, pass 1
Thu Dec 11 02:43:00 2008  relations with 0 large ideals: 309936
Thu Dec 11 02:43:00 2008  relations with 1 large ideals: 2156967
Thu Dec 11 02:43:00 2008  relations with 2 large ideals: 6043755
Thu Dec 11 02:43:00 2008  relations with 3 large ideals: 7486313
Thu Dec 11 02:43:00 2008  relations with 4 large ideals: 3500414
Thu Dec 11 02:43:00 2008  relations with 5 large ideals: 15613
Thu Dec 11 02:43:00 2008  relations with 6 large ideals: 114983
Thu Dec 11 02:43:00 2008  relations with 7+ large ideals: 0
Thu Dec 11 02:43:00 2008  19627981 relations and about 18440872 large ideals
Thu Dec 11 02:43:00 2008  commencing singleton removal, pass 2
Thu Dec 11 02:47:46 2008  found 6946256 singletons
Thu Dec 11 02:47:46 2008  current dataset: 12681725 relations and about 10257697 large ideals
Thu Dec 11 02:47:46 2008  commencing singleton removal, pass 3
Thu Dec 11 02:51:11 2008  found 1853109 singletons
Thu Dec 11 02:51:11 2008  current dataset: 10828616 relations and about 8291347 large ideals
Thu Dec 11 02:51:11 2008  commencing singleton removal, pass 4
Thu Dec 11 02:54:20 2008  found 558151 singletons
Thu Dec 11 02:54:20 2008  current dataset: 10270465 relations and about 7721313 large ideals
Thu Dec 11 02:54:20 2008  commencing singleton removal, pass 5
Thu Dec 11 02:57:28 2008  found 176731 singletons
Thu Dec 11 02:57:28 2008  current dataset: 10093734 relations and about 7543291 large ideals
Thu Dec 11 02:57:28 2008  commencing singleton removal, final pass
Thu Dec 11 03:00:49 2008  memory use: 167.8 MB
Thu Dec 11 03:00:49 2008  commencing in-memory singleton removal
Thu Dec 11 03:00:50 2008  begin with 10093734 relations and 8421019 unique ideals
Thu Dec 11 03:01:06 2008  reduce to 7903809 relations and 6154282 ideals in 17 passes
Thu Dec 11 03:01:06 2008  max relations containing the same ideal: 45
Thu Dec 11 03:01:09 2008  reading rational ideals above 720000
Thu Dec 11 03:01:09 2008  reading algebraic ideals above 720000
Thu Dec 11 03:01:09 2008  commencing singleton removal, final pass
Thu Dec 11 03:04:31 2008  keeping 6806288 ideals with weight <= 20, new excess is 822273
Thu Dec 11 03:04:43 2008  memory use: 186.2 MB
Thu Dec 11 03:04:43 2008  commencing in-memory singleton removal
Thu Dec 11 03:04:44 2008  begin with 7905875 relations and 6806288 unique ideals
Thu Dec 11 03:04:56 2008  reduce to 7887728 relations and 6778437 ideals in 11 passes
Thu Dec 11 03:04:56 2008  max relations containing the same ideal: 20
Thu Dec 11 03:05:02 2008  removing 842718 relations and 764991 ideals in 77727 cliques
Thu Dec 11 03:05:02 2008  commencing in-memory singleton removal
Thu Dec 11 03:05:03 2008  begin with 7045010 relations and 6778437 unique ideals
Thu Dec 11 03:05:13 2008  reduce to 6978651 relations and 5946229 ideals in 10 passes
Thu Dec 11 03:05:13 2008  max relations containing the same ideal: 20
Thu Dec 11 03:05:18 2008  removing 612397 relations and 534670 ideals in 77727 cliques
Thu Dec 11 03:05:19 2008  commencing in-memory singleton removal
Thu Dec 11 03:05:19 2008  begin with 6366254 relations and 5946229 unique ideals
Thu Dec 11 03:05:26 2008  reduce to 6325607 relations and 5370445 ideals in 8 passes
Thu Dec 11 03:05:26 2008  max relations containing the same ideal: 20
Thu Dec 11 03:05:31 2008  relations with 0 large ideals: 75786
Thu Dec 11 03:05:31 2008  relations with 1 large ideals: 528587
Thu Dec 11 03:05:31 2008  relations with 2 large ideals: 1508161
Thu Dec 11 03:05:31 2008  relations with 3 large ideals: 2141410
Thu Dec 11 03:05:31 2008  relations with 4 large ideals: 1514008
Thu Dec 11 03:05:31 2008  relations with 5 large ideals: 473107
Thu Dec 11 03:05:31 2008  relations with 6 large ideals: 78623
Thu Dec 11 03:05:31 2008  relations with 7+ large ideals: 5925
Thu Dec 11 03:05:31 2008  commencing 2-way merge
Thu Dec 11 03:05:39 2008  reduce to 3680548 relation sets and 2725386 unique ideals
Thu Dec 11 03:05:39 2008  commencing full merge
Thu Dec 11 03:06:19 2008  memory use: 197.5 MB
Thu Dec 11 03:06:20 2008  found 1799253 cycles, need 1671586
Thu Dec 11 03:06:20 2008  weight of 1671586 cycles is about 117209411 (70.12/cycle)
Thu Dec 11 03:06:20 2008  distribution of cycle lengths:
Thu Dec 11 03:06:20 2008  1 relations: 220348
Thu Dec 11 03:06:20 2008  2 relations: 198992
Thu Dec 11 03:06:20 2008  3 relations: 198435
Thu Dec 11 03:06:20 2008  4 relations: 177304
Thu Dec 11 03:06:20 2008  5 relations: 160729
Thu Dec 11 03:06:20 2008  6 relations: 135962
Thu Dec 11 03:06:20 2008  7 relations: 116735
Thu Dec 11 03:06:20 2008  8 relations: 101380
Thu Dec 11 03:06:20 2008  9 relations: 86198
Thu Dec 11 03:06:20 2008  10+ relations: 275503
Thu Dec 11 03:06:20 2008  heaviest cycle: 17 relations
Thu Dec 11 03:06:21 2008  commencing cycle optimization
Thu Dec 11 03:06:24 2008  start with 9202460 relations
Thu Dec 11 03:06:45 2008  pruned 210499 relations
Thu Dec 11 03:06:45 2008  memory use: 254.2 MB
Thu Dec 11 03:06:45 2008  distribution of cycle lengths:
Thu Dec 11 03:06:45 2008  1 relations: 220348
Thu Dec 11 03:06:45 2008  2 relations: 204053
Thu Dec 11 03:06:45 2008  3 relations: 205528
Thu Dec 11 03:06:45 2008  4 relations: 181869
Thu Dec 11 03:06:45 2008  5 relations: 163921
Thu Dec 11 03:06:45 2008  6 relations: 137494
Thu Dec 11 03:06:45 2008  7 relations: 117891
Thu Dec 11 03:06:45 2008  8 relations: 101113
Thu Dec 11 03:06:45 2008  9 relations: 85271
Thu Dec 11 03:06:45 2008  10+ relations: 254098
Thu Dec 11 03:06:45 2008  heaviest cycle: 17 relations
Thu Dec 11 03:06:52 2008  
Thu Dec 11 03:06:52 2008  commencing linear algebra
Thu Dec 11 03:06:54 2008  read 1671586 cycles
Thu Dec 11 03:07:00 2008  cycles contain 5505912 unique relations
Thu Dec 11 03:09:25 2008  read 5505912 relations
Thu Dec 11 03:09:35 2008  using 20 quadratic characters above 268435314
Thu Dec 11 03:10:15 2008  building initial matrix
Thu Dec 11 03:11:38 2008  memory use: 648.8 MB
Thu Dec 11 03:11:42 2008  read 1671586 cycles
Thu Dec 11 03:12:17 2008  matrix is 1670943 x 1671586 (481.0 MB) with weight 159151327 (95.21/col)
Thu Dec 11 03:12:17 2008  sparse part has weight 112725825 (67.44/col)
Thu Dec 11 03:13:05 2008  filtering completed in 3 passes
Thu Dec 11 03:13:05 2008  matrix is 1648961 x 1649161 (477.4 MB) with weight 157710349 (95.63/col)
Thu Dec 11 03:13:05 2008  sparse part has weight 111961629 (67.89/col)
Thu Dec 11 03:13:32 2008  read 1649161 cycles
Thu Dec 11 03:18:15 2008  matrix is 1648961 x 1649161 (477.4 MB) with weight 157710349 (95.63/col)
Thu Dec 11 03:18:15 2008  sparse part has weight 111961629 (67.89/col)
Thu Dec 11 03:18:16 2008  saving the first 48 matrix rows for later
Thu Dec 11 03:18:17 2008  matrix is 1648913 x 1649161 (458.0 MB) with weight 125936961 (76.36/col)
Thu Dec 11 03:18:17 2008  sparse part has weight 110175293 (66.81/col)
Thu Dec 11 03:18:17 2008  matrix includes 64 packed rows
Thu Dec 11 03:18:17 2008  using block size 65536 for processor cache size 4096 kB
Thu Dec 11 03:18:33 2008  commencing Lanczos iteration (2 threads)
Thu Dec 11 03:18:33 2008  memory use: 469.4 MB
Thu Dec 11 10:10:59 2008  lanczos halted after 26078 iterations (dim = 1648912)
Thu Dec 11 10:11:04 2008  recovered 29 nontrivial dependencies
Thu Dec 11 10:11:04 2008  
Thu Dec 11 10:11:04 2008  commencing square root phase
Thu Dec 11 10:11:04 2008  reading relations for dependency 1
Thu Dec 11 10:11:05 2008  read 825057 cycles
Thu Dec 11 10:11:08 2008  cycles contain 3300817 unique relations
Thu Dec 11 10:14:22 2008  read 3300817 relations
Thu Dec 11 10:14:47 2008  multiplying 2741854 relations
Thu Dec 11 10:23:59 2008  multiply complete, coefficients have about 133.84 million bits
Thu Dec 11 10:24:06 2008  initial square root is modulo 63617
Thu Dec 11 10:40:56 2008  reading relations for dependency 2
Thu Dec 11 10:40:57 2008  read 824435 cycles
Thu Dec 11 10:41:00 2008  cycles contain 3296962 unique relations
Thu Dec 11 10:43:59 2008  read 3296962 relations
Thu Dec 11 10:44:24 2008  multiplying 2740548 relations
Thu Dec 11 10:53:37 2008  multiply complete, coefficients have about 133.77 million bits
Thu Dec 11 10:53:44 2008  initial square root is modulo 63281
Thu Dec 11 11:10:34 2008  prp51 factor: 135683092839561778345179134216468406505969615380817
Thu Dec 11 11:10:34 2008  prp86 factor: 17786284453774220812003991279427789209519280274926855113618447429183098094154853531163
Thu Dec 11 11:10:34 2008  elapsed time 08:40:08

and it would easily fit into 1 GB (my laptop has 2GB RAM).

FYI:

Code:

total relations   needs # more
12484328          408k
13305783          408k
14931206          406k
15733823          415k <-- seems to start to go up here
16956322          613k
17959054          1.00M
19238647          1.2M
20492618          227k
21254686          success!

As it seems to be difficult to estimate the count of relations needed when it is heavily undersieved, it might be a bit less misleading when it says something like "Filtering wants >25% more relations" instead of "Filtering wants 400k more relations".

fivemack · 2008-12-11, 12:39

I don't know if this is practical, but would it be possible, in the common event that #{large ideals} > #{relations} after the first scan through the file, to measure how many new large ideals the last million relations in the file gave, and use (rel-large)/(1-new_large_per_rel) that as an estimate of how many more relations would be needed?

(yes, this estimate is negative in the early stages of sieving where you get more than one new large ideal per relation, but if that happens you can display a 'vastly undersieved' error message)

You will of course get a better estimate if you do this measurement after singleton removal.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Congruence relations	Lee Yiyuan	Miscellaneous Math	7	2012-05-08 12:55
Keeping relations	fivemack	Factoring	1	2009-01-26 17:49
Compressing relations	fivemack	Factoring	5	2007-10-16 15:50
More relations mean many more relations wanted	fivemack	Factoring	7	2007-08-04 17:32
How many relations do we need for 2 ^ 713 -1 ?	thomasn	NFSNET Discussion	10	2003-07-11 19:26

2008-12-07, 11:21	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·3·5²·67 Posts	A ballpark for a 28-bit project, you'd need 20-25M relns. So everything goes as planned so far (seriously). Your log fragments look fairly normal. It doesn't estimate well how many it wants -- until the last stage. The reported wanted number will stay at ~400K, then it will spike up (capped at 1,000,000), and then, on the way down it will be quite precise. Before the spike, never mind the number. All will be fine, right now you are ~ halfway done.

2008-12-07, 14:35	#4
jasonp Tribal Bullet Oct 2004 3²·5·79 Posts	There used to be a 2GB file limit (Microsoft's C runtime library has a bug), but that limit was worked around long ago. You should be more worried about having enough memory for the postprocessing to complete (I'd estimate a C136 needs 1-1.5GB)

2008-12-11, 12:39	#7
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 2×7×461 Posts	I don't know if this is practical, but would it be possible, in the common event that #{large ideals} > #{relations} after the first scan through the file, to measure how many new large ideals the last million relations in the file gave, and use (rel-large)/(1-new_large_per_rel) that as an estimate of how many more relations would be needed? (yes, this estimate is negative in the early stages of sieving where you get more than one new large ideal per relation, but if that happens you can display a 'vastly undersieved' error message) You will of course get a better estimate if you do this measurement after singleton removal.