mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   CADO-NFS (https://www.mersenneforum.org/forumdisplay.php?f=170)
-   -   CADO NFS (https://www.mersenneforum.org/showthread.php?t=11948)

VBCurtis 2018-05-04 15:26

Excellent! Q=16M is in the optimistic side of the expected range.

The only reason to adjust from 2 threads per process that I know of is to save memory. I=15 uses something on the order of 2GB per process, but the thread pool shares that footprint; a 4GB 4-core machine would want to run 4 threads on a single client rather than two on two clients to save memory when I=15 (Say, GNFS-180+). I believe I=14 uses around 500MB per client, which should be no problem even with multiple clients running.

EdH 2018-05-04 15:42

[QUOTE=VBCurtis;486954]Excellent! Q=16M is in the optimistic side of the expected range.

The only reason to adjust from 2 threads per process that I know of is to save memory. I=15 uses something on the order of 2GB per process, but the thread pool shares that footprint; a 4GB 4-core machine would want to run 4 threads on a single client rather than two on two clients to save memory when I=15 (Say, GNFS-180+). I believe I=14 uses around 500MB per client, which should be no problem even with multiple clients running.[/QUOTE]
Thanks. Most of my i7s (actually, the others, too) are memory deficient at 4GB. The server has 16GB.

wombatman 2018-05-04 17:37

[QUOTE=VBCurtis;486910]wombatman-
Here's my guess at c165 params:
[code]###########################################################################
# Polynomial selection
###########################################################################

tasks.polyselect.degree = 5

tasks.polyselect.P = 1200000
tasks.polyselect.admin = 1500
tasks.polyselect.admax = 6e5
tasks.polyselect.adrange = 960
tasks.polyselect.incr = 60
tasks.polyselect.nq = 15625
tasks.polyselect.nrkeep = 100
tasks.polyselect.ropteffort = 15

###########################################################################
# Sieve
###########################################################################

tasks.I = 14
tasks.sieve.qmin = 7000000
lim0 = 38000000
lim1 = 60000000
lpb0 = 31
lpb1 = 32
tasks.sieve.mfb0 = 62
tasks.sieve.mfb1 = 64
tasks.sieve.ncurves0 = 18
tasks.sieve.ncurves1 = 25
tasks.sieve.qrange = 2000

###########################################################################
# Filtering
###########################################################################

tasks.filter.purge.keep = 175
tasks.filter.maxlevel = 32
tasks.filter.target_density = 160.0
[/code]
Note that bwc.interval is just a "how often we update the screen" setting; I like it at 500 so I get more frequent screen output.
The poly select should take ~1.4M cpu-seconds, which is 4x longer than Ed's C155 file. I did a CADO poly select for C166 a month or two ago, and spent 1.55M cpu-seconds; I adjusted params a bit lower for your C164.
If you could report the CPU and wall-clock times for size-opt, root-opt, sieve, LA as Ed did, that would help me out for future optimization. If you happen to see the maximum Q sieved, that helps refine alim/rlim selection.[/QUOTE]

Thanks Curtis. I'll try and get this started tonight and report on all requested times when it finishes.

VictordeHolland 2018-05-05 12:43

Does anybody got CADO-NFS working under windoz?
On Ubuntu it is super easy with "git clone" and "make" and it will get all the packages it needs.

I compiled GMP, ECM and mlucas on Windows using Mingw, but this is a totally different beast. Even with the instructions included in the git repo :(. But I'm still a newbie with compiling....

EdH 2018-05-06 02:33

The C155 is in LA:
[code]
Sending workunit c155_sieving_27572000-27574000 to client
Adding workunit c155_sieving_27592000-27594000 to database
Reached target of 137934925 relations, now have 137935755
[/code]

VBCurtis 2018-05-06 02:51

Excellent! I'm trying to pick lim's such that sieving completes somewhere between the midpoint of the lim's and the higher lim; for the C155 params I set, that would be 25 to 33M. 27 lands nicely in that range. :) My GGNFS run of a similar input size sieved to 28M, but msieve needs fewer relations to build a matrix so I think this still indicates CADO yield is superior to GGNFS. Your run needed 23MQ for 137M raw relations, a yield of almost exactly 6.0.

As input size grows, the sieve range will grow faster than the lim's grow; this is consistent with choices on the 14e queue on nfs@home, and accepts a small decrease in yield in trade for hopes of a smaller matrix. CADO sievers appear to perform much better at relatively large Q than GGNFS, so I wonder if we ought to test even-smaller lim's on the 150-170 digit range.

henryzz 2018-05-06 05:09

[QUOTE=VictordeHolland;487012]Does anybody got CADO-NFS working under windoz?
On Ubuntu it is super easy with "git clone" and "make" and it will get all the packages it needs.

I compiled GMP, ECM and mlucas on Windows using Mingw, but this is a totally different beast. Even with the instructions included in the git repo :(. But I'm still a newbie with compiling....[/QUOTE]

I believe natively on windows isn't possible. It runs easily on the Linux subsystem on Windows 10

EdH 2018-05-06 17:39

And, the final results:
[code]
Info:Polynomial Selection (size optimized): Aggregate statistics:
Info:Polynomial Selection (size optimized): potential collisions: 150312
Info:Polynomial Selection (size optimized): raw lognorm (nr/min/av/max/std): 152195/46.670/56.086/63.060/1.112
Info:Polynomial Selection (size optimized): optimized lognorm (nr/min/av/max/std): 152195/45.120/50.015/56.830/1.370
Info:Polynomial Selection (size optimized): Total time: 303408
Info:Polynomial Selection (root optimized): Aggregate statistics:
Info:Polynomial Selection (root optimized): Total time: 12391.1
Info:Polynomial Selection (root optimized): Rootsieve time: 12389.6
Info:Generate Factor Base: Total cpu/real time for makefb: 38.09/7.7912
Info:Generate Free Relations: Total cpu/real time for freerel: 2481.92/322.779
Info:Lattice Sieving: Aggregate statistics:
Info:Lattice Sieving: Total number of relations: 137935755
Info:Lattice Sieving: Average J: 7702.62 for 1391605 special-q, max bucket fill: 0.618744
Info:Lattice Sieving: Total CPU time: 5.15512e+06s
Info:Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 768.46/444.318
Info:Filtering - Duplicate Removal, splitting pass: Aggregate statistics:
Info:Filtering - Duplicate Removal, splitting pass: CPU time for dup1: 444.1s
Info:Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 2034.56/409.591
Info:Filtering - Singleton removal: Total cpu/real time for purge: 888.21/283.444
Info:Filtering - Merging: Total cpu/real time for merge: 1090.49/979.903
Info:Filtering - Merging: Total cpu/real time for replay: 143.67/120.943
Info:Linear Algebra: Total cpu/real time for bwc: 440875/0.000195265
Info:Linear Algebra: Aggregate statistics:
Info:Linear Algebra: Krylov: WCT time 36874.43
Info:Linear Algebra: Lingen CPU time 1438.56, WCT time 219.83
Info:Linear Algebra: Mksol: WCT time 19838.11
Info:Quadratic Characters: Total cpu/real time for characters: 173.52/48.1477
Info:Square Root: Total cpu/real time for sqrt: 10010.9/1382.47
Info:HTTP server: Shutting down HTTP server
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 5.92942e+06/97592.1
Info:root: Cleaning up computation data in /tmp/cado.xp9ko4wu
106603488380168454820927220360012878679207958575989291522270608237193062808643 102639592829741105772054196573991675900716567808038066803341933521790711307779
[/code]During the sieving, I lost three i7 clients for an undetermined time. I restarted all three.

The core count was still around 170, but I have shifted some machines around and actually removed some dual core low end ones from the mix. So, the "mix" was slightly different from the previous run(s).

VBCurtis 2018-05-06 18:17

Looks like CADO is stretching its lead: C150 took 3.71M cpu-sec, while C155 took 5.93M cpu-sec. That's well under a doubling of time. My prior results showed a "double every 6 digits" scaling from C100 to C132; comparing these two times suggests that scaling is consistent up here in "meaningful work" territory.

I've yet to see someone dispute that msieve-GGNFS scales very close to doubling-every-5-digits, so it looks like even with the slow LA phase CADO may be the package of choice at GNFS150+!

If you get a chance to run a similar-sized number (say, within a factor of 2) with msieve/GGNFS, I'm quite interested to see the wall-clock comparison.

EdH 2018-05-07 01:12

If things go as planned, I'll start the same C155 in the morning using the same machines.

LaurV 2018-05-07 04:12

[QUOTE=VBCurtis;487091]If you get a chance to run a similar-sized number (say, within a factor of 2) with msieve/GGNFS [/QUOTE]
Does yafu counts? (we run our aliquot sequences in this range and may have logs, and yafu is using msieve/ggnfs, albeit not the last version).

EdH 2018-05-07 15:48

[QUOTE=EdH;487104]If things go as planned, I'll start the same C155 in the morning using the same machines.[/QUOTE]I had a troublesome start. I'll have to try again tomorrow.

[QUOTE=LaurV;487110]Does yafu counts? (we run our aliquot sequences in this range and may have logs, and yafu is using msieve/ggnfs, albeit not the last version).[/QUOTE]Curtis might be able to calculate some details, but to get a comparison wall clock time, I plan to use the same machines with the same composite to run my msieve/ggnfs scripts and compare the wall times directly.

But, thanks and Curtis may have a use for the logs.

VBCurtis 2018-05-07 16:54

[QUOTE=LaurV;487110]Does yafu counts? (we run our aliquot sequences in this range and may have logs, and yafu is using msieve/ggnfs, albeit not the last version).[/QUOTE]

Definitely! Just need wall-clock time for poly select, sieving, and LA; and the CPU specs for the machine used.
Ed's testing is sticking to inputs a multiple a 5 digits, so data you have for C145, 150,155,... will be quite helpful. I'll be doing CADO runs on these sizes on single machines, so I can compare my results to yours to get a sense of the relative speed of the two packages.

EdH 2018-05-09 04:19

Well, the polyselect and sieving time came in just under the sleep time for my slumber set of machines. I think that was longer than cado, but I didn't check. The LA has an ETA about six hours from now. It was expecting 7h18m at the start.

I was noticing that there are directions for running cado-nfs to LA, programming cado-nfs to stop there, perform a couple steps and transfer everything to msieve for the LA. As soon as I understand that process a bit more and can automate it, I will try that method with this composite and see if it would save even more.

More to follow in the morning...

EdH 2018-05-09 14:58

C155 msieve/ggnfs results are in:

Started process at day0 08:20:04 with a five minute poly select deadline:
[code]
Tue May 8 08:20:34 2018 Msieve v. 1.54 (SVN 1015)
Tue May 8 08:20:34 2018 random seeds: 2f149115 be482431
Tue May 8 08:20:34 2018 factoring 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897 (155 digits)
Tue May 8 08:20:35 2018 searching for 15-digit factors
Tue May 8 08:20:35 2018 commencing number field sieve (155-digit input)
Tue May 8 08:20:35 2018 commencing number field sieve polynomial selection
Tue May 8 08:20:35 2018 polynomial degree: 5
Tue May 8 08:20:35 2018 max stage 1 norm: 8.07e+23
Tue May 8 08:20:35 2018 max stage 2 norm: 4.96e+21
Tue May 8 08:20:35 2018 min E-value: 2.38e-12
Tue May 8 08:20:35 2018 poly select deadline: 300
Tue May 8 08:20:35 2018 time limit set to 0.08 CPU-hours
Tue May 8 08:20:35 2018 expecting poly E from 2.51e-12 to > 2.89e-12
Tue May 8 08:20:35 2018 searching leading coefficients from 1 to 3000
Tue May 8 08:34:05 2018 polynomial selection complete
Tue May 8 08:34:05 2018 R0: -3908239679572398037902061722952
Tue May 8 08:34:05 2018 R1: 4396266218171701
Tue May 8 08:34:05 2018 A0: -3110911159201674198111127589701474714298715
Tue May 8 08:34:05 2018 A1: 32056958887872842584995494485398422
Tue May 8 08:34:05 2018 A2: 591851843466883645077818327
Tue May 8 08:34:05 2018 A3: -4151561972490124674
Tue May 8 08:34:05 2018 A4: -21071420652
Tue May 8 08:34:05 2018 A5: 12
Tue May 8 08:34:05 2018 skew 194465259.33, size 3.996e-15, alpha -7.245, combined = 2.484e-12 rroots = 5
Tue May 8 08:34:05 2018 elapsed time 00:13:31
[/code]Sieving began at day0 08:35:05 across 36 machines (~170 cores):
[code]Tue May 08 08:35:05 2018 -> factmsieve.py (v0.86)
Tue May 08 08:35:05 2018 -> This is client 1 of 36
Tue May 08 08:35:05 2018 -> Running on 4 Cores with 2 hyper-threads per Core
Tue May 08 08:35:05 2018 -> Working with NAME = comp
Tue May 08 08:35:05 2018 -> Selected lattice siever: gnfs-lasieve4I14e
Tue May 08 08:35:05 2018 -> Creating param file to detect parameter changes...
Tue May 08 08:35:05 2018 -> Running setup ...
Tue May 08 08:35:05 2018 -> Estimated minimum relations needed: 6.03237e+07
Tue May 08 08:35:05 2018 -> cleaning up before a restart
Tue May 08 08:35:05 2018 -> Running lattice siever ...
Tue May 08 08:35:05 2018 -> entering sieving loop
Tue May 08 08:35:05 2018 -> making sieve job for q = 13550000 in 13550000 .. 13562500 as file comp.job.T0
[/code]Linear Algebra began at day0 22:31:16:
[code]
Tue May 8 22:31:16 2018 commencing linear algebra
Tue May 8 22:31:17 2018 read 3995271 cycles
Tue May 8 22:31:21 2018 cycles contain 11109792 unique relations
Tue May 8 22:32:25 2018 read 11109792 relations
Tue May 8 22:32:36 2018 using 20 quadratic characters above 4294917295
Tue May 8 22:33:24 2018 building initial matrix
Tue May 8 22:34:56 2018 memory use: 1526.8 MB
Tue May 8 22:34:57 2018 read 3995271 cycles
Tue May 8 22:34:58 2018 matrix is 3995094 x 3995271 (1210.4 MB) with weight 377883871 (94.58/col)
Tue May 8 22:34:58 2018 sparse part has weight 269359854 (67.42/col)
Tue May 8 22:35:26 2018 filtering completed in 2 passes
Tue May 8 22:35:27 2018 matrix is 3994383 x 3994560 (1210.4 MB) with weight 377860202 (94.59/col)
Tue May 8 22:35:27 2018 sparse part has weight 269354323 (67.43/col)
Tue May 8 22:35:45 2018 matrix starts at (0, 0)
Tue May 8 22:35:46 2018 matrix is 3994383 x 3994560 (1210.4 MB) with weight 377860202 (94.59/col)
Tue May 8 22:35:46 2018 sparse part has weight 269354323 (67.43/col)
Tue May 8 22:35:46 2018 saving the first 48 matrix rows for later
Tue May 8 22:35:47 2018 matrix includes 64 packed rows
Tue May 8 22:35:47 2018 matrix is 3994335 x 3994560 (1166.8 MB) with weight 302134637 (75.64/col)
Tue May 8 22:35:47 2018 sparse part has weight 265931977 (66.57/col)
Tue May 8 22:35:47 2018 using block size 8192 and superblock size 786432 for processor cache size 8192 kB
Tue May 8 22:35:58 2018 commencing Lanczos iteration (8 threads)
Tue May 8 22:35:58 2018 memory use: 935.5 MB
Tue May 8 22:36:09 2018 linear algebra at 0.0%, ETA 7h18m
[/code]The factors were logged at day1 06:41:25:
[code]
Wed May 9 06:41:25 2018 p78 factor: 102639592829741105772054196573991675900716567808038066803341933521790711307779
Wed May 9 06:41:25 2018 p78 factor: 106603488380168454820927220360012878679207958575989291522270608237193062808643
[/code]Total wall time:
[code]
22:21:21
[/code]if my clock math is correct. I think cado-nfs came in at:
[code]
27:06:32
[/code]

VBCurtis 2018-05-09 15:47

[QUOTE=EdH;487280]Total wall time:
[code]
22:21:21
[/code]if my clock math is correct. I think cado-nfs came in at:
[code]
27:06:32
[/code][/QUOTE]

Your CADO-data notes wall-clock time for the matrix at ~59000 seconds, on the order of 19 hr. That means poly select and sieving ran in just 8 hours!??

GGNFS/msieve took 14 hrs for poly select/sieving/filtering. So, outside of LA, it appears CADO is over 50% faster than GGNFS at this size!
One reason to note "outside of LA" is that it's possible in principle to use CADO for poly and sieve with msieve for LA, as you noted a couple posts up. A more important reason is that for a normal person with just one machine doing a job, LA time won't dominate the wall-clock measurement the way it does with your farm. If it takes me 80hr rather than 140 to sieve a number, I don't mind that LA takes 19 hr rather than 8!!

EdH 2018-05-09 16:33

[QUOTE=VBCurtis;487284]Your CADO-data notes wall-clock time for the matrix at ~59000 seconds, on the order of 19 hr. That means poly select and sieving ran in just 8 hours!??[/QUOTE]I've been watching that, specifically on the fact that msieve/ggnfs is maxed with this C155 for the sieve time available for some of my machines. CADO-NFS, OTOH, has a bit more time available for sieving.

[QUOTE=VBCurtis;487284]GGNFS/msieve took 14 hrs for poly select/sieving/filtering. So, outside of LA, it appears CADO is over 50% faster than GGNFS at this size!
One reason to note "outside of LA" is that it's possible in principle to use CADO for poly and sieve with msieve for LA, as you noted a couple posts up.[/QUOTE] I plan to experiment in this area. I need to find a way to automate the changeover. I'll have to work with some smaller composites before I can try one of these larger ones for another comparison.
[QUOTE=VBCurtis;487284]A more important reason is that for a normal person with just one machine doing a job, LA time won't dominate the wall-clock measurement the way it does with your farm. If it takes me 80hr rather than 140 to sieve a number, I don't mind that LA takes 19 hr rather than 8!![/QUOTE]Quite true. My farm is bottlenecked at LA. Less machines would swing the run into a different light. Something else to note, is that I'm seeing a lot of idle time on my clients while the final poly selection is made. This would not occur on a sole machine.

You've modified my understanding a bit, in that due to the ratio of multi-machine to single machine processes, there is more difference based on the makeup of the overall system of machines than I realized.:smile:

VBCurtis 2018-05-09 17:02

[QUOTE=EdH;487286]I've been watching that, specifically on the fact that msieve/ggnfs is maxed with this C155 for the sieve time available for some of my machines. CADO-NFS, OTOH, has a bit more time available for sieving.
[/QUOTE]
Note that CADO's server setup is designed for clients to appear and disappear at will; you can shut down the client-farm overnight while the machine with the CADO server sieves a bit, and in the morning reconnect the farm/CADO clients without any hiccups.
If C155 took ~8 hrs of the 14 available, you can do ~C160 worth of sieving each day (since poly select only happens the first day), so a C170 would take about 5 daytime-days of sieve-farming (plus a lengthy matrix, of course).
Edit: For that matter, you can shut down the CADO server, too- you'd just need to restart it using the snapshot invocation rather than the usual "start this job" command.

henryzz 2018-05-09 19:46

[QUOTE=VBCurtis;487288]Note that CADO's server setup is designed for clients to appear and disappear at will; you can shut down the client-farm overnight while the machine with the CADO server sieves a bit, and in the morning reconnect the farm/CADO clients without any hiccups.
If C155 took ~8 hrs of the 14 available, you can do ~C160 worth of sieving each day (since poly select only happens the first day), so a C170 would take about 5 daytime-days of sieve-farming (plus a lengthy matrix, of course).
Edit: For that matter, you can shut down the CADO server, too- you'd just need to restart it using the snapshot invocation rather than the usual "start this job" command.[/QUOTE]

It would be possible to go further than that. There is no reason why someone on the forum couldn't host a server for all of us to connect to. Once it becomes possible to do a very large factorization in a similar or better time than ggnfs we should probably start doing that as a forum.

EdH 2018-05-09 20:53

[QUOTE=VBCurtis;487288]Note that CADO's server setup is designed for clients to appear and disappear at will; you can shut down the client-farm overnight while the machine with the CADO server sieves a bit, and in the morning reconnect the farm/CADO clients without any hiccups.
If C155 took ~8 hrs of the 14 available, you can do ~C160 worth of sieving each day (since poly select only happens the first day), so a C170 would take about 5 daytime-days of sieve-farming (plus a lengthy matrix, of course).
Edit: For that matter, you can shut down the CADO server, too- you'd just need to restart it using the snapshot invocation rather than the usual "start this job" command.[/QUOTE]
I knew I could remove and restart clients and in my case, I can interrupt them for ggnfs, too, since I only suspend the clients. In the case of ggnfs, the clients will try to complete their range even after the server is running LA. I do end up stopping manually the clients that continue on. I was looking at this in a pure running sense for these experiments. I would consider a break of anything other than minor as a loss of validity. Maybe that's not correct since times are computed, at least for CADO-NFS.

I have seen the snapshot info scroll by and expected to be able to use it, but have not looked to see if it is in the temp folder. The temp folder seems to disappear once the factorization is complete. Is it in a log where I can find it or do I need to capture it before it scrolls out of range in the terminal? (I can look for it myself during my next runs)
[QUOTE=henryzz;487291]It would be possible to go further than that. There is no reason why someone on the forum couldn't host a server for all of us to connect to. Once it becomes possible to do a very large factorization in a similar or better time than ggnfs we should probably start doing that as a forum.[/QUOTE]
Team Aliquot projects could take on a different aspect. That could be done now, but for the LA portion. If the LA is able to be done by msieve with a savings in time, it would already be feasible.

VBCurtis 2018-05-09 21:00

[QUOTE=EdH;487295]
I have seen the snapshot info scroll by and expected to be able to use it, but have not looked to see if it is in the temp folder. The temp folder seems to disappear once the factorization is complete. Is it in a log where I can find it or do I need to capture it before it scrolls out of range in the terminal? (I can look for it myself during my next runs)

Team Aliquot projects could take on a different aspect. That could be done now, but for the LA portion. If the LA is able to be done by msieve with a savings in time, it would already be feasible.[/QUOTE]
The snapshot file is indeed in the temp folder, which does not disappear if you close CADO server while it's running. The file is named something obvious, like jobname.snapshot.0. When you know the name, invocation from the CADO folder points to that file rather than the local params file. You may also edit the params in the snapshot if you wish to change something during a job (say, changing tasks.qrange or adding more poly select by changing admax). Close CADO-server, edit the snapshot file, start server with "./cado-nfs.py /tmp/foldername/snapshotfilename"

When I was running a bunch of CADO tests on a multi-machine setup, I'd run the server with zero threads for sieving; when one job went to LA (taking up all CPUs), I'd fire up another CADO instance using zero sieve threads for the clients to connect to. My clients were roughly fast enough to finish sieving one problem in about the time the server finished LA on the previous one.

RichD 2018-05-10 01:28

It seems between [B]henryzz[/B] and [B]VBCurtis[/B] comments there could be a dedicated server for dishing out work and performing post-processing for Aliquot Sequences. Would this extend the reach of yafu@home into the C140s & C150s or are we talking bigger numbers? Who would do the ECM work prior to submitting the number?

VBCurtis 2018-05-10 05:01

I have a 32GB server with a public-facing internet connection that runs CADO jobs already; RichD connected to it for a past job as proof-of-concept for a shared CADO effort.

If there is interest in doing group-testing for CADO in 160-180 digit range, I'm game for selecting GNFS tasks from whatever project and firing up the CADO-server. Ed seems to have sub-160 covered in just a day with his own farm, so group work doesn't need to extend below 160.
I'm running a C149 on a single machine presently to get timing info on a non-farm environment; sieving is ETA'ed at just over 5 days on half of a 12-core Sandy Bridge (HP Z600).

Ideally, we find a pair of similar-sized numbers so I can adjust params after run 1 to try to improve performance in run 2; if we get good results, I can send the params to the CADO group for inclusion in their git release.

Edit: I am more interested in testing to improve params, but I'm game to do so on a bunch of C150s for aliquot work with my setup. I'll have time for the manual job-entry part on smaller jobs once the term ends early June.

VBCurtis 2018-05-10 19:29

[QUOTE=VBCurtis;487323]
I'm running a C149 on a single machine presently to get timing info on a non-farm environment; sieving is ETA'ed at just over 5 days on half of a 12-core Sandy Bridge (HP Z600).[/QUOTE]
This seemed high, so I did a little investigating and learned I didn't set qmin (the starting Q for sieving). CADO chose something near the midpoint of alim and rlim as default, and who knew that sieving 24M-42M would be less efficient than 4M-20M?
I restarted the job.

RichD 2018-05-10 21:44

[QUOTE=VBCurtis;487375]... and who knew that sieving 24M-42M would be less efficient than 4M-20M?.[/QUOTE]

I assume that was a joke. :smile:

Dubslow 2018-05-10 22:09

[QUOTE=RichD;487378]I assume that was a joke. :smile:[/QUOTE]

Well I think it used to be not a joke until he figured out recently that CADO siever is way more capable than GGNFS! :D

EdH 2018-05-11 01:36

I could use some help working with replay.

From README.msieve:
[code]
- use CADO-NFS for the filtering. In what follows, let 'prefix' be
the prefix used for all the CADO filenames
- use the CADO 'replay' binary with --for_msieve to produce
a file <prefix>.cyc
[/code]replay usage:
[code]
$ ../build/math79/filter/replay
Usage: ../build/math79/filter/replay <parameters>
The available parameters are the following:
-purged input purged file
-his input history file
-out basename for output matrices
-skip number of heaviest columns that go to the dense matrix (default 32)
-index file containing description of rows (relations-sets) of the matrix
-ideals file containing correspondence between ideals and matrix columns
-force-posix-threads (switch)
-path_antebuffer path to antebuffer program
-for_msieve output matrix in msieve format
-Nmax stop at Nmax number of rows (default 0)
-verbose_flags fine grained control on which messages get printed
[/code]replay attempt:
[code]
$ ../build/math79/filter/replay -for_msieve -purged c100.purged.gz -out c100.cyc -his c100.history.gz
# (2acb184f4) ../build/math79/filter/replay -for_msieve -purged c100.purged.gz -out c100.cyc -his c100.history.gz
# List of modified files in working directory and their SHA1 sum:
# (tarball extracted)
# Compiled with gcc 5.4.0 20160609
# Compilation flags -std=c99 -g -W -Wall -O2 -msse3 -mssse3 -msse4.1 -mavx -mpclmul
# Output matrices will be written in text format
antebuffer set to /home/math79/Math/cado-nfs/build/math79/utils/antebuffer
Sparse matrix has 676479 rows and 3141033 cols
The biggest index appearing in a relation is 3141033
Reading row additions
# Read 1024 row additions in 0.0s -- 96668.2 line/s
# Read 2048 row additions in 0.0s -- 163645.9 line/s
# Read 4096 row additions in 0.0s -- 275344.9 line/s
# Read 8192 row additions in 0.0s -- 453749.6 line/s
# Read 16384 row additions in 0.0s -- 650469.3 line/s
# Read 32768 row additions in 0.0s -- 869410.1 line/s
# Read 65536 row additions in 0.1s -- 1031672.9 line/s
# Read 131072 row additions in 0.1s -- 1149342.5 line/s
# Read 262144 row additions in 0.2s -- 1236750.1 line/s
# Read 524288 row additions in 0.4s -- 1166020.3 line/s
# Read 1048576 row additions in 0.8s -- 1361737.7 line/s
# Done: Read 1804303 row additions in 1.4s -- 1262598.0 line/s
Error, skip should be 0 with --for_msieve
[/code]Do I need to provide some other parameters, or something else?

EdH 2018-05-11 03:47

Darn the "edit window"...:sad:

[strike]Never-mind. I think I have it working, at least this far...[/strike]

I couldn't find a purge.log file, but I tried to continue without it.
[code]
$ ../../msieve/msieve -v -nf c100.fb -s c100 -nc2 "cado_filter=1"


Msieve v. 1.54 (SVN 1015)
Fri May 11 00:03:19 2018
random seeds: 5d49b7ee 1fc2f017
factoring 12957015248209241740975112870606500218152612197581145459935694931757631591512221494932593267684526589 (101 digits)
searching for 15-digit factors
commencing number field sieve (101-digit input)
R0: -2155705088808880551219399
R1: 32505869823781
A0: 16513438386348717729880931554
A1: -12209262827745380195609
A2: -10321887470935094
A3: -335931020
A4: 600
skew 1.00, size 5.291e-14, alpha -3.954, combined = 4.281e-11 rroots = 2

commencing linear algebra
assuming CADO-NFS filtering
read 171923 cycles
cycles contain 0 unique purge entries
error: cannot locate relation 16
[/code]

VBCurtis 2018-05-11 05:46

[QUOTE=RichD;487378]I assume that was a joke. :smile:[/QUOTE]

Yessir. :)
I restarted the job about 36 hr after it began, and the ETA is over 24 hr sooner. A slight parameter oversight, that! ~60 hr savings for a now 4 day job.

henryzz 2018-05-11 11:37

@EdH I think that the CADO format changed and msieve hasn't been updated. You should be able to pass the raw relations to msieve filtering though.

EdH 2018-05-11 18:46

[QUOTE=henryzz;487406]@EdH I think that the CADO format changed and msieve hasn't been updated. You should be able to pass the raw relations to msieve filtering though.[/QUOTE]
Is there an easier way to retrieve the relations than to manually extract them from 147 archived files?

henryzz 2018-05-12 07:24

[QUOTE=EdH;487422]Is there an easier way to retrieve the relations than to manually extract them from 147 archived files?[/QUOTE]

Due to how gzip works you should be able to concatenate all the files and then extract. You then might want to remove all the lines beginning with # although I think msieve would probably cope.

EdH 2018-05-12 12:40

[QUOTE=henryzz;487437]Due to how gzip works you should be able to concatenate all the files and then extract. You then might want to remove all the lines beginning with # although I think msieve would probably cope.[/QUOTE]
Worked great - thanks!

All I needed to do was:
[code]
cat *.gz > rels.dat.gz
[/code]convert c100.poly to c100.fb
and run msieve:
[code]
$ ../msieve -i c100.n -s rels.dat.gz -l c100msieve.log -nf c100.fb -t 8 -nc1
$ ../msieve -i c100.n -s rels.dat.gz -l c100msieve.log -nf c100.fb -t 8 -nc2
linear algebra completed 212499 of 213442 dimensions (99.6%, ETA 0h 0m)
$ ../msieve -i c100.n -s rels.dat.gz -l c100msieve.log -nf c100.fb -t 8 -nc3
[/code]And, I only separated the three steps to see how they performed. I'm sure:
[code]
$ ../msieve -i c100.n -s rels.dat.gz -l c100msieve.log -nf c100.fb -t 8 -nc
[/code]would have run as well.

Now to work on scripting it all...

EdH 2018-05-12 15:38

Well, I'm still not enlightened enough, yet!:sad:

How should I proceed if msieve responds with:
[code]
filtering wants 1000000 more relations
[/code]Is there a cado-nfs command to seive more, or should I hit the ggnfs sievers a bit?

Is there a setting in params.cxxx that I should change to give cado-nfs a better chance at providing enough relations from its first run?

VBCurtis 2018-05-12 21:28

Yes!
I don't recall the command offhand, but it's listed in one of the readme files included in the main CADO folder. There's a param setting to set minimum relations, and a different setting to tell CADO what % more relations to produce if filtering fails (default is 1%).

VBCurtis 2018-05-13 00:08

Took me a while to find, as it's not the readme in the main CADO folder. In /scripts/cadofactor, there's a readme, with this info:
"Note: if your factorization already started the linear algebra step, and you
want to do more sieving, you can restart it with a larger "rels_wanted" than
the current number of relations. For example if you have say 1000000 relations
(grep "is now" in the log file), just add in the cado-nfs.py line:

tasks.sieve.rels_wanted=1000001

If not enough relations are collected after the filtering step, the sieve
is executed again with an additional number of wanted relations. The
parameter tasks.filter.add_ratio controls the number of additional
required relations as a ratio of the number of unique relations already
collected:

tasks.filter.add_ratio=0.05

specifies that you want 5% more relations before next filtering step.
The default value is 0.01 (i.e. 1% more relations)."

kosta 2018-05-13 01:52

Ran a c140 on cado, just to get familiar. The number was an snfs, with a natural octic. Cado rejects octics, so i downconverted to a septic which looked decent enough, but has a yield which is way below the one from polyselect. Reading the papers from Murphy etal, did not produce any actionable ideas. So i ran with GNFS, it finished successfully. I note:
1) the software overall is very high quality
2) Its not all that hard to split the range and run two or more different servers on different sites
3) the crypto certificate verification fails under various scenarios A) tunneling through port redirect behind a firewall, B) client has the clock set to a wrong date

In this light, if someone sets up a public Cado server (would be nice) it is maybe ok to turn off ssl but then the downloading of executables should be turned off, i think there is such a mode.

EdH 2018-05-13 03:17

@Curtis,

Thanks for finding that for me. I had gone over the READMEs in the main directory and now I remember seeing the other one.

I now have scripts/binaries that will run straight from providing a command line bash call with a composite as the only option, though to the printing of the factors in the terminal at the end, (unless it needs more relations). It stops cado-nfs at the filtering step and continues with msieve. I will soon try it on the c155 from earlier. I'm actually wondering if it won't fail with too few relations and the extra sieving will eat up any LA time saving.

Something I have observed, though, is that the siever clients continue to run until their assignment is complete, even if the server has moved on to filtering, etc. This might actually help the issue if more relations are needed. First, I'll see what happens when I try a straight run with the c155.

Ed

VBCurtis 2018-05-13 04:42

When I sent my params files to PaulZ and the CADO group, Paul suggested that I may wish to set rels_needed to a minimum higher than CADO default. I believe the cause is that sieving smaller Q values produces more duplicates than the default Q-range CADO chooses, so the number of raw relations CADO aims for isn't quite enough because of the extra duplicates. We can use your data from the previous run to do that- set the rels needed to 5% less than the number you needed last time (to account for C153 or C154 jobs that would run on this file too).

I like that the siever-clients keep running during filtering; I feel like wasting a couple filtering attempts is worth the chance at saved sieve time, and wall clock time doesn't suffer much because the other clients produce a bunch of relations while the first filtering pass runs. With your 100+ clients, this isn't as efficient (since inevitably a bunch of sieve effort will be wasted when the filtering pass builds a matrix).

Edit: Then again, if needing more relations causes a hiccup in your automation, ask for 15% more relations than we think is needed, and hope that means msieve only needs to be called once!

EdH 2018-05-13 15:59

[QUOTE=VBCurtis;487488]When I sent my params files to PaulZ and the CADO group, Paul suggested that I may wish to set rels_needed to a minimum higher than CADO default. I believe the cause is that sieving smaller Q values produces more duplicates than the default Q-range CADO chooses, so the number of raw relations CADO aims for isn't quite enough because of the extra duplicates. We can use your data from the previous run to do that- set the rels needed to 5% less than the number you needed last time (to account for C153 or C154 jobs that would run on this file too).

I like that the siever-clients keep running during filtering; I feel like wasting a couple filtering attempts is worth the chance at saved sieve time, and wall clock time doesn't suffer much because the other clients produce a bunch of relations while the first filtering pass runs. With your 100+ clients, this isn't as efficient (since inevitably a bunch of sieve effort will be wasted when the filtering pass builds a matrix).

Edit: Then again, if needing more relations causes a hiccup in your automation, ask for 15% more relations than we think is needed, and hope that means msieve only needs to be called once![/QUOTE]Thanks Curtis,

I can't find a rels_needed in the parameter list, but I see a rels_wanted with a default of 0. My recent c100 test shows a value of 2679831 and I have a c150 log that shows 71293383, but I can't find any c155 log. Is this what I would adjust? I'll probably try a default run first because the set of relations I tried that failed, may have been incomplete. I can also have a rels number to work with for later adjustment.

I didn't get started with my machines early enough today for a test run. Maybe I can get things set up tonight and start a run tomorrow morning.

Ed

VBCurtis 2018-05-13 16:49

Sorry, I meant the tasks.sieve.rels_wanted from the readme a few posts ago. Just about any flag that can be set on the command line can also be placed in the params file.

Your CADO c155 run lists 138M relations at 30/31LP. Long ago I solved a C155 with msieve 30LP and needed 80M relations; more recently I solved a C149 with 31LP and 135M relations. Based on those two data points, the CADO production of 138M relations should be more than sufficient! If they're not, that suggests CADO maybe has a higher duplicate rate than GGNFS; we should then compare unique relations rather than raw relations to see what's going on.

EdH 2018-05-13 20:36

[QUOTE=VBCurtis;487506]Sorry, I meant the tasks.sieve.rels_wanted from the readme a few posts ago. Just about any flag that can be set on the command line can also be placed in the params file.

Your CADO c155 run lists 138M relations at 30/31LP. Long ago I solved a C155 with msieve 30LP and needed 80M relations; more recently I solved a C149 with 31LP and 135M relations. Based on those two data points, the CADO production of 138M relations should be more than sufficient! If they're not, that suggests CADO maybe has a higher duplicate rate than GGNFS; we should then compare unique relations rather than raw relations to see what's going on.[/QUOTE]OK, so that sounds good for me to try a default run, then. I was concerned because of a trial I did with the rels I had from a c150 run, but it's probable the "snapshot" of the temporary folder was made prior to the completion of sieving.

We might also find out from your calculations, that the cado-nfs relations could be cut some.

I'm looking forward to seeing how this next experiment runs.

Of course, from my "farming" viewpoint, I would really welcome distributed LA, as suggested somewhere I recently read, but can't seem to locate again. It was something different from the paper you pointed me to a few posts back.

I wish I knew enough to help in that development, but it would take more dedication than I can muster to learn what I would need...

EdH 2018-05-14 17:55

I had two false starts this morning in trying to run the c155 with my new scripts. Apparently, I had a conflict with providing a name when one existed within the params file. I think I have solved this issue and have completed a couple of smaller tests with success. I'll try a little larger one later and the c155 again tomorrow.

When letting CADO-NFS complete the factorization, it kills the clients, appropriately, when no longer needed. I see, now that I am telling CADO-NFS to stop at filtering, it no longer tells the clients to stop at all. This may be because I am manually controlling the clients, whereas if I had the server call them, they may be killed when it is aborted.

As to aborting at the filtering stage, it does not appear to be a gentle ending to the cado-nfs.py script, but rather a "harsh" ending with Traceback and Exception messages.

EdH 2018-05-14 18:48

How disappointing:
[code]
Mon May 14 13:31:40 2018 Msieve v. 1.54 (SVN 1015)
Mon May 14 13:31:40 2018 random seeds: bda7bc3a 7d279c6a
Mon May 14 13:31:40 2018 factoring 83430973660859696075606860121751204140765096280774007534994681679625269640631965880347308911045515734302894715692241103470949 (125 digits)
Mon May 14 13:31:40 2018 searching for 15-digit factors
Mon May 14 13:31:41 2018 commencing number field sieve (125-digit input)
Mon May 14 13:31:41 2018 R0: -753029938976683458937593
Mon May 14 13:31:41 2018 R1: 1785081673495471
Mon May 14 13:31:41 2018 A0: -7629089397626407377977251370
Mon May 14 13:31:41 2018 A1: 1398616311587389133353367
Mon May 14 13:31:41 2018 A2: 43796173748317237522
Mon May 14 13:31:41 2018 A3: -1503928724515567
Mon May 14 13:31:41 2018 A4: -138299341992
Mon May 14 13:31:41 2018 A5: -2756160
Mon May 14 13:31:41 2018 skew 1.00, size 4.464e-12, alpha -6.578, combined = 6.846e-12 rroots = 3
...
Mon May 14 13:35:58 2018 commencing linear algebra
Mon May 14 13:35:58 2018 read 850225 cycles
Mon May 14 13:35:59 2018 cycles contain 2733559 unique relations
Mon May 14 13:36:20 2018 read 2733559 relations
Mon May 14 13:36:22 2018 using 20 quadratic characters above 4294917295
Mon May 14 13:36:34 2018 building initial matrix
Mon May 14 13:36:52 2018 memory use: 358.7 MB
Mon May 14 13:36:52 2018 read 850225 cycles
Mon May 14 13:36:53 2018 matrix is 850047 x 850225 (258.0 MB) with weight 81305451 (95.63/col)
Mon May 14 13:36:53 2018 sparse part has weight 57440675 (67.56/col)
Mon May 14 13:36:58 2018 filtering completed in 2 passes
Mon May 14 13:36:58 2018 matrix is 849325 x 849502 (258.0 MB) with weight 81275010 (95.67/col)
Mon May 14 13:36:58 2018 sparse part has weight 57430903 (67.61/col)
Mon May 14 13:37:01 2018 matrix starts at (0, 0)
Mon May 14 13:37:01 2018 matrix is 849325 x 849502 (258.0 MB) with weight 81275010 (95.67/col)
Mon May 14 13:37:01 2018 sparse part has weight 57430903 (67.61/col)
Mon May 14 13:37:01 2018 saving the first 48 matrix rows for later
Mon May 14 13:37:01 2018 matrix includes 64 packed rows
Mon May 14 13:37:02 2018 matrix is 849277 x 849502 (247.0 MB) with weight 64545583 (75.98/col)
Mon May 14 13:37:02 2018 sparse part has weight 56241767 (66.21/col)
Mon May 14 13:37:02 2018 using block size 8192 and superblock size 786432 for processor cache size 8192 kB
Mon May 14 13:37:04 2018 commencing Lanczos iteration (8 threads)
Mon May 14 13:37:04 2018 memory use: 192.7 MB
Mon May 14 13:37:07 2018 linear algebra at 0.4%, ETA 0h13m
Mon May 14 13:53:15 2018 lanczos halted after 13434 iterations (dim = 849276)
Mon May 14 13:53:16 2018 recovered 31 nontrivial dependencies
Mon May 14 13:53:16 2018 BLanczosTime: 1038
Mon May 14 13:53:16 2018
Mon May 14 13:53:16 2018 commencing square root phase
Mon May 14 13:53:16 2018 [B]cannot handle negative leading algebraic polynomial coefficient[/B]
Mon May 14 13:53:16 2018 sqrtTime: 0
Mon May 14 13:53:16 2018 elapsed time 00:21:36
[/code]

henryzz 2018-05-14 19:05

I might be wrong but I think you could just flip the sign for all the coefficients. It will add a factor of -1 to each relation but that is fine.

jasonp 2018-05-14 21:47

That was reported to work on an older very large factorization.

VictordeHolland 2018-05-14 22:18

Huhhh??
 
HELP, CADO-NFS is fast! :confused2::max::sos:


[SIZE=3][B]RSA-100[/B][/SIZE]


[B]Factmsieve(v0.86) + Msieve + GGNFS sievers (with asm)[/B]

[code]
Mon May 14 00:11:33 2018 -> factmsieve.py (v0.86)
Mon May 14 00:11:33 2018 -> This is client 1 of 1
Mon May 14 00:11:33 2018 -> Running on 16 Cores with 2 hyper-threads per Core
Mon May 14 00:11:33 2018 -> Working with NAME = RSA100
Mon May 14 00:11:33 2018 -> Running polynomial selection ...
Mon May 14 00:11:33 2018 -> ./msieve -s ./RSA100.dat.T0 -l ./RSA100.log.T0 -i ./RSA100.ini.T0 -nf ./RSA100.fb.T0 -np 1,100 -v > ./RSA100.msp.T0
...
<deleted lines>
...
Mon May 14 00:11:58 2018 Best score so far: # norm 1.402930e-13 alpha -6.325236 e 1.281e-08 rroots 2
...
Mon May 14 00:11:58 2018 -> Selected lattice siever: gnfs-lasieve4I12e
Mon May 14 00:11:58 2018 -> entering sieving loop
....
Mon May 14 00:19:08 2018 Found 5074452 relations, 123.9% of the estimated minimum (4095000).
Mon May 14 00:19:09 2018 commencing relation filtering
...
Mon May 14 00:20:42 2018 -> Running matrix solving step
..
Mon May 14 00:22:25 2018 -> Running square root step
...
Mon May 14 00:22:53 2018 p50 factor: 37975227936943673922808872755445627854565536638199
Mon May 14 00:22:53 2018 p50 factor: 40094690950920881030683735292761468389214899724061[/code]If my time math is correct:

0:00:25 Poly
0:07:10 Sieving
0:01:34 Filtering
0:01:43 LA
0:00:28 SQR
-----------
0:11:20 total ([B]680 seconds[/B])


[B]CADO-NFS 3.0-dev[/B]

[code]./cado-nfs.py 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139
Info:root: Using default parameter file ./parameters/factor/params.c100
...
...
Info:Square Root: Factors: 37975227936943673922808872755445627854565536638199 40094690950920881030683735292761468389214899724061
Info:Polynomial Selection (size optimized): Aggregate statistics:
Info:Polynomial Selection (size optimized): potential collisions: 5781.44
Info:Polynomial Selection (size optimized): raw lognorm (nr/min/av/max/std): 5778/32.780/37.836/38.680/0.700
Info:Polynomial Selection (size optimized): optimized lognorm (nr/min/av/max/std): 5778/32.780/36.541/38.680/0.989
Info:Polynomial Selection (size optimized): Total time: 179.29
Info:Polynomial Selection (root optimized): Aggregate statistics:
Info:Polynomial Selection (root optimized): Total time: 113.19
Info:Polynomial Selection (root optimized): Rootsieve time: 112.7
Info:Generate Factor Base: Total cpu/real time for makefb: 1.42/0.164074
Info:Generate Free Relations: Total cpu/real time for freerel: 41.53/1.53222
Warning:Lattice Sieving: some stats could not be displayed for sieving (see log file for debug info)
Info:Lattice Sieving: Aggregate statistics:
Info:Lattice Sieving: Total number of relations: 2554287
Info:Lattice Sieving: Average J: 1026.82 for 85306 special-q
Info:Lattice Sieving: Total CPU time: 11204.3s
Info:Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 8.95/7.15092
Info:Filtering - Duplicate Removal, splitting pass: Aggregate statistics:
Info:Filtering - Duplicate Removal, splitting pass: CPU time for dup1: 6.9s
Info:Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 41.33/16.053
Warning:Filtering - Duplicate Removal, removal pass: some stats could not be displayed for duplicates2 (see log file for debug info)
Info:Filtering - Singleton removal: Total cpu/real time for purge: 36.22/17.4717
Info:Filtering - Merging: Total cpu/real time for merge: 77.19/56.4209
Info:Filtering - Merging: Total cpu/real time for replay: 7.2/6.00657
Info:Linear Algebra: Total cpu/real time for bwc: 1019.53/109.33
Info:Linear Algebra: Aggregate statistics:
Info:Linear Algebra: Krylov: WCT time 57.87, iteration CPU time 0.01, COMM 0.0, cpu-wait 0.0, comm-wait 0.0 (6000 iterations)
Info:Linear Algebra: Lingen CPU time 70.78, WCT time 6.49
Info:Linear Algebra: Mksol: WCT time 33.26, iteration CPU time 0.01, COMM 0.0, cpu-wait 0.0, comm-wait 0.0 (3000 iterations)
Info:Quadratic Characters: Total cpu/real time for characters: 8.98/1.74848
Info:Square Root: Total cpu/real time for sqrt: 119.93/18.0659
Info:HTTP server: Shutting down HTTP server
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 21026.1/715.742
[/code]CADO-NFS took [B]716[/B] seconds, only 36 seconds more than the GGNFS+msieve pack. (so only ~5% slower). Isn't GGNFS supposed to run circles around CADO-NFS in the lower ( < C140 ) regions??? I actually didn't believe the result at first, so I ran it again and it the timings were almost identical (actually even a few seconds WCT faster)
[code]
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 21181.5/709.047

[/code]So what happens if we move on to slightly bigger composites?
[SIZE=3][B]RSA-110[/B][/SIZE]

[B]Factmsieve(v0.86) + Msieve + GGNFS sievers (with asm routines)[/B]
[code]
Mon May 14 13:26:50 2018 -> factmsieve.py (v0.86)
Mon May 14 13:26:50 2018 -> This is client 1 of 1
Mon May 14 13:26:50 2018 -> Running on 16 Cores with 2 hyper-threads per Core
Mon May 14 13:26:50 2018 -> Working with NAME = RSA110
Mon May 14 13:26:50 2018 -> Running polynomial selection ...
Mon May 14 13:26:50 2018 -> ./msieve -s ./RSA110.dat.T0 -l ./RSA110.log.T0 -i ./RSA110.ini.T0 -nf ./RSA110.fb.T0 -np 1,1000 -v > ./RSA110.msp.T0
..
Mon May 14 13:28:44 2018 Best score so far: # norm 2.170012e-10 alpha -6.451622 e 1.047e-09 rroots 5
Mon May 14 13:28:44 2018 -> Selected lattice siever: gnfs-lasieve4I13e
Mon May 14 13:28:44 2018 -> entering sieving loop
...
Mon May 14 13:57:57 2018 Found 8210614 relations, 111.7% of the estimated minimum (7350000).

Mon May 14 13:57:58 2018 commencing relation filtering
...
Mon May 14 14:00:47 2018 -> Running matrix solving step
...
Mon May 14 14:02:47 2018 commencing square root phase
...
Mon May 14 14:04:16 2018 p55 factor: 5846418214406154678836553182979162384198610505601062333
Mon May 14 14:04:16 2018 p55 factor: 6122421090493547576937037317561418841225758554253106999

[/code]0:02:54 Poly
0:29:13 Sieving
0:02:50 Filtering
0:02:00 LA
0:01:29 SQR
----------
0:38:26 total ([B]2306[/B] seconds, 2306/680= 3.39xRSA100), keep those [U]2300[/U] seconds in mind!

For this run I changed the size of the np1 workunits in the factmsieve.py from 100 to 1000 (for a more constant CPU load) and the range from 0 - 4000 to:
[code]# msieve polynomial search leading coefficients limits
# search from POLY_MIN_LC + 1 to POLY_MAX_LC inclusive
POLY_MIN_LC = 0
POLY_MAX_LC = 64000
[/code]


Now comes the unbelievable part:

[B]CADO-NFS 3.0-dev[/B]
[code]
./cado-nfs.py 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667 workdir=/tmp/RSA110
Info:root: Using default parameter file ./parameters/factor/params.c110
Info:root: No database exists yet
Info:root: Set tasks.threads=32 based on detected logical cpus
...
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_0-5000 to client localhost
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_5000-10000 to client localhost+2
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_10000-15000 to client localhost+3
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_15000-20000 to client localhost+4
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_20000-25000 to client localhost+6
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_25000-30000 to client localhost+5
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_30000-35000 to client localhost+7
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_35000-40000 to client localhost+8
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_40000-45000 to client localhost+10
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_45000-50000 to client localhost+9
...
Info:Polynomial Selection (root optimized): Finished, best polynomial from file /tmp/RSA110/c110.upload/c110.polyselect2.pfbrex9n.opt_72 has Murphy_E = 2.59e-09
...
Info:Square Root: Factors: 6122421090493547576937037317561418841225758554253106999 5846418214406154678836553182979162384198610505601062333
Info:Polynomial Selection (size optimized): Aggregate statistics:
Info:Polynomial Selection (size optimized): potential collisions: 11711.3
Info:Polynomial Selection (size optimized): raw lognorm (nr/min/av/max/std): 11672/31.850/38.956/44.950/1.139
Info:Polynomial Selection (size optimized): optimized lognorm (nr/min/av/max/std): 11672/31.310/34.551/39.370/0.976
Info:Polynomial Selection (size optimized): Total time: 1176.67
Info:Polynomial Selection (root optimized): Aggregate statistics:
Info:Polynomial Selection (root optimized): Total time: 489.95
Info:Polynomial Selection (root optimized): Rootsieve time: 488.36
Info:Generate Factor Base: Total cpu/real time for makefb: 4.37/0.373342
Info:Generate Free Relations: Total cpu/real time for freerel: 109.26/3.60933
Warning:Lattice Sieving: some stats could not be displayed for sieving (see log file for debug info)
Info:Lattice Sieving: Aggregate statistics:
Info:Lattice Sieving: Total number of relations: 5412839
Info:Lattice Sieving: Average J: 1893.28 for 79582 special-q
Info:Lattice Sieving: Total CPU time: 28220.8s
Info:Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 18.96/16.6092
Info:Filtering - Duplicate Removal, splitting pass: Aggregate statistics:
Info:Filtering - Duplicate Removal, splitting pass: CPU time for dup1: 16.0s
Info:Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 113.86/54.6661
Warning:Filtering - Duplicate Removal, removal pass: some stats could not be displayed for duplicates2 (see log file for debug info)
Info:Filtering - Singleton removal: Total cpu/real time for purge: 97.19/51.8443
Info:Filtering - Merging: Total cpu/real time for merge: 106.71/89.2541
Info:Filtering - Merging: Total cpu/real time for replay: 9.6/7.87395
Info:Linear Algebra: Total cpu/real time for bwc: 1904.82/190.56
Info:Linear Algebra: Aggregate statistics:
Info:Linear Algebra: Krylov: WCT time 105.61, iteration CPU time 0.01, COMM 0.0, cpu-wait 0.0, comm-wait 0.0 (8000 iterations)
Info:Linear Algebra: Lingen CPU time 110.81, WCT time 10.02
Info:Linear Algebra: Mksol: WCT time 59.48, iteration CPU time 0.01, COMM 0.0, cpu-wait 0.0, comm-wait 0.0 (4000 iterations)
Info:Quadratic Characters: Total cpu/real time for characters: 13.74/2.61752
Info:Square Root: Total cpu/real time for sqrt: 260.73/37.302
Info:HTTP server: Shutting down HTTP server
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 42899.5/[B]1549.64[/B]
6122421090493547576937037317561418841225758554253106999 5846418214406154678836553182979162384198610505601062333[/code][B]1550[/B] seconds WCT!! Remember those 2300 seconds it took GGNFS?
1550 seconds works out to 25:50 for us mortals. That is [U]12 [/U]minutes faster than GGNFS. If left running, it would be halfway the second factorization!



CADO-NFS is cheating somewhere :chappy:, or I must have made a mistake. Or maybe the GGNFS default parameters are not very good??!!

CADO searched a smaller LC range (1 - 50 000) in Poly selection and found a poly with a much better Murpy-E (2.59e-09) compared to Msieve (e 1.047e-09), assuming they use the leading coeficients and compute Murpy-E the same way???????

I also ran this twice, with very similar CPUtime and WCT stats

[code]
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 42725.2/1555.01[/code]


[SIZE=3][B]RSA-120[/B][/SIZE]

[B]Factmsieve(v0.86) + Msieve + GGNFS sievers (with asm routines)[/B]
[code]
Mon May 14 15:57:16 2018 -> factmsieve.py (v0.86)
Mon May 14 15:57:16 2018 -> This is client 1 of 1
Mon May 14 15:57:16 2018 -> Running on 16 Cores with 2 hyper-threads per Core
Mon May 14 15:57:16 2018 -> Working with NAME = RSA120
Mon May 14 15:57:16 2018 -> Running polynomial selection ...
Mon May 14 15:57:16 2018 -> ./msieve -s ./RSA120.dat.T0 -l ./RSA120.log.T0 -i ./RSA120.ini.T0 -nf ./RSA120.fb.T0 -np 1,1000 -v > ./RSA120.msp.T0
...
Mon May 14 16:12:45 2018 -> ./msieve -s ./RSA120.dat.T31 -l ./RSA120.log.T31 -i ./RSA120.ini.T31 -nf ./RSA120.fb.T31 -np 127001,128000 -v >> ./RSA120.msp.T31
...
Mon May 14 16:12:46 2018 Best score so far: # norm 2.428994e-11 alpha -6.396319 e 3.305e-10 rroots 5
...
Mon May 14 16:12:46 2018 -> Selected lattice siever: gnfs-lasieve4I13e
Mon May 14 16:12:46 2018 -> entering sieving loop
...
Mon May 14 17:09:15 2018 Found 9260958 relations, 104.6% of the estimated minimum (8850000)
Mon May 14 17:09:16 2018 commencing relation filtering
...
Mon May 14 17:12:13 2018 filtering wants 1000000 more relations
...
Mon May 14 17:16:20 2018 Found 10027164 relations, 113.3% of the estimated minimum (8850000)
Mon May 14 17:16:21 2018 commencing relation filtering
...
Mon May 14 17:20:00 2018 -> Running matrix solving step
...
Mon May 14 17:26:53 2018 -> Running square root step
...
Mon May 14 17:28:40 2018 p60 factor: 327414555693498015751146303749141488063642403240171463406883
Mon May 14 17:28:40 2018 p60 factor: 693342667110830181197325401899700641361965863127336680673013

[/code]0:15:30 Poly
0:56:29 Sieving
0:02:58 Filtering attempt1
0:04:08 extra Sieving (total Sieving 1:00:37)
0:03:39 Filtering attempt2 (total Filtering 0:06:37)
0:06:53 LA
0:01:47 SQR

-----------

1:31:24 Total ([B]5484[/B] seconds), This is a [U]strong[/U] performance from GGNFS. With excellent scaling, only 2.38x RSA110 (nowhere near doubling every 5 digits!). Poly search was maybe a bit too long (1 - 128 000) and if it didn't attempt the first time filtering it could save maybe another 5 minutes?



[B]CADO-NFS 3.0-dev[/B]
[code]
./cado-nfs.py 227010481295437363334259960947493668895875336466084780038173258247009162675779735389791151574049166747880487470296548479
Info:root: Using default parameter file ./parameters/factor/params.c120
...
Info:root: Set tasks.threads=32 based on detected logical cpus
...
Info:Polynomial Selection (size optimized): Adding workunit c120_polyselect1_96000-100000 to database
...
Info:Polynomial Selection (root optimized): Finished, best polynomial from file /tmp/cado.y6d80vda/c120.upload/c120.polyselect2.s7415ny4.opt_90 has Murphy_E = 2.47e-09
...
Info:Square Root: Factors: 327414555693498015751146303749141488063642403240171463406883 693342667110830181197325401899700641361965863127336680673013
Info:Polynomial Selection (size optimized): Aggregate statistics:
Info:Polynomial Selection (size optimized): potential collisions: 19893.3
Info:Polynomial Selection (size optimized): raw lognorm (nr/min/av/max/std): 20018/34.470/42.677/47.450/1.072
Info:Polynomial Selection (size optimized): optimized lognorm (nr/min/av/max/std): 20018/33.410/37.836/43.140/0.979
Info:Polynomial Selection (size optimized): Total time: 4541.77
Info:Polynomial Selection (root optimized): Aggregate statistics:
Info:Polynomial Selection (root optimized): Total time: 1416.04
Info:Polynomial Selection (root optimized): Rootsieve time: 1414.04
Info:Generate Factor Base: Total cpu/real time for makefb: 9.54/0.656109
Info:Generate Free Relations: Total cpu/real time for freerel: 219.4/7.26091
Warning:Lattice Sieving: some stats could not be displayed for sieving (see log file for debug info)
Info:Lattice Sieving: Aggregate statistics:
Info:Lattice Sieving: Total number of relations: 13250893
Info:Lattice Sieving: Average J: 1901.72 for 233502 special-q
Info:Lattice Sieving: Total CPU time: 106196s
Info:Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 48.16/42.6905
Info:Filtering - Duplicate Removal, splitting pass: Aggregate statistics:
Info:Filtering - Duplicate Removal, splitting pass: CPU time for dup1: 41.8s
Info:Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 377.57/203.891
Warning:Filtering - Duplicate Removal, removal pass: some stats could not be displayed for duplicates2 (see log file for debug info)
Info:Filtering - Singleton removal: Total cpu/real time for purge: 325.72/185.027
Info:Filtering - Merging: Total cpu/real time for merge: 273.95/228.449
Info:Filtering - Merging: Total cpu/real time for replay: 25.6/20.9339
Info:Linear Algebra: Total cpu/real time for bwc: 10267.9/981.21
Info:Linear Algebra: Aggregate statistics:
Info:Linear Algebra: Krylov: WCT time 592.94, iteration CPU time 0.02, COMM 0.0, cpu-wait 0.01, comm-wait 0.0 (18500 iterations)
Info:Linear Algebra: Lingen CPU time 270.32, WCT time 24.72
Info:Linear Algebra: Mksol: WCT time 340.55, iteration CPU time 0.02, COMM 0.0, cpu-wait 0.01, comm-wait 0.0 (9500 iterations)
Info:Quadratic Characters: Total cpu/real time for characters: 37.88/6.75894
Info:Square Root: Total cpu/real time for sqrt: 772.36/110.95
Info:HTTP server: Shutting down HTTP server
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 142725/[B]5569.33[/B]
Info:root: Cleaning up computation data in /tmp/cado.y6d80vda
327414555693498015751146303749141488063642403240171463406883 693342667110830181197325401899700641361965863127336680673013

[/code][B]5569[/B] seconds WCT (1:32:49). GGNFS was faster, but only 1-2 minutes!! Also, CADO [U]continued[/U] sieving while attempting filtering, while the GGNFS/factmsieve.py script waits for the outcome of the filtering attempt.
And look at the E scores: e 3.305e-10 vs. Murphy_E = [B]2.47e-09[/B]
Did CADO just find a really, really good poly with (1 - 100 000)??? Or did GGNFS/Msieve somehow fail (or did I somewhere??)


Please tell me what did I do wrong? There must be some mistake somewhere or the believe that GGNFS/Msieve/factmsieve.py package is faster for small composites needs revision?

Please check, double check and tripple check my findings!


We need MOAAAARR DATA!!!!

EdH 2018-05-15 03:21

[QUOTE=henryzz;487590]I might be wrong but I think you could just flip the sign for all the coefficients. It will add a factor of -1 to each relation but that is fine.[/QUOTE]
Thanks - worked great! Is there some way to tell if I will have this trouble prior to translating the poly file to the fb file. If I can tell at that time, I can translate as needed. Should c0/A0 be positive to start with, perhaps?

VBCurtis 2018-05-15 04:50

[QUOTE=EdH;487623]Thanks - worked great! Is there some way to tell if I will have this trouble prior to translating the poly file to the fb file. If I can tell at that time, I can translate as needed. Should c0/A0 be positive to start with, perhaps?[/QUOTE]

If you mean c5/a5, yes. It's the leading coeff that msieve doesn't like.

VBCurtis 2018-05-15 04:58

[QUOTE=VictordeHolland;487608]\[B]5569[/B] seconds WCT (1:32:49). GGNFS was faster, but only 1-2 minutes!! Also, CADO [U]continued[/U] sieving while attempting filtering, while the GGNFS/factmsieve.py script waits for the outcome of the filtering attempt.
And look at the E scores: e 3.305e-10 vs. Murphy_E = [B]2.47e-09[/B]
Did CADO just find a really, really good poly with (1 - 100 000)??? Or did GGNFS/Msieve somehow fail (or did I somewhere??)
program

Please tell me what did I do wrong? There must be some mistake somewhere or the believe that GGNFS/Msieve/factmsieve.py package is faster for small composites needs revision?[/QUOTE]
CADO calculates E-score differently; the numbers don't compare directly for poly scores. CADO calculates the score based on the sieving region you declare in the params file; if you change lim0 and lim1 the reported poly score will change also. This is more accurate for comparing polys (using the params you intend to sieve on rather than a standard-candle approach), but it means scores aren't comparable to msieve scores.

As for your timings, I believe CADO handles many-threads better than factmsieve/msieve. If you repeat your RSA100 experiment with only 4 threads for each package, I think msieve wins. That's what has been reported here time and time again, though some of those reports preceded my improved params files.

CPU time is, to me, a better measure than wall-clock time; as you noted factmsieve filters single-threaded and the sievers don't run during that time. I often run small factorizations on the "free" hyperthreads on a 6-core machine, so any idle time in factmsieve is being used by other processes running on the machine.

Dubslow 2018-05-15 12:40

[QUOTE=VBCurtis;487626]CADO calculates E-score differently; the numbers don't compare directly for poly scores. CADO calculates the score based on the sieving region you declare in the params file; if you change lim0 and lim1 the reported poly score will change also. This is more accurate for comparing polys (using the params you intend to sieve on rather than a standard-candle approach), but it means scores aren't comparable to msieve scores.
[/QUOTE]

It's also problematic when the sieve parameters aren't known until after poly select is complete, e.g. adjusting lpb's depending on how good a poly is found, testing degree transitions, gnfs vs snfs testing, etc... my overall experience with the CADO package is that, while the networking and individual subcomponents are great, the glue python code is extremely monolithic and inflexible. The entire process start to finish must be done one way only, and any variations on that process (such as are quite common on this forum for distributed projects, such as team sieves or multiperson poly searches etc) will be ~impossible. A couple years ago when I was playing with the poly select code I wound up writing my own python wrappers around the C executables to be able to do things like polsel stage 1+sizeopt separately from rootopt. (And they are indeed different executables! But looking at CADO's python you'd never know that.)

(And, btw in reference to the rest of your post, is CADO's filtering not single threaded? I had assumed it was, is my assumption incorrect?)

EdH 2018-05-15 12:52

[QUOTE=VBCurtis;487625]If you mean c5/a5, yes. It's the leading coeff that msieve doesn't like.[/QUOTE]
I wrote before thinking - not uncommon** for me.:sad:

Thanks!

**Much of the time I catch it in my proofreading, but shorter posts proofread more poorly...

jasonp 2018-05-15 16:24

[QUOTE=VBCurtis;487625]If you mean c5/a5, yes. It's the leading coeff that msieve doesn't like.[/QUOTE]
Msieve can handle leading rational coefficients that are negative without issue, I just wasn't sure how the arithmetic in the square root changed when the leading algebraic coefficient was negative. For all I know it would work fine without changes, or would work fine on average, but I didn't want to take that risk when there is already so much that can go wrong in the square root.

henryzz 2018-05-15 21:10

[QUOTE=jasonp;487664]Msieve can handle leading rational coefficients that are negative without issue, I just wasn't sure how the arithmetic in the square root changed when the leading algebraic coefficient was negative. For all I know it would work fine without changes, or would work fine on average, but I didn't want to take that risk when there is already so much that can go wrong in the square root.[/QUOTE]

Assuming that inverting the sign always works it might be worth msieve always doing that with a negative leading algebraic coefficient.

VBCurtis 2018-05-16 01:49

You'd think I would not need to discover this twice:
If you run CADO within "screen", and the session is not live when the factorization completes, CADO makes no record of the results whatsoever. The temp folder with all the data is erased, including the log, and since the process finished "screen -r" has nothing to resume.
So, I have only very rough wall-clock data for the C149 I ran.
On the bright side, I decided to try Ed's relation-catting-for-msieve, so I have all the relations and msieve is matrix-ing now. At least I get factors!

Dubslow 2018-05-16 02:48

I didn't even know you could use screen just for one process lol. I just run screen, and then once in the screen whatever command I need, and it always persists until I close it.

VBCurtis 2018-05-16 03:52

I have a helpful ISP that drops any connection after 30 min of inactivity. At least, I think it's the ISP.... anyway, my server is at work and I SSH in to do my factoring jobs. Most jobs have screen activity often enough to not matter, but msieve filtering and CADO sqrt both cause disconnections.
"screen python ./factmsieve.py [etc]" means the job finishes and all is well; doing the same with CADO is a problem.
I reported this as a bug, requesting a file be written (or even the params file be edited) with factors found, and was told I could fix it myself by telling CADO to not use /tmp for its work.
I'm just not a fan of any program that only outputs results to screen.... perhaps I'll start making my own log file by redirecting screen output to a file.

Also, on this C149 candidate, CADO took ~31 hr for the matrix, while msieve ETA is 18 hr total (after 10% has run, so ETA should be accurate). Sieving on 12 threads of a 12-core Sandy Bridge system doing ~11 other things (7xLLR, 3x ECM, srsieve) took just under 96 hr.
I tried msieve postprocessing on the relation set at 92% of CADO's targeted relations, without success. CADO ended up sieving to about 105% of its own targeted relations, and that set produced a 4.4M matrix in msieve without setting Target Density. I believe CADO said its matrix was 3.8M, suggesting my CADO-params file has target density set higher than msieve-equivalent-70 (I think that's a plus, given how slow CADO solves matrices).

RichD 2018-05-16 04:23

So what happens when you get a power outage after a factorization completes in the middle of the night during a thunderstorm? Oh, don't get me started about weather related power issues in the Midwest. :smile:

Gimarel 2018-05-16 04:56

c145 comparison cado vs. yafu/msieve
 
The comparison was run on an i7-3770K @ 4GHz.

[B]YAFU/msieve[/B] with patches for better parametrisation
Poly selection: 02:21:19
Sieving: 41:05:55
Matrix: 01:45:36
[B]Total: 45:45:00[/B]

[B]CADO[/B] with default parameters
Poly selection: 01:58:30
Sieving: 95:00:34
Matrix: 14:13:40
[B]Total: 112:04:07[/B]

Total time includes setup, filtering, and square root.
Note that the CADO poly had a msieve score that was about 5% better than the score of the YAFU poly.

VBCurtis 2018-05-16 07:17

[QUOTE=RichD;487725]So what happens when you get a power outage after a factorization completes in the middle of the night during a thunderstorm? Oh, don't get me started about weather related power issues in the Midwest. :smile:[/QUOTE]

That's how I lost the first job! This time, I learned screen -r doesn't work after the process completed. I really like that the data is auto-deleted; I've run out of disk more times than I can count because I forgot to delete relations from a previous factorization (or two). So, I don't want to manually direct the factorization data away from /tmp.

pinhodecarlos 2018-05-16 07:29

This can be off topic or not but distributed.net posted last night (GMT) on facebook the following: "Do you have a math project which is looking for a huge processing power? We can help."


I can't find anything on this on their website but maybe they can support on a distributed CADO NFS.

Dubslow 2018-05-16 07:56

[QUOTE=VBCurtis;487729]This time, I learned screen -r doesn't work after the process completed. [/QUOTE]

Not if you run the process from within screen! (As opposed to being an argument to screen, like you quoted before)

VictordeHolland 2018-05-16 13:21

[QUOTE=Gimarel;487726]The comparison was run on an i7-3770K @ 4GHz.

[B]YAFU/msieve[/B] with patches for better parametrisation
Poly selection: 02:21:19
Sieving: 41:05:55
Matrix: 01:45:36
[B]Total: 45:45:00[/B]

[B]CADO[/B] with default parameters
Poly selection: 01:58:30
Sieving: 95:00:34
Matrix: 14:13:40
[B]Total: 112:04:07[/B]

Total time includes setup, filtering, and square root.
Note that the CADO poly had a msieve score that was about 5% better than the score of the YAFU poly.[/QUOTE]
Could you share the better parameters?

EdH 2018-05-16 16:09

I may have to figure out some more details, but the rsa155 hybrid run is finished. It was not without trouble, though. Again I had the negative leading coefficient trouble and had to run the square root phase again with a modified .fb file. I will have to add a check for this to my poly to .fb binary.

I will probably need to dig out more details, but for now:

cado-nfs was started at day 1 08:13:10
sieving completed at day 1 18:11:49
msieve filtering started at day 1 18:17:05

Filtering had a huge error -11 problem, with a few error -1's thrown in:
[code]
Tue May 15 18:17:05 2018 Msieve v. 1.54 (SVN 1015)
Tue May 15 18:17:05 2018 random seeds: b0c7282b 1f9fcba3
Tue May 15 18:17:05 2018 factoring 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897 (155 digits)
Tue May 15 18:17:06 2018 searching for 15-digit factors
Tue May 15 18:17:06 2018 commencing number field sieve (155-digit input)
Tue May 15 18:17:06 2018 R0: -612027504584914645235174827421
Tue May 15 18:17:06 2018 R1: 25879721744003857318699
Tue May 15 18:17:06 2018 A0: 182745817499024369420760271832448384
Tue May 15 18:17:06 2018 A1: -427211473195034674829019757212
Tue May 15 18:17:06 2018 A2: -3743757388243368106451009
Tue May 15 18:17:06 2018 A3: 10289593997537051662
Tue May 15 18:17:06 2018 A4: 15468757262920
Tue May 15 18:17:06 2018 A5: -8954400
Tue May 15 18:17:06 2018 skew 1.00, size 5.406e-15, alpha -7.580, combined = 4.712e-14 rroots = 3
Tue May 15 18:17:06 2018
Tue May 15 18:17:06 2018 commencing relation filtering
Tue May 15 18:17:06 2018 estimated available RAM is 15926.6 MB
Tue May 15 18:17:06 2018 commencing duplicate removal, pass 1
Tue May 15 18:17:06 2018 error -1 reading relation 0 (line 21)
Tue May 15 18:17:06 2018 error -11 reading relation 1
Tue May 15 18:17:06 2018 error -11 reading relation 2
...
Tue May 15 18:17:10 2018 error -11 reading relation 224097
Tue May 15 18:17:10 2018 error -11 reading relation 224098
Tue May 15 18:17:10 2018 error -11 reading relation 224099 (line 224120)
Tue May 15 18:29:02 2018 error -1 reading relation 97073091
Tue May 15 18:29:10 2018 error -1 reading relation 98240030
Tue May 15 18:29:23 2018 error -1 reading relation 100033046
...
[/code]LA started at day 1 18:58:32 and finished at day 2 06:18:23:
[code]
Tue May 15 18:58:32 2018 commencing linear algebra
Tue May 15 18:58:33 2018 read 4811300 cycles
Tue May 15 18:58:39 2018 cycles contain 16143189 unique relations
Tue May 15 19:01:43 2018 read 16143189 relations
Tue May 15 19:01:59 2018 using 20 quadratic characters above 4294917295
Tue May 15 19:03:09 2018 building initial matrix
Tue May 15 19:05:04 2018 memory use: 2101.0 MB
Tue May 15 19:05:06 2018 read 4811300 cycles
Tue May 15 19:05:07 2018 matrix is 4811123 x 4811300 (1457.0 MB) with weight 456267854 (94.83/col)
Tue May 15 19:05:07 2018 sparse part has weight 329008565 (68.38/col)
Tue May 15 19:05:48 2018 filtering completed in 2 passes
Tue May 15 19:05:49 2018 matrix is 4807229 x 4807405 (1456.7 MB) with weight 456143785 (94.88/col)
Tue May 15 19:05:49 2018 sparse part has weight 328985188 (68.43/col)
Tue May 15 19:06:11 2018 matrix starts at (0, 0)
Tue May 15 19:06:12 2018 matrix is 4807229 x 4807405 (1456.7 MB) with weight 456143785 (94.88/col)
Tue May 15 19:06:12 2018 sparse part has weight 328985188 (68.43/col)
Tue May 15 19:06:12 2018 saving the first 48 matrix rows for later
Tue May 15 19:06:12 2018 matrix includes 64 packed rows
Tue May 15 19:06:13 2018 matrix is 4807181 x 4807405 (1411.2 MB) with weight 363261148 (75.56/col)
Tue May 15 19:06:13 2018 sparse part has weight 321855481 (66.95/col)
Tue May 15 19:06:13 2018 using block size 8192 and superblock size 786432 for processor cache size 8192 kB
Tue May 15 19:06:27 2018 commencing Lanczos iteration (8 threads)
Tue May 15 19:06:27 2018 memory use: 1140.4 MB
Tue May 15 19:06:40 2018 linear algebra at 0.0%, ETA 11h29m
Tue May 15 19:06:44 2018 checkpointing every 430000 dimensions
Wed May 16 06:18:18 2018 lanczos halted after 76017 iterations (dim = 4807178)
Wed May 16 06:18:23 2018 recovered 25 nontrivial dependencies
Wed May 16 06:18:23 2018 BLanczosTime: 40791
Wed May 16 06:18:23 2018
Wed May 16 06:18:23 2018 commencing square root phase
Wed May 16 06:18:23 2018 cannot handle negative leading algebraic polynomial coefficient
Wed May 16 06:18:23 2018 sqrtTime: 0
Wed May 16 06:18:23 2018 elapsed time 12:01:18
[/code]But, as shown, the square root phase failed. The square root phase was restarted at day 2 09:37:21 with the modified .fb file and it completed at day 2 10:19:10:
[code]
Wed May 16 09:37:21 2018 Msieve v. 1.54 (SVN 1015)
Wed May 16 09:37:21 2018 random seeds: d021314b 0b59fad8
Wed May 16 09:37:21 2018 factoring 10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897 (155 digits)
Wed May 16 09:37:21 2018 searching for 15-digit factors
Wed May 16 09:37:22 2018 commencing number field sieve (155-digit input)
Wed May 16 09:37:22 2018 R0: -612027504584914645235174827421
Wed May 16 09:37:22 2018 R1: 25879721744003857318699
Wed May 16 09:37:22 2018 A0: -182745817499024369420760271832448384
Wed May 16 09:37:22 2018 A1: 427211473195034674829019757212
Wed May 16 09:37:22 2018 A2: 3743757388243368106451009
Wed May 16 09:37:22 2018 A3: -10289593997537051662
Wed May 16 09:37:22 2018 A4: -15468757262920
Wed May 16 09:37:22 2018 A5: 8954400
Wed May 16 09:37:22 2018 skew 1.00, size 5.406e-15, alpha -7.580, combined = 4.712e-14 rroots = 3
Wed May 16 09:37:22 2018
Wed May 16 09:37:22 2018 commencing square root phase
Wed May 16 09:37:22 2018 reading relations for dependency 1
Wed May 16 09:37:22 2018 read 2403030 cycles
Wed May 16 09:37:25 2018 cycles contain 8068356 unique relations
Wed May 16 09:40:02 2018 read 8068356 relations
Wed May 16 09:40:35 2018 multiplying 8068356 relations
Wed May 16 09:48:37 2018 multiply complete, coefficients have about 463.52 million bits
Wed May 16 09:48:39 2018 initial square root is modulo 207512621
Wed May 16 09:58:16 2018 GCD is N, no factor found
Wed May 16 09:58:16 2018 reading relations for dependency 2
Wed May 16 09:58:16 2018 read 2403705 cycles
Wed May 16 09:58:19 2018 cycles contain 8076686 unique relations
Wed May 16 10:00:56 2018 read 8076686 relations
Wed May 16 10:01:29 2018 multiplying 8076686 relations
Wed May 16 10:09:30 2018 multiply complete, coefficients have about 464.00 million bits
Wed May 16 10:09:32 2018 initial square root is modulo 211638667
Wed May 16 10:19:09 2018 sqrtTime: 2507
Wed May 16 10:19:10 2018 p78 factor: 102639592829741105772054196573991675900716567808038066803341933521790711307779
Wed May 16 10:19:10 2018 p78 factor: 106603488380168454820927220360012878679207958575989291522270608237193062808643
Wed May 16 10:19:10 2018 elapsed time 00:41:49
[/code]Summary from above:
[code]
cado-nfs was started at day 1 08:13:10
sieving completed at day 1 18:11:49
msieve filtering started at day 1 18:17:05
LA started at day 1 18:58:32
LA finished at day 2 06:18:23

Sqrt restarted at day 2 09:37:21
Sqrt completed at day 2 10:19:10

Total wall clock time 22:47:02

[/code]Compared to the earlier times, this one took slightly longer than the original ggnfs/msieve run with all the same machines.
[QUOTE=EdH;487280]Total wall time:
[code]
22:21:21
[/code]if my clock math is correct. I think cado-nfs came in at:
[code]
27:06:32
[/code][/QUOTE]

Gimarel 2018-05-17 08:25

1 Attachment(s)
[QUOTE=VictordeHolland;487745]Could you share the better parameters?[/QUOTE]

The patches are not very clean.
The msieve patches are against ^/trunk revision 983.
The yafu patches are against ^/branches/wip revision 366.
The yafu patches won't work without the msieve patches and will probably break SNFS.

The values for c145 can probably be optimised. The values for c150 are a complete guess. I don't have values above c150.
The crossover 13e to 14e is about 0.5 to 1.0 digits to low, but I didn't care enough to get more precise values.

The crossover SIQS to GNFS is at about 91 digits with these patches. But yafu tune will generate wrong results.

VictordeHolland 2018-05-21 13:29

[QUOTE=Gimarel;487838]The patches are not very clean.
The msieve patches are against ^/trunk revision 983.
The yafu patches are against ^/branches/wip revision 366.
The yafu patches won't work without the msieve patches and will probably break SNFS.

The values for c145 can probably be optimised. The values for c150 are a complete guess. I don't have values above c150.
The crossover 13e to 14e is about 0.5 to 1.0 digits to low, but I didn't care enough to get more precise values.

The crossover SIQS to GNFS is at about 91 digits with these patches. But yafu tune will generate wrong results.[/QUOTE]
[code]+/* digits, r/alim, lpbr/a, mfbr/a, r/alambda, siever, min-rels, q-range, sievestart */
+ {105, 700000, 29, 58, 2.50, 12, 9100000, 5000, 500000},
+ {110, 700000, 29, 58, 2.50, 12, 11000000, 5000, 500000},
+ {115, 900000, 29, 58, 2.50, 12, 15200000, 5000, 800000},
+ {120, 1400000, 29, 58, 2.50, 12, 20400000, 5000, 800000},
+ {120, 1400000, 29, 58, 2.50, 13, 17500000, 5000, 1200000},
+ {125, 2200000, 29, 58, 2.50, 13, 23400000, 5000, 1800000},[/code] Thanks for sharing! I only did a quick test with RSA110 by editing the def-par.txt and using the factmsieve.py script. Using the 12e siever instead of the 13e for 110 digits does indeed seem faster, but I don't understand why would you want to use lpb of 29 for these small composites?? That seems a bit excessive and creates bigger data files and requires more relations?? :confused2:

[B]RSA110 - 2500k @4.0GHz[/B]
13e siever - lbp: 27 (defaults from def-par.txt)
1:21:00 (17,739 CPUsec according to ggnfs.log)
7,760,669 raw relations
349123 x 349349 matrix (0:02:24)

13e siever - lbp: [U]29[/U]
1:16:35 (16,704 CPUsec)
8,810,357 raw relations
276548 x 276796 (0:01:34)

[U]12e[/U] siever - lbp: 27
1:10:31 (15,759 CPUsec)
7,582,183 raw relations
409071 x 409300 matrix (0:03:33)

[U]12e[/U] siever - lbp: 26
1:08:18 (15,434 CPUsec)
5,674,595 raw relations
455269 x 455495 matrix (0:03:56)

PS: If this is too offtopic for the CADO thread or worthy of a new thread that is fine with me.

VictordeHolland 2018-05-21 15:10

[QUOTE=VictordeHolland;487608]
[SIZE=3][B]RSA-110[/B][/SIZE]
[B]Factmsieve(v0.86) + Msieve + GGNFS sievers (with asm routines)[/B]
[code]
Mon May 14 13:26:50 2018 -> factmsieve.py (v0.86)
Mon May 14 13:26:50 2018 -> This is client 1 of 1
Mon May 14 13:26:50 2018 -> Running on 16 Cores with 2 hyper-threads per Core
Mon May 14 13:26:50 2018 -> Working with NAME = RSA110
Mon May 14 13:26:50 2018 -> Running polynomial selection ...
Mon May 14 13:26:50 2018 -> ./msieve -s ./RSA110.dat.T0 -l ./RSA110.log.T0 -i ./RSA110.ini.T0 -nf ./RSA110.fb.T0 -np 1,1000 -v > ./RSA110.msp.T0
..
Mon May 14 13:28:44 2018 Best score so far: # norm 2.170012e-10 alpha -6.451622 e 1.047e-09 rroots 5
Mon May 14 13:28:44 2018 -> Selected lattice siever: gnfs-lasieve4I13e
Mon May 14 13:28:44 2018 -> entering sieving loop
...
Mon May 14 13:57:57 2018 Found 8210614 relations, 111.7% of the estimated minimum (7350000).

Mon May 14 13:57:58 2018 commencing relation filtering
...
Mon May 14 14:00:47 2018 -> Running matrix solving step
...
Mon May 14 14:02:47 2018 commencing square root phase
...
Mon May 14 14:04:16 2018 p55 factor: 5846418214406154678836553182979162384198610505601062333
Mon May 14 14:04:16 2018 p55 factor: 6122421090493547576937037317561418841225758554253106999

[/code]0:02:54 Poly
0:29:13 Sieving
0:02:50 Filtering
0:02:00 LA
0:01:29 SQR
----------
0:38:26 total ([B]2306[/B] seconds)

[B]CADO-NFS 3.0-dev[/B]
[code]
./cado-nfs.py 35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667 workdir=/tmp/RSA110
Info:root: Using default parameter file ./parameters/factor/params.c110
Info:root: No database exists yet
Info:root: Set tasks.threads=32 based on detected logical cpus
...
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_0-5000 to client localhost
...
Info:HTTP server: 127.0.0.1 Sending workunit c110_polyselect1_45000-50000 to client localhost+9
...
Info:Polynomial Selection (root optimized): Finished, best polynomial from file /tmp/RSA110/c110.upload/c110.polyselect2.pfbrex9n.opt_72 has Murphy_E = 2.59e-09
...
Info:Square Root: Factors: 6122421090493547576937037317561418841225758554253106999 5846418214406154678836553182979162384198610505601062333
Info:Polynomial Selection (size optimized): Aggregate statistics:
Info:Polynomial Selection (size optimized): potential collisions: 11711.3
Info:Polynomial Selection (size optimized): raw lognorm (nr/min/av/max/std): 11672/31.850/38.956/44.950/1.139
Info:Polynomial Selection (size optimized): optimized lognorm (nr/min/av/max/std): 11672/31.310/34.551/39.370/0.976
Info:Polynomial Selection (size optimized): Total time: 1176.67
Info:Polynomial Selection (root optimized): Aggregate statistics:
Info:Polynomial Selection (root optimized): Total time: 489.95
Info:Polynomial Selection (root optimized): Rootsieve time: 488.36
Info:Generate Factor Base: Total cpu/real time for makefb: 4.37/0.373342
Info:Generate Free Relations: Total cpu/real time for freerel: 109.26/3.60933
Warning:Lattice Sieving: some stats could not be displayed for sieving (see log file for debug info)
Info:Lattice Sieving: Aggregate statistics:
Info:Lattice Sieving: Total number of relations: 5412839
Info:Lattice Sieving: Average J: 1893.28 for 79582 special-q
Info:Lattice Sieving: Total CPU time: 28220.8s
Info:Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 18.96/16.6092
Info:Filtering - Duplicate Removal, splitting pass: Aggregate statistics:
Info:Filtering - Duplicate Removal, splitting pass: CPU time for dup1: 16.0s
Info:Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 113.86/54.6661
Warning:Filtering - Duplicate Removal, removal pass: some stats could not be displayed for duplicates2 (see log file for debug info)
Info:Filtering - Singleton removal: Total cpu/real time for purge: 97.19/51.8443
Info:Filtering - Merging: Total cpu/real time for merge: 106.71/89.2541
Info:Filtering - Merging: Total cpu/real time for replay: 9.6/7.87395
Info:Linear Algebra: Total cpu/real time for bwc: 1904.82/190.56
Info:Linear Algebra: Aggregate statistics:
Info:Linear Algebra: Krylov: WCT time 105.61, iteration CPU time 0.01, COMM 0.0, cpu-wait 0.0, comm-wait 0.0 (8000 iterations)
Info:Linear Algebra: Lingen CPU time 110.81, WCT time 10.02
Info:Linear Algebra: Mksol: WCT time 59.48, iteration CPU time 0.01, COMM 0.0, cpu-wait 0.0, comm-wait 0.0 (4000 iterations)
Info:Quadratic Characters: Total cpu/real time for characters: 13.74/2.61752
Info:Square Root: Total cpu/real time for sqrt: 260.73/37.302
Info:HTTP server: Shutting down HTTP server
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 42899.5/[B]1549.64[/B]
6122421090493547576937037317561418841225758554253106999 5846418214406154678836553182979162384198610505601062333[/code][B]1550[/B] seconds WCT!! Remember those 2300 seconds it took GGNFS?
1550 seconds works out to 25:50 for us mortals.
[/QUOTE]
Rerunning RSA110 with GGNFS/Msieve using the 12e and lpb 26 improved the time only a little bit.


0:01:10 Poly Select
0:22:40 Sieving
0:03:40 Filtering
0:04:04 Linear Algebra
0:03:45 SQR
--------
0:35:19

Even though I shaved off almost 2 min at Poly Select and 6 minutes at Sieving. It had to filter twice (first time barely failed) and the LA took a bit longer. It got a bit unlucky at the SQR (only found the factors at the 3rd dependency).
Total CPUtime spend sieving (35079) is now much closer to CADO (28220).

Gimarel 2018-05-21 15:50

[QUOTE=VictordeHolland;488098]Using the 12e siever instead of the 13e for 110 digits does indeed seem faster, but I don't understand why would you want to use lpb of 29 for these small composites?? That seems a bit excessive and creates bigger data files and requires more relations?? :confused2:
[/QUOTE]

Because it's faster, at least for me.

The relation count for lpb 29 seems to low for me, it should be about 11000000.
Did you notice, that the comment is a bit misleading: The algebraic factor base is set at a different place to 999999999. This will be limited to the beginning of the sieved range by the siever.

Also note, that the parameters are only good, if the sieving starts at the value, that's computed by yafu.

Gimarel 2018-05-23 06:16

c145 comparison cado vs. yafu/msieve
 
I sieved the c145 with the cado siever and the parameters that were used by yafu (with my patches).
The [B]sieving time[/B] until a matrix could be built was about [B]48h[/B]. This is almost halve the time of the cado default parameters.

The commandline was like:
[CODE]las -v -T -T -stats-stderr -I 14 -lim0 6721882 -lpb0 30 -lpb1 30 -mfb0 60 -mfb1 60 -lambda0 2.25 -lambda1 2.25 -poly c145.poly -fb c145.fb -out c145.dat -lim1 4912000 -q0 4912000 -q1 4917000[/CODE]Note that -lim1 is set to the same value as -q0. The sieving started at 4912000 in 5k steps.

henryzz 2018-05-23 08:43

[QUOTE=Gimarel;488178]I sieved the c145 with the cado siever and the parameters that were used by yafu (with my patches).
The [B]sieving time[/B] until a matrix could be built was about [B]48h[/B]. This is almost halve the time of the cado default parameters.

The commandline was like:
[CODE]las -v -T -T -stats-stderr -I 14 -lim0 6721882 -lpb0 30 -lpb1 30 -mfb0 60 -mfb1 60 -lambda0 2.25 -lambda1 2.25 -poly c145.poly -fb c145.fb -out c145.dat -lim1 4912000 -q0 4912000 -q1 4917000[/CODE]Note that -lim1 is set to the same value as -q0. The sieving started at 4912000 in 5k steps.[/QUOTE]

It is worth noting that unlike the ggnfs siever cado can sieve below the fb bound.

Gimarel 2018-05-23 09:08

[QUOTE=henryzz;488186]It is worth noting that unlike the ggnfs siever cado can sieve below the fb bound.[/QUOTE]
I think you mean, that cado can sieve with fb entries above the currently sieved special-q.
IMO that's slower overall, at least for small composites like c145. That's the reason I limited the fb.

wombatman 2018-05-26 23:23

Error?
 
[CODE]Info:Linear Algebra: Starting
Warning:Command: Process with PID 23973 finished with return code 255
Error:Linear Algebra: Program run on server failed with exit code 255
Error:Linear Algebra: Command line was: /home/wombatman/cado-nfs-2.3.0/build/BenMeekins-PC/linalg/bwc/bwc.pl :complete 'thr=8' 'nullspace=left' 'matrix=/tmp/cado.ui87i89u/c165.sparse.bin' 'wdir=/tmp/cado.ui87i89u/c165.bwc' 'cpubinding=/home/wombatman/cado-nfs-2.3.0/parameters/misc/cpubinding.conf' 'cantor_threshold=2048' 2> /tmp/cado.ui87i89u/c165.bwc.stderr.3
b'Missing parameters: m and/or n at linalg/bwc/bwc.pl line 360.\n[/CODE]

Any ideas what this is? Sieving and merging completed without issue. This error occurs immediately upon the start of linear algebra.

wombatman 2018-05-27 02:16

Since I can't edit the previous post, the solution was to add the appropriate parameter line to the new c165 params file (and in this case, to the snapshot as well). That's my bad. The lines I added were the following, copied from pre-existing c165 params file:

[CODE]###########################################################################
# Linear algebra
###########################################################################

tasks.linalg.bwc.interval = 1000
tasks.linalg.bwc.interleaving = 0
tasks.linalg.m = 64
tasks.linalg.n = 64

###########################################################################
# Characters
###########################################################################

tasks.linalg.characters.nchar = 50[/CODE]

wombatman 2018-07-02 01:43

CADO-NFS on RPis
 
I've been playing with using RPis as a mini-cluster with CADO-NFS. I'm running into what I think is a memory issue. The short version is this: the RPis can do polynomial selection workunits up to at least C17x (I think C177 is the highest I've done). However, they cannot handle sieving workunits above C117 (C119 and above led to the error detailed below), giving the following error repeatedly:

[CODE]Error:Lattice Sieving: Program run on localhost failed with exit code -9
Error:Lattice Sieving: Stderr output follows (stored in file /tmp/cado.znzw_dvb/c120.upload/c120_sieving_196000-197000#2.2w0rleb9.stderr0):
b'madvise failed: Invalid argument\n'[/CODE]


I know I can take this to the CADO-NFS programmers, but I figured I would check here first in case there's a simple solution. This is on an RPi Model 3B+(1GB RAM).

VBCurtis 2018-07-02 05:13

If you're using 2.3.0, the C120 params file uses I = 14 for no good reason. C115 file uses I = 12. If you're using the git 3.0.0, then params.c120 uses I = 12 and I dunno why you're getting crashes.

I=12 should fit comfortably in 1GB.

wombatman 2018-07-02 05:45

It's the 2.3.0 version. Thanks!

VictordeHolland 2018-07-02 08:03

[QUOTE=wombatman;490983]I know I can take this to the CADO-NFS programmers, but I figured I would check here first in case there's a simple solution. This is on an RPi Model 3B+(1GB RAM).[/QUOTE]
Could you time RSA-100 to compare the RPi 3B+ with my (ancient) Odroid-U2 ARM board?

CADO-NFS 3.0-dev timings for RSA-100 on Odroid-U2:
[URL]http://mersenneforum.org/showpost.php?p=481269&postcount=129[/URL]


RSA-100 with Msieve-lasieve4-python script on Odroid-U2 in:
[URL]http://mersenneforum.org/showthread.php?t=23471[/URL]

wombatman 2018-07-02 19:21

Sure. Started it just now with default parameters, 4 threads.

wombatman 2018-07-03 02:35

[CODE]Info:Square Root: finished
Info:Square Root: Factors: 37975227936943673922808872755445627854565536638199 40094690950920881030683735292761468389214899724061
Info:Square Root: Total cpu/real time for sqrt: 441/124.699
Info:Polynomial Selection (size optimized): Aggregate statistics:
Info:Polynomial Selection (size optimized): potential collisions: 2890.72
Info:Polynomial Selection (size optimized): raw lognorm (nr/min/av/max/std): 2920/32.780/37.719/38.560/0.695
Info:Polynomial Selection (size optimized): optimized lognorm (nr/min/av/max/std): 2920/32.780/36.417/38.550/0.985
Info:Polynomial Selection (size optimized): Total time: 403.24
Info:Polynomial Selection (root optimized): Aggregate statistics:
Info:Polynomial Selection (root optimized): Total time: 510.88
Info:Polynomial Selection (root optimized): Rootsieve time: 507.48
Info:Generate Factor Base: Total cpu/real time for makefb: 8.42/2.29804
Info:Generate Free Relations: Total cpu/real time for freerel: 245.18/62.0037
Info:Lattice Sieving: Aggregate statistics:
Info:Lattice Sieving: Total number of relations: 2689258
Info:Lattice Sieving: Average J: 1023.74 for 88142 special-q, max bucket fill: 0.707584
Info:Lattice Sieving: Total CPU time: 40586.2s
Info:Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 24.95/68.3106
Info:Filtering - Duplicate Removal, splitting pass: Aggregate statistics:
Info:Filtering - Duplicate Removal, splitting pass: CPU time for dup1: 67.6s
Info:Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 108.2/94.0727
Info:Filtering - Singleton removal: Total cpu/real time for purge: 117.94/84.1812
Info:Filtering - Merging: Total cpu/real time for merge: 386.29/355.652
Info:Filtering - Merging: Total cpu/real time for replay: 35.57/37.4631
Info:Linear Algebra: Total cpu/real time for bwc: 18146.5/0.00117993
Info:Linear Algebra: Aggregate statistics:
Info:Linear Algebra: Krylov: WCT time 2941.91
Info:Linear Algebra: Lingen CPU time 303.06, WCT time 84.66
Info:Linear Algebra: Mksol: WCT time 1477.02
Info:Quadratic Characters: Total cpu/real time for characters: 19.53/9.2079
Info:Square Root: Total cpu/real time for sqrt: 441/124.699
Info:HTTP server: Shutting down HTTP server
Info:Complete Factorization: Total cpu/elapsed time for entire factorization: 61033.9/16947.3
Info:root: Cleaning up computation data in /tmp/cado.1xpfmivz
37975227936943673922808872755445627854565536638199 40094690950920881030683735292761468389214899724061[/CODE]

***Note that everything except for the linear algebra was done on 2 threads.

Polyselect: 23 minutes, 42 seconds
Sieving: 40586.2 seconds (~5.5 hours real time)
Filtering: 639 secs (~10 minutes)
Linear Algebra: 2941.91+84.66+1477.02 = 4503.59 seconds (~1.25 hours) ***4 threads here
Sqrt: 125 seconds
Total (CPU/Real): 61033.9/16947.3 seconds

VictordeHolland 2018-07-03 10:38

[QUOTE=wombatman;491045]
***Note that everything except for the linear algebra was done on 2 threads.

Polyselect: 23 minutes, 42 seconds
Sieving: 40586.2 seconds (~5.5 hours real time)
Filtering: 639 secs (~10 minutes)
Linear Algebra: 2941.91+84.66+1477.02 = 4503.59 seconds (~1.25 hours) ***4 threads here
Sqrt: 125 seconds
Total (CPU/Real): 61033.9/16947.3 seconds[/QUOTE]
Cool, thx!
I'm a bit surprised that it is not faster than the quad-A9 in the ODROID-U2?! Even after taking into account the clockspeed difference (1700 MHz for the U2 vs. 1400MHz of the RP3B+)
Were you using the CADO 3.0-dev latest git version?

wombatman 2018-07-03 14:11

No, this was with the CADO-2.3.0 release. I haven't compiled the latest version.

VictordeHolland 2018-07-03 17:31

Okay, I think you'll probably get faster/shorter times with the parameter files from 3.0 .

Speaking of the parameter file:
How do the
tasks.filter.target_density = 160
and
tasks.filter.purge.keep =160
Work? Do they correspond to Target density and excess in Msieve?

VBCurtis 2018-07-03 20:30

Yes, to target density; though it is measured differently. I haven't gotten too firm an estimate, but density 140 in CADO is around TD 80 in msieve (I think). The relationship should be constant-difference or nearly so, so 180 in CADO would be a rather high density.

madhurima 2018-07-09 19:11

Filtering large sparse matrix using CADO
 
have a sparse matrix with 5221950 rows and 4222046 columns in .txt format. I wish to filter this matrix to make it dense. What is the CADO code for doing it.

VBCurtis 2018-07-10 01:09

Both the CADO and msieve tools are designed to solve sparse matrices. What density is your matrix, and how dense do you want it to be? Why not just solve it as it is? If your matrix is of the typical density from an NFS job, you're looking at under a day to solve it as-is.

Secondly, filtering is a procedure applied to NFS relations, not to a matrix. Matrix-building happens after the filtering step.

madhurima 2018-07-10 07:51

[QUOTE=VBCurtis;491380]Both the CADO and msieve tools are designed to solve sparse matrices. What density is your matrix, and how dense do you want it to be? Why not just solve it as it is? If your matrix is of the typical density from an NFS job, you're looking at under a day to solve it as-is.

Secondly, filtering is a procedure applied to NFS relations, not to a matrix. Matrix-building happens after the filtering step.[/QUOTE]
I tried to solve the matrix as it is. It requires a huge amount of memory for doing so.

The computation started on July 8. It says krylov steps will be done by July 28. Today is july 10 and already 600 GB of memory has been used up.

We have limited computational resources. So providing this huge memory may be difficult.
Actually, I wanted to run Block Wiedemann to the matrix.
I have run the code below.
"software/cado-nfs/build/magma4/linalg/bwc/bwc.pl :complete thr=90 m=4 n=2 nullspace=right matrix=/user1/res/asu/madhurima_r/software/cado-nfs//sparse-folder22bit/fullmat.sparse.bin"
Can something be done so that I am able to run Block Wiedemann on the matrix, in such a way that filtering is done automatically and so much memory is not needed.

VictordeHolland 2018-07-10 20:07

[QUOTE=madhurima;491395]I tried to solve the matrix as it is. It requires a huge amount of memory for doing so.

The computation started on July 8. It says krylov steps will be done by July 28. Today is july 10 and already 600 GB of memory has been used up. [/QUOTE]
Solving a GNFS 5.2M matrix shouldn't take that long and not use that much memory.

For instance a GNFS160 with Msieve uses less than 3GB and takes less than a day to solve on a quadcore.

[code]
Wed Oct 28 16:15:20 2015 matrix is 5796592 x 5796817 (2608.9 MB) with weight 698630622 (120.52/col)
Wed Oct 28 16:15:20 2015 sparse part has weight 625952164 (107.98/col)
Wed Oct 28 16:15:20 2015 using block size 8192 and superblock size 786432 for processor cache size 8192 kB
Wed Oct 28 16:15:53 2015 commencing Lanczos iteration (4 threads)
Wed Oct 28 16:16:15 2015 linear algebra at 0.0%, ETA 22h17m[/code][quote]
Can something be done so that I am able to run Block Wiedemann on the matrix, in such a way that filtering is done automatically and so much memory is not needed.[/quote]CADO-NFS or Msieve should be able to do the filtering of the relations and produce a solvable matrix. I would rerun the filtering step, maybe an error occurred which resulted in a unsolvable matrix.

Nooks 2018-07-19 14:40

VBCurtis, we talked over in the HP49 thread about timing information from jobs of 160+ digits.

My factorization of the 181-digit N at [url]http://stdkmd.com/nrr/cont/3/37771.htm#N195_C181[/url] just completed; the factors were a p78 and p103.

[QUOTE]Just need wall-clock time for poly select, sieving, and LA; and the CPU specs for the machine used.
[/QUOTE]

You can see the final section of the CADO-NFS logfile at the above url; if I am reading correctly, WCT for the polyselect, sieving and LA steps were 9.15021e+06s, 4.30315e+07s, and 2.03259e+06s respectively. (If I have those wrong or you'd like to see the full logfile I'm happy to provide it.)

The execution environment was six machines as follows with 64GB RAM each, with just one machine running the non-distributed portion.

[CODE]$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
NUMA node(s): 1
Vendor ID: AuthenticAMD
CPU family: 23
Model: 1
Model name: AMD Ryzen 7 1700X Eight-Core Processor
Stepping: 1
CPU MHz: 2200.000
CPU max MHz: 3400.0000
CPU min MHz: 2200.0000
BogoMIPS: 6799.72
Virtualization: AMD-V
L1d cache: 32K
L1i cache: 64K
L2 cache: 512K
L3 cache: 8192K
NUMA node0 CPU(s): 0-15
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good nopl nonstop_tsc extd_apicid aperfmperf eagerfpu pni pclmulqdq monitor ssse3 fma cx16 sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw skinit wdt tce topoext perfctr_core perfctr_nb bpext perfctr_l2 mwaitx hw_pstate vmmcall fsgsbase bmi1 avx2 smep bmi2 rdseed adx smap clflushopt sha_ni xsaveopt xsavec xgetbv1 xsaves clzero irperf ibpb arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold avic overflow_recov succor smca
[/CODE]

I used the default c180 parameters from git head.

I will say that keeping this factorization running smoothly was a little tricky thanks to several of the machines locking up and needing reboots; this happened enough that eventually the factorization stopped completely due to too many failures.

VBCurtis 2018-07-19 15:39

[QUOTE=Nooks;492122]
You can see the final section of the CADO-NFS logfile at the above url; if I am reading correctly, WCT for the polyselect, sieving and LA steps were 9.15021e+06s, 4.30315e+07s, and 2.03259e+06s respectively.
[/CODE]

I used the default c180 parameters from git head.

I will say that keeping this factorization running smoothly was a little tricky thanks to several of the machines locking up and needing reboots; this happened enough that eventually the factorization stopped completely due to too many failures.[/QUOTE]
Your timing report suggests that CADO only tracked the sieve effort after your last reboot. I don't think a C180 can be sieved in 43 megaCPUseconds! CADO reports CPU time rather than wall clock time for poly select and sieving; for LA, both CPU and wall clock time are reported.
It doesn't make sense for 9M sec poly select, 43M secs sieve, 20M sec LA; so I think sieve time was only the last invocation after a restart.
Thanks for the data, all the same! If you do another 180-class CADO, let me know and I can try to improve the default parameters; I've saved 30-50% CPU time over default in previous 145-155 digit efforts (see above in this thread). My next personal job is a GNFS180 with CADO and my own parameters.

Nooks 2018-07-19 16:23

[QUOTE=VBCurtis;492127]Thanks for the data, all the same! If you do another 180-class CADO, let me know and I can try to improve the default parameters; I've saved 30-50% CPU time over default in previous 145-155 digit efforts (see above in this thread). My next personal job is a GNFS180 with CADO and my own parameters.[/QUOTE]

I have a c185 ([url]http://stdkmd.com/nrr/c.cgi?q=37771_258[/url]) 2/3 of the way through polyselect now; I guess we can check back in a few months.

I have to say that I have found it challenging to not have to stop the CADO server from time to time to recover from client failures; the machine running the server last restarted on June 15 --- I've had to issue eleven resets for 6 machines so far; I'm starting to suspect that they've been crashing under memory pressure, but I'm not sure.

I do have a complete CADO logfile and all the data files produced by the 37771_195 factorization if useful estimates of actual CPU time used could be collected.

R. Gerbicz 2018-07-19 16:38

[QUOTE=Nooks;492122]VBCurtis, we talked over in the HP49 thread about timing information from jobs of 160+ digits.

My factorization of the 181-digit N at [url]http://stdkmd.com/nrr/cont/3/37771.htm#N195_C181[/url] just completed; the factors were a p78 and p103.
[/QUOTE]

[QUOTE=VBCurtis;492127]Your timing report suggests that CADO only tracked the sieve effort after your last reboot. I don't think a C180 can be sieved in 43 megaCPUseconds! CADO reports CPU time rather than wall clock time for poly select and sieving; for LA, both CPU and wall clock time are reported.[/QUOTE]

We are speaking about a factorization of a factor of N=34*10^195-61. What is a pretty nice totally trivial snfs number. What an overshoot doing this with gnfs..... Personally I don't recommend everybody Maths and programming.

Nooks 2018-07-19 17:32

Apologies, I could have mentioned that this is a number better suited to SNFS.

I have two more in the pipeline for GFNS treatment before committing to learning how to import Kamada's SNFS polynomials.

VBCurtis 2018-07-19 17:53

You can learn SNFS in a few minutes; it's not exactly a commitment.
34*10^195-61 = 34x^5 - 61. What is x?
That's it.
Set m = the x-value you figure out, c5 = 34, c0 = -61. Done. The factorization would take a quad-core a day, maybe?

Edit: "m" is how ggnfs/msieve records that value. I think CADO needs the rational poly spelled out, so you'd use R1 = 1, R0 = m, or -m (trial and error? Not sure what exact names CADO uses for these, but there's a sample included with the package)

Nooks 2018-07-19 18:53

I recall the sticking point was converting GGNFS form to CADO poly form via convert_poly and my best judgement for the mapping between GGNFS parameters and CADO's; I did not keep the logfile to indicate where it failed.

Thanks for the quick demo on SNFS polynomial selection for numbers of this form---x is of course 10^39, and for 34*10^196-61, x would be 10^49 for a quartic polynomial, or c5 = 340 and x = 10^39 -- the smaller value of m being preferred over a lower-degree polynomial.

I'll abstain from this thread until I'm more sure I have something more useful to contribute.

VBCurtis 2018-07-26 03:21

A pleasant combination of a light summer teaching load and a shiny new-to-me 20-core Xeon box has me resuming my parameter optimation work for CADO. I'm pleased to say that while 10 threads solve a matrix from the 15e queue, I can still crack a C145 in under 24hr on this single machine.

I'm going through the aliquot sequence thread, factoring every fully-ECM'ed composite mentioned in an un-reservation in 2018. I expect to have new params files for c115 through c150 within a week or two; I'll post them to this thread in hopes some of you will test them against default CADO or against msieve/GGNFS (yafu or factmsieve or your own custom params).

If anyone has GNFS inputs in the 130s they'd like me to solve, I'll be happy to factor a few. It seems there are few released sequences with ECM'ed cofactors in the 130s, so I don't have much data on jobs that size.

RichD 2018-07-26 04:15

[QUOTE=VBCurtis;492504]If anyone has GNFS inputs in the 130s they'd like me to solve, I'll be happy to factor a few. It seems there are few released sequences with ECM'ed cofactors in the 130s, so I don't have much data on jobs that size.[/QUOTE]
A post from a different thread.
[QUOTE=hyramgraff;492435]Since you're asking about numbers that are ready for SNFS I thought I should mention that just last week I finished running 45 digit ECM on all of the C130-C139 numbers in [URL="https://gitlab.com/hyramgraff/odd-perfect-ecm/blob/e2ecd2a115d7ed06c39aaf11bc241dd0ca56639a/t2100.txt"]this [/URL]version of the t2100 file. I believe that they are now ready for SNFS.[/QUOTE]
Actually these are mostly GNFS jobs. The t2100 file can be found at [url]http://www.lirmm.fr/~ochem/opn/t2100.txt[/url] or linked from Pascal's OPN homepage at [url]http://www.lirmm.fr/~ochem/opn/[/url]

VBCurtis 2018-08-11 05:34

I clicked on those links, and didn't find the file format easily grokked in terms on which should be GNFS and which should be SNFS. Aliquot terms are much simpler for me to grab, ECM pretest, and run.

I'm on break from refining parameters, as I've fired up a GNFS 180 on CADO. I'm quite impressed with I=15 siever performance:
32/33LP, 64/95 MFB, 60M/100M factor base bounds. Q=10-18M so far has produced over 100M relations! That's a yield of.... twelve. ETA is around 3 weeks to harvest 450M relations (CADO default target). CADO does not provide timing data, but some hand timing of individual 1k ranges tested on client machines indicates around 0.1 sec/relation.
It's possible that CADO is *much* more efficient using 3LP than GGNFS sievers. That would explain their params files using 3LP some 30 digits lower than we traditionally have!
Once it enters the matrix phase, I'll zcat all the rels files to an msieve instance and compare matrix ETA forecasts. I expect msieve will be much quicker for the matrix, and that I'll manage a GNFS 180 sieve + LA on personal machines in under a calendar month!

If anyone is in the mood to test CADO out some more, please request params files; I have updated files for 105-145, still experimenting with looser LP bounds (occasionally a great improvement, but timings vary more from input to input). I think I've improved 115 and 120 files 10% from my previous submissions.


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

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