Originally posted by jjjjL
Yea! SoBSieve is much faster now... even faster than (the albeit more portable) NBeGon:
Yeah, NbeGon stopped development (or I stopped development on it), 30 seconds before I handed my source code and description to Paul. I realised that the only thing that I could do further was optimise, and as Paul said from the outset this shouldn't be an optimisation competition. I'd spent the previous week working out _algorithmics_, proof of principle, not optimising. As a proof of principle I don't think it was too bad.

Paul's software has since then had two major algorithmic boosts, one of which I had already put in NbeGon, the other of which isn't, it was merely <taps head> up here. So in theory I _could_ put together one final NbeGon, which would be at the same "tech" as Pauls, but not as highly optimised, as mine would be all C.

To be honest, I've not looked at the problem, save exchanging mails with Paul, for several days, I've had several other things on my plate. (Anyone want a wacky replacement to Pollard's P+1 factoring algorithm?).

Anyway, back on topic, I noticed mention of using candidate-by-candidate factoring algorithms in the thread, and it's worth trying to analyse to see what they say:

If we pluck a figure out of the air for sieving depth, say 10T, and pretend that the average machine does <100000p/s, then we conclude that the job's >1000 CPU days. What else could we do in that number of CPU days? If we were to sieve half way, then we'd have 500 days spare for factoring. Say we have 700000 candidates left (I'm in 1s.f. land here), then that's about 1 minute per candidate. You can't do anything useful in one minute. Not even 10 minutes would be useful. Once you know no factors are below 5e12, and you're time limited, you're looking probably at just running Pollard's P-1, with B1>10000, B2=B1*30, and on numbers of this size that's just prohibitive.

i.e. sieving 700000 candidates is _much_ more cost-effective than factoring.

The reason GIMPS use P-1 and ECM to factor candidates is because they _can't_ sieve. Even the old style trial-division NewPGen was probably more effective than factoring, and we're 100 times faster than that now.

Phil