mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Msieve (https://www.mersenneforum.org/forumdisplay.php?f=83)
-   -   So, HOW many more relations does it want? (https://www.mersenneforum.org/showthread.php?t=11102)

Andi47 2008-12-07 11:09

So, HOW many more relations does it want?
 
I am currently factoring [URL="http://mersennewiki.org/index.php/Base_10_Still_Open#HP548"]hp548.74[/URL] 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
[/code]

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 [b]<-- LOL[/b]
Sat Dec 06 12:09:08 2008 max relations containing the same ideal: 2
Sat Dec 06 12:09:08 2008 filtering wants [b]402855[/b] more relations
Sat Dec 06 12:09:08 2008 elapsed time 00:19:18[/code]

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 [b]<--ROTFL[/b]
Sat Dec 06 20:11:15 2008 max relations containing the same ideal: 2
Sat Dec 06 20:11:15 2008 filtering wants [b]402852[/b] more relations
Sat Dec 06 20:11:15 2008 elapsed time 00:19:01[/code]

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 [b]403524[/b] more relations
Sun Dec 07 11:48:07 2008 elapsed time 00:21:56
[/code]

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.

[I]It[/I] doesn't estimate well how many [I]it[/I] 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=Batalov;152348]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.

[I]It[/I] doesn't estimate well how many [I]it[/I] 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.[/QUOTE]

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=jasonp;152363]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)[/QUOTE]

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[/code]

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![/code]

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.


All times are UTC. The time now is 01:31.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.