mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   CADO-NFS (https://www.mersenneforum.org/forumdisplay.php?f=170)
-   -   Parameter explorations for CADO 165-170 digits (https://www.mersenneforum.org/showthread.php?t=25535)

VBCurtis 2020-05-11 17:16

Parameter explorations for CADO 165-170 digits
 
1 Attachment(s)
This thread explores parameter options for 163-172 digit numbers.

Things to determine:
What siever? I=14 vs A=28 vs I=15
2LP or 3LP on side 1?
For 2LP side(s), what lambda?
What lims?

I've attached a first guess at c170 params; As we find faster settings I'll update the file(s) on this first post so best-practices are easy to locate.

First guess: A=28, 3LP, lambda0=1.88 (corresponding to mfb0 = 58.3). Lims possibly too high, at 80M/115M. We should try one much smaller also, like 60/85M.

charybdis 2020-05-13 13:12

I've been sieving the c168 from 5+3_1215L with these parameters, as suggested in the 175-180 thread:

[code]tasks.A = 28
tasks.qmin = 10000000
tasks.lim0 = 80000000
tasks.lim1 = 115000000
tasks.lpb0 = 31
tasks.lpb1 = 31
tasks.sieve.mfb0 = 58
tasks.sieve.mfb1 = 90
tasks.sieve.ncurves0 = 20
tasks.sieve.ncurves1 = 13[/code]

19.1M CPU-seconds of sieving produced the following:

[code]Wed May 13 12:46:32 2020 Msieve v. 1.54 (SVN 1030M)
Wed May 13 12:46:32 2020 random seeds: 9ffee2f6 41951ee0
Wed May 13 12:46:32 2020 factoring 245609880520494362682705606347409092539758689544648910766910287096779616823469115034356435763879242747931684930827717014249287135786561075491831877899088616371815708911 (168 digits)
Wed May 13 12:46:33 2020 searching for 15-digit factors
Wed May 13 12:46:33 2020 commencing number field sieve (168-digit input)
Wed May 13 12:46:33 2020 R0: -223470566836941710449157486820982
Wed May 13 12:46:33 2020 R1: 79664348591951467630451
Wed May 13 12:46:33 2020 A0: -7589872577078303699524772499775295445
Wed May 13 12:46:33 2020 A1: -196971342286318522372786728569142
Wed May 13 12:46:33 2020 A2: 55213576168005775518349496
Wed May 13 12:46:33 2020 A3: -122057413788280381324
Wed May 13 12:46:33 2020 A4: -6005969398245
Wed May 13 12:46:33 2020 A5: 1324260
Wed May 13 12:46:33 2020 skew 1.00, size 2.278e-16, alpha -6.095, combined = 5.596e-15 rroots = 3
Wed May 13 12:46:33 2020
Wed May 13 12:46:33 2020 commencing relation filtering
Wed May 13 12:46:33 2020 setting target matrix density to 100.0
Wed May 13 12:46:33 2020 estimated available RAM is 15845.9 MB
Wed May 13 12:46:33 2020 commencing duplicate removal, pass 1
Wed May 13 13:04:10 2020 found 40021465 hash collisions in 189567218 relations
Wed May 13 13:04:32 2020 commencing duplicate removal, pass 2
Wed May 13 13:07:48 2020 found 43897302 duplicates and 145669916 unique relations
Wed May 13 13:07:48 2020 memory use: 1321.5 MB
Wed May 13 13:07:49 2020 reading ideals above 89194496
Wed May 13 13:07:49 2020 commencing singleton removal, initial pass
Wed May 13 13:18:08 2020 memory use: 3012.0 MB
Wed May 13 13:18:08 2020 reading all ideals from disk
Wed May 13 13:18:24 2020 memory use: 2748.9 MB
Wed May 13 13:18:28 2020 commencing in-memory singleton removal
Wed May 13 13:18:32 2020 begin with 145669916 relations and 140458395 unique ideals
Wed May 13 13:19:16 2020 reduce to 72650875 relations and 58132947 ideals in 17 passes
Wed May 13 13:19:16 2020 max relations containing the same ideal: 28
Wed May 13 13:19:21 2020 reading ideals above 720000
Wed May 13 13:19:22 2020 commencing singleton removal, initial pass
Wed May 13 13:26:59 2020 memory use: 1506.0 MB
Wed May 13 13:27:00 2020 reading all ideals from disk
Wed May 13 13:27:25 2020 memory use: 2815.9 MB
Wed May 13 13:27:30 2020 keeping 68118732 ideals with weight <= 200, target excess is 360258
Wed May 13 13:27:36 2020 commencing in-memory singleton removal
Wed May 13 13:27:40 2020 begin with 72650877 relations and 68118732 unique ideals
Wed May 13 13:28:22 2020 reduce to 72634839 relations and 68102690 ideals in 10 passes
Wed May 13 13:28:22 2020 max relations containing the same ideal: 200
Wed May 13 13:28:48 2020 removing 7760595 relations and 6760595 ideals in 1000000 cliques
Wed May 13 13:28:50 2020 commencing in-memory singleton removal
Wed May 13 13:28:54 2020 begin with 64874244 relations and 68102690 unique ideals
Wed May 13 13:29:39 2020 reduce to 64141232 relations and 60595322 ideals in 12 passes
Wed May 13 13:29:39 2020 max relations containing the same ideal: 191
Wed May 13 13:30:01 2020 removing 5952038 relations and 4952038 ideals in 1000000 cliques
Wed May 13 13:30:03 2020 commencing in-memory singleton removal
Wed May 13 13:30:06 2020 begin with 58189194 relations and 60595322 unique ideals
Wed May 13 13:30:40 2020 reduce to 57683158 relations and 55128834 ideals in 10 passes
Wed May 13 13:30:40 2020 max relations containing the same ideal: 181
Wed May 13 13:31:01 2020 removing 5427833 relations and 4427833 ideals in 1000000 cliques
Wed May 13 13:31:02 2020 commencing in-memory singleton removal
Wed May 13 13:31:05 2020 begin with 52255325 relations and 55128834 unique ideals
Wed May 13 13:31:32 2020 reduce to 51779832 relations and 50217186 ideals in 9 passes
Wed May 13 13:31:32 2020 max relations containing the same ideal: 169
Wed May 13 13:31:51 2020 removing 5205947 relations and 4205947 ideals in 1000000 cliques
Wed May 13 13:31:52 2020 commencing in-memory singleton removal
Wed May 13 13:31:55 2020 begin with 46573885 relations and 50217186 unique ideals
Wed May 13 13:32:19 2020 reduce to 46074717 relations and 45502789 ideals in 9 passes
Wed May 13 13:32:19 2020 max relations containing the same ideal: 158
Wed May 13 13:32:35 2020 removing 1163580 relations and 1009552 ideals in 154028 cliques
Wed May 13 13:32:36 2020 commencing in-memory singleton removal
Wed May 13 13:32:38 2020 begin with 44911137 relations and 45502789 unique ideals
Wed May 13 13:32:54 2020 reduce to 44886292 relations and 44468291 ideals in 6 passes
Wed May 13 13:32:54 2020 max relations containing the same ideal: 157
Wed May 13 13:33:16 2020 relations with 0 large ideals: 1286
Wed May 13 13:33:16 2020 relations with 1 large ideals: 1573
Wed May 13 13:33:16 2020 relations with 2 large ideals: 30197
Wed May 13 13:33:16 2020 relations with 3 large ideals: 293969
Wed May 13 13:33:16 2020 relations with 4 large ideals: 1561336
Wed May 13 13:33:16 2020 relations with 5 large ideals: 4986951
Wed May 13 13:33:16 2020 relations with 6 large ideals: 10038808
Wed May 13 13:33:16 2020 relations with 7+ large ideals: 27972172
Wed May 13 13:33:16 2020 commencing 2-way merge
Wed May 13 13:33:38 2020 reduce to 27425585 relation sets and 27007584 unique ideals
Wed May 13 13:33:38 2020 commencing full merge
Wed May 13 13:39:32 2020 memory use: 2958.8 MB
Wed May 13 13:39:34 2020 found 12476332 cycles, need 12451784
Wed May 13 13:39:37 2020 weight of 12451784 cycles is about 1245332899 (100.01/cycle)
Wed May 13 13:39:37 2020 distribution of cycle lengths:
Wed May 13 13:39:37 2020 1 relations: 1167437
Wed May 13 13:39:37 2020 2 relations: 1129539
Wed May 13 13:39:37 2020 3 relations: 1141919
Wed May 13 13:39:37 2020 4 relations: 1059954
Wed May 13 13:39:37 2020 5 relations: 1004089
Wed May 13 13:39:37 2020 6 relations: 931457
Wed May 13 13:39:37 2020 7 relations: 840380
Wed May 13 13:39:37 2020 8 relations: 749799
Wed May 13 13:39:37 2020 9 relations: 687709
Wed May 13 13:39:37 2020 10+ relations: 3739501
Wed May 13 13:39:37 2020 heaviest cycle: 28 relations
Wed May 13 13:39:39 2020 commencing cycle optimization
Wed May 13 13:39:54 2020 start with 92367168 relations
Wed May 13 13:41:53 2020 pruned 2737568 relations
Wed May 13 13:41:54 2020 memory use: 2787.8 MB
Wed May 13 13:41:54 2020 distribution of cycle lengths:
Wed May 13 13:41:54 2020 1 relations: 1167437
Wed May 13 13:41:54 2020 2 relations: 1158374
Wed May 13 13:41:54 2020 3 relations: 1184944
Wed May 13 13:41:54 2020 4 relations: 1091585
Wed May 13 13:41:54 2020 5 relations: 1035797
Wed May 13 13:41:54 2020 6 relations: 952023
Wed May 13 13:41:54 2020 7 relations: 858487
Wed May 13 13:41:54 2020 8 relations: 761081
Wed May 13 13:41:54 2020 9 relations: 694773
Wed May 13 13:41:54 2020 10+ relations: 3547283
Wed May 13 13:41:54 2020 heaviest cycle: 28 relations
Wed May 13 13:42:13 2020 RelProcTime: 3340
Wed May 13 13:42:17 2020
Wed May 13 13:42:17 2020 commencing linear algebra
Wed May 13 13:42:18 2020 read 12451784 cycles
Wed May 13 13:42:37 2020 cycles contain 44543120 unique relations
Wed May 13 13:46:53 2020 read 44543120 relations
Wed May 13 13:47:48 2020 using 20 quadratic characters above 4294917295
Wed May 13 13:50:38 2020 building initial matrix
Wed May 13 13:57:23 2020 memory use: 5986.7 MB
Wed May 13 13:58:04 2020 read 12451784 cycles
Wed May 13 13:58:06 2020 matrix is 12451607 x 12451784 (5093.3 MB) with weight 1553697525 (124.78/col)
Wed May 13 13:58:06 2020 sparse part has weight 1185747861 (95.23/col)
Wed May 13 14:00:02 2020 filtering completed in 2 passes
Wed May 13 14:00:04 2020 matrix is 12450174 x 12450351 (5093.2 MB) with weight 1553641047 (124.79/col)
Wed May 13 14:00:04 2020 sparse part has weight 1185735705 (95.24/col)
Wed May 13 14:01:07 2020 matrix starts at (0, 0)
Wed May 13 14:01:09 2020 matrix is 12450174 x 12450351 (5093.2 MB) with weight 1553641047 (124.79/col)
Wed May 13 14:01:09 2020 sparse part has weight 1185735705 (95.24/col)
Wed May 13 14:01:09 2020 saving the first 48 matrix rows for later
Wed May 13 14:01:10 2020 matrix includes 64 packed rows
Wed May 13 14:01:11 2020 matrix is 12450126 x 12450351 (4936.6 MB) with weight 1301689606 (104.55/col)
Wed May 13 14:01:11 2020 sparse part has weight 1169600559 (93.94/col)
Wed May 13 14:01:11 2020 using block size 8192 and superblock size 884736 for processor cache size 9216 kB
Wed May 13 14:01:42 2020 commencing Lanczos iteration (6 threads)
Wed May 13 14:01:43 2020 memory use: 4708.1 MB
Wed May 13 14:02:09 2020 linear algebra at 0.0%, ETA 56h57m[/code]

This strikes me as being a bit slower than we want; I was getting times of 55-60M CPU-seconds at c178. It also doesn't compare too well with a c167 that I ran in March with the parameters
[code]tasks.I = 14
tasks.qmin = 7000000
tasks.lim0 = 38000000
tasks.lim1 = 60000000
tasks.lpb0 = 31
tasks.lpb1 = 32
tasks.sieve.mfb0 = 62
tasks.sieve.mfb1 = 64
tasks.sieve.ncurves0 = 18
tasks.sieve.ncurves1 = 25[/code]
which produced a 9M matrix after 16M CPU-seconds of sieving (not entirely comparable as I didn't run it on exactly the same machines, but if anything it would be even faster on the ones I'm using at the moment).

The obvious difference between these two jobs is 2LP vs 3LP, though the lims could also be having an effect - we need more runs to see what's really going on. Does anyone have some more numbers of this size hanging around?

swellman 2020-05-13 13:47

Kamada’s site has some suitable GNFS jobs available

[url]https://stdkmd.net/nrr/wanted.htm#suitableforgnfs[/url]

VBCurtis 2020-05-13 14:58

I would say that both observations are correct- lims are too big, and 3LP may not be suitable. It's also likely that I=14 is better than A=28; it may be that these even A-values are only faster in unusual cases (say, a low-yielding poly that would normally be a size to use I=14).

That said, 20% slower for 1 digit larger isn't a huge miss; clearly not faster, but not slower-enough to rule out 3LP as still possibly a good idea. The larger-than-your-c167 matrix tells us you didn't oversieve, and we know 3LP matrices turn out bigger.

If we go 2LP on both sides, I suggest also using lambda0 & lambda1 of 1.85 or so to reduce the number of relations needed.

So, possible changes:
I=14
lim's of, say, 50M and 70M
2LP

My notes include a C167 sent to nfs@home 14e queue, in which I used lim's of 67M on both sides. ggnfs likes power-of-2 lim's, but that indicates 50/70 are more likely correct than 80/110.

chris2be8 2020-05-13 15:44

[QUOTE=charybdis;545232]Does anyone have some more numbers of this size hanging around?[/QUOTE]

Here are the smallest 3 numbers in the Brent tables:
[code]
(95^128+1)/267800772103727976108674546747470814168968227593565342652934454279571759350601155586
# 170 digits:
52578676770574634512595466847841062400406219898703178016790505924363888689365475143019601569100893681427169623580739917336603746042987149267328695780988068362551904560641
[/code]

[code]
(24^179+1)/43663605833505119109437514756662567033795467630332680195392449662667612167525
# 171 digits:
261633088864353542789446012422373060420258849456315466227530404025437348932344174393051880283883795455352667032238196892137483412153757222899501668268383799664562709253229
[/code]

[code]
(86^131-1)/127296350506000474708670512286771610891902627605122671646543238329335622840049145135
# 171 digits:
206291417462093576497275239580773052795596055350565606087502662805051224044201602337850673455835775692863740037805407606265476824913591751307682500480113600344276700606001
[/code]

If you don't want them I can do them with NFS@Home.

Chris

charybdis 2020-05-13 15:56

[QUOTE=chris2be8;545254]Here are the smallest 3 numbers in the Brent tables:
<snip>

If you don't want them I can do them with NFS@Home.

Chris[/QUOTE]

Thank you! I'd be happy to do at least some of these, though I'll be doing the c170 from Aliquot 3366 first if it survives ECM. I take it all of these numbers have had enough ECM?

chris2be8 2020-05-13 16:18

As far as I know everything in the Brent tables has been ECMed to at least t60.

Chris

charybdis 2020-05-15 13:51

The c170 from Aliquot 3366 has built a matrix:

[code]Fri May 15 13:30:04 2020 Msieve v. 1.54 (SVN 1030M)
Fri May 15 13:30:04 2020 random seeds: 85bae23a bde7ff6e
Fri May 15 13:30:04 2020 factoring 86631352523777317443318741611426541309296773170541288874048777015161155735273728068286738505405324469613265780485465094938752555194870805288145702027767872412047031948633 (170 digits)
Fri May 15 13:30:05 2020 searching for 15-digit factors
Fri May 15 13:30:05 2020 commencing number field sieve (170-digit input)
Fri May 15 13:30:05 2020 R0: -997917629737604869042704488941047
Fri May 15 13:30:05 2020 R1: 2231945554206892494565181
Fri May 15 13:30:05 2020 A0: 8911247040789664012374838655454593624736
Fri May 15 13:30:05 2020 A1: 58966576361359993167845008084069822
Fri May 15 13:30:05 2020 A2: -14226780425800550539646724351
Fri May 15 13:30:05 2020 A3: -1607926381901953698037
Fri May 15 13:30:05 2020 A4: 79303929919170
Fri May 15 13:30:05 2020 A5: 2457000
Fri May 15 13:30:05 2020 skew 1.00, size 1.375e-16, alpha -8.660, combined = 2.335e-15 rroots = 5
Fri May 15 13:30:05 2020
Fri May 15 13:30:05 2020 commencing relation filtering
Fri May 15 13:30:05 2020 setting target matrix density to 100.0
Fri May 15 13:30:05 2020 estimated available RAM is 15845.9 MB
Fri May 15 13:30:05 2020 commencing duplicate removal, pass 1
...
Fri May 15 13:50:46 2020 found 59360613 hash collisions in 213148587 relations
Fri May 15 13:51:08 2020 commencing duplicate removal, pass 2
Fri May 15 13:55:12 2020 found 75754247 duplicates and 137394340 unique relations
...
Fri May 15 14:40:19 2020 matrix is 10495776 x 10496000 (4191.2 MB) with weight 1118174547 (106.53/col)
Fri May 15 14:40:19 2020 sparse part has weight 993750449 (94.68/col)
Fri May 15 14:40:19 2020 using block size 8192 and superblock size 884736 for processor cache size 9216 kB
Fri May 15 14:40:46 2020 commencing Lanczos iteration (6 threads)
Fri May 15 14:40:46 2020 memory use: 3956.9 MB
Fri May 15 14:41:08 2020 linear algebra at 0.0%, ETA 40h11m[/code]

This took 23.3M CPU-seconds of sieving with parameters
[code]tasks.I = 14
tasks.qmin = 7000000
tasks.lim0 = 50000000
tasks.lim1 = 70000000
tasks.lpb0 = 31
tasks.lpb1 = 32
tasks.sieve.mfb0 = 58
tasks.sieve.mfb1 = 60
tasks.sieve.lambda0 = 1.85
tasks.sieve.lambda1 = 1.85
tasks.sieve.ncurves0 = 20
tasks.sieve.ncurves1 = 25[/code]

I've seen somewhere that sieve time should double every 5.5 digits, in which case this is still a bit slower than we'd like based on the timings at c177/8.

I'll do 95^128+1 next; Chris, do I need to reserve this somewhere? As for parameters, should I maybe try A=28 instead of I=14 and keep everything else the same?

VBCurtis 2020-05-15 14:49

Well, at least the matrix got smaller! 213M rels at 31/32 vs 189M at 31/31/3LP; we could tighten lambda a bit more (1.84 and 1.83, respectively) and expect rels_wanted to drop another ~5M or so. I don't see that getting us the 5-10% speed improvement we "expect", though.

Trying A=28 all else equal should help us decide which siever to stick with for further testing; good plan. It would be nice to compare Q-final for these two runs once you do A=28.

My prior ggnfs runs at 166-170 digits had matrices 9-10M in size, with 275M relations (EDIT: 32/32LP) and no restriction on lambda (mfb=63). I used 170 as my cutoff between 14e and 15e, but I expect CADO to be faster on I=14 than I=15 here.

chris2be8 2020-05-15 15:32

This thread should do for a reservation. In practice no one but me is working on the Brent tables.

Chris

charybdis 2020-05-17 21:44

[code]Sun May 17 19:51:22 2020 Msieve v. 1.54 (SVN 1030M)
Sun May 17 19:51:22 2020 random seeds: 74f448f4 3f9ca822
Sun May 17 19:51:22 2020 factoring 52578676770574634512595466847841062400406219898703178016790505924363888689365475143019601569100893681427169623580739917336603746042987149267328695780988068362551904560641 (170 digits)
Sun May 17 19:51:22 2020 searching for 15-digit factors
Sun May 17 19:51:23 2020 commencing number field sieve (170-digit input)
Sun May 17 19:51:23 2020 R0: -647379397577956473141846534803906
Sun May 17 19:51:23 2020 R1: 34336932387135505576189
Sun May 17 19:51:23 2020 A0: 67111045429448622534099281184997406601
Sun May 17 19:51:23 2020 A1: 247012654371586877957224260881448
Sun May 17 19:51:23 2020 A2: -65521455613079545959441611
Sun May 17 19:51:23 2020 A3: -56319283841035187455
Sun May 17 19:51:23 2020 A4: 3534129102237
Sun May 17 19:51:23 2020 A5: 462210
Sun May 17 19:51:23 2020 skew 1.00, size 1.512e-16, alpha -4.882, combined = 3.112e-15 rroots = 5
Sun May 17 19:51:23 2020
Sun May 17 19:51:23 2020 commencing relation filtering
Sun May 17 19:51:23 2020 setting target matrix density to 100.0
Sun May 17 19:51:23 2020 estimated available RAM is 15845.4 MB
Sun May 17 19:51:23 2020 commencing duplicate removal, pass 1
Sun May 17 20:10:03 2020 found 49623560 hash collisions in 200069821 relations
Sun May 17 20:10:25 2020 commencing duplicate removal, pass 2
Sun May 17 20:14:03 2020 found 61168048 duplicates and 138901773 unique relations
...
Sun May 17 20:55:50 2020 matrix is 9099996 x 9100221 (3602.2 MB) with weight 949734284 (104.36/col)
Sun May 17 20:55:50 2020 sparse part has weight 853284443 (93.77/col)
Sun May 17 20:55:50 2020 using block size 8192 and superblock size 884736 for processor cache size 9216 kB
Sun May 17 20:56:12 2020 commencing Lanczos iteration (6 threads)
Sun May 17 20:56:12 2020 memory use: 3428.1 MB
Sun May 17 20:56:30 2020 linear algebra at 0.0%, ETA 28h16m[/code]

23.7M CPU-seconds of sieving with A=28; the polynomial is supposedly slightly better than the one from the previous job (3.76e-13 vs 3.53e-13) which would suggest I=14 is a little faster. The matrix has come out smaller though, despite a similar number of unique relations (and, in fact, a smaller excess of relations over ideals). Not really clear which will end up being fastest when everything else is optimised.

Final Q-values were 157.7M for the I=14 job and 104.3M for this one; both started at 7M.


All times are UTC. The time now is 12:47.

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