three large primes

[bsquared]

Originally Posted by jasonp

How do you handle the filtering for datasets that include TLP relations?

It does a full merge using the greedy combining process described in section 4 of Dodson and Lenstra's paper .

The resulting matrix for the C135 wasn't very large, but it was pretty dense. Some of that can be improved by rejecting cycles that are huge, which I didn't do. Even so, single-thread Lanczos only took an hour or so to run on the dense matrix.

[jasonp]

Ok, I was asking because if you want to tune that part of the process you can convert relations into the intermediate format that Msieve's NFS filtering uses and then run all the filtering as if it was an NFS job. I can almost guarantee the resulting matrix would wind up much better because you can leverage the algorithm research that goes into NFS filtering.

Of course that takes a backseat to tuning the sieving.

[xilman]

Originally Posted by bsquared

More concerning to me is the fact that the TLP doesn't seem any better than DLP at the moment. Its very possible that I'm doing something wrong still, some bug or oversight that is limiting the TLP speed, or maybe it is parameters.

I suspect the latter. Before the C135 computation I'd been running my TMPQS implementation for a year or so on perhaps 20 different numbers ranging from C85 to C110 (these may not be accurate figures because I don't have access to the contemporary hand-written records which are still in the UK but they are in the right ballpark), tweaking the parameters to minimize sieving time. Our implementations are so different that the optimal parameter sets should also be expected to be different.

Back in the day there were still many composites of interest which were still best done by QS, not least because GNFS implementations were not easily available and, even if you could get hold of one, it was bleeding edge code which need skill and patience to nurse its way through a factorization. Sic transit gloria mundi.

[bsquared]

Originally Posted by xilman

I'm sure Ben is aware of this but others may not be: in our paper we stated that GNFS was a better option than TMPQS for numbers of this size. Our experiment was purely to investigate the cycle explosion behaviour and to characterize the phase transition when it happened.

Yes, indeed.

An NFS run on the same number and same computer took about 8 hours for poly find and sieving. The matrix was larger, of course, but used Jason's multi-threaded and better optimized Lanczos. The matrix+sqrt took about another hour (on a different machine on which those tasks are better suited). In round numbers, QS ran about 75hrs / 9 hrs ~ 8 times slower than NFS. The NFS in question is yafu's automated msieve+ggnfs version.

[xilman]

Originally Posted by Till

Sorry, but taking Moore's law into account your result does not look too impressive.

Original computation time (2001): 231 days ~= 5544 hours.
New Computation time (2019): 75 hours


Assuming that computing speed doubles every 2 years we have
Original computation time/2^9 = 10.8 hours

APPLE .NE. ORANGE

The hardware architectures are radically different. Back in the day memory could almost keep up with the cpu. That hasn't been true for a long time now. Our computation ran for a large part on MIPS and Sparc processors. That which did use x86 ran on 486 or early (inevitably 32-bit) Pentium cpus.

You also appear to be comparing elapsed times. A fairer comparison would be to use cpu-core time.

[bsquared]

Originally Posted by jasonp

Ok, I was asking because if you want to tune that part of the process you can convert relations into the intermediate format that Msieve's NFS filtering uses and then run all the filtering as if it was an NFS job. I can almost guarantee the resulting matrix would wind up much better because you can leverage the algorithm research that goes into NFS filtering.

Of course that takes a backseat to tuning the sieving.

I wanted to roll my own at first because I wanted to understand more about how many-large-prime merging works. I'm happy I was able to understand it enough to get something up and running that works fairly well. This has been a nagging open question/task for me for probably close to a decade now that I can finally check off. Now, however, yes... using better techniques that you and others have extensively developed is on the list to do.

[jasonp]

I've been remiss in adding my congrats, getting end-to-end QS with three large primes is a major major undertaking.

[xilman]

Originally Posted by jasonp

I've been remiss in adding my congrats, getting end-to-end QS with three large primes is a major major undertaking.

I'll take that as a compliment to Arjen and myself

[chris2be8]

Originally Posted by Till

Sorry, but taking Moore's law into account your result does not look too impressive.

Original computation time (2001): 231 days ~= 5544 hours.
New Computation time (2019): 75 hours


Assuming that computing speed doubles every 2 years we have
Original computation time/2^9 = 10.8 hours

Hardware speed doubled every 2 years up to about 2005. Then CPUs hit the thermal limit so clock rates havn't increased much since then, although instructions per clock cycle and the number of cores have increased. So compare CPU core hours * clock rate for each calculation for a better comparison.

Chris

[Till]

Originally Posted by xilman

APPLE .NE. ORANGE

The hardware architectures are radically different. Back in the day memory could almost keep up with the cpu. That hasn't been true for a long time now. Our computation ran for a large part on MIPS and Sparc processors. That which did use x86 ran on 486 or early (inevitably 32-bit) Pentium cpus.

You also appear to be comparing elapsed times. A fairer comparison would be to use cpu-core time.

Originally Posted by chris2be8

Hardware speed doubled every 2 years up to about 2005. Then CPUs hit the thermal limit so clock rates havn't increased much since then, although instructions per clock cycle and the number of cores have increased. So compare CPU core hours * clock rate for each calculation for a better comparison.

Chris

You are both certainly right, but I only did a quickshot calculation. No serious critics intended, by the way.

Otherwise, I might be able to deduce the parameters of Ben's hardware from other threads, but https://infoscience.epfl.ch/record/1...es/NPDF-28.pdf does not seem to contain the necessary information.

Anyway, whoever wants more accurate numbers is free to compute them :-)

[bsquared]

Originally Posted by Till

Actually I am impressed too (despite my calculation above).


Do you know Thorsten Kleinjungs SIQS variant?
http://www.ams.org/journals/mcom/201...-2015-03058-0/


He seems to have made an algorithmic improvement to SIQS.

There are some numbers for up to 130 digit factor arguments (measured in core years).

I'm trying to weigh whether or not to try out the ideas in the paper.

The paper has timings for the main computational steps of the class group computations for imaginary quadratic fields with d-digit discriminants. They mention that the sieving step of this computation is the same as that used during SIQS integer factorization, but I don't know much more than that about class group computations. Anyway, the table reports a time of 2.23 core years spent in the sieving step for a C130 input. Their core is a 1.9GHz Opteron core.

I used a 7210 KNL processor that has 256 virtual cores (64 physical cores, each with 4 hyperthreads) that run at 1.5 GHz.

The C135 sieving took 74 wall clock hours * 256 cores = 18,944 core-hours = 2.16 core years. Although I'm not sure how to handle the hyperthreads... if you only count physical cores (performance certainly does not scale linearly past 64 cores on this processor) then it spent 0.54 core years. Call it double that to 1.08 core-years to account for the diminishing return of the hyperthreads.

Scaling the ratio of core-years by the ratio of clock frequencies and inversely by the ratio of effort I get:
2.23 / 1.08 * 1.9 / 1.5 * exp(sqrt(ln C135 ln ln C135)) / exp(sqrt(ln C130 ln ln C130))
which if I did that right means 4.88 times the effort for equivalent job sizes.

This still isn't right because the sievers are probably memory bound, not cpu bound, and the two implementations use way different instruction sets (and AVX512 could maybe also accelerate their ideas). But it's enough to tell me that it might not be worth the effort to try to implement it.

Even so, I do need to read more and try to understand it better.