On 26 Nov 2001, at 19:18, George Woltman wrote: > Hi, > > At 12:46 AM 11/27/2001 +0100, george de fockert wrote: > >One of my machines does trial factoring. > >Now in the M17900000 range, factoring to 2^66. > >This takes a very long time, is it better to let it double check ? > > It is a matter of personal preference. You can figure out how long a > double-check would take at http://www.mersenne.org/bench.htm > > Another option for slow machines is ECM factoring. See > http://www.mersenne.org/ecm.htm for details (this is not an > automated project)
Or P-1 factoring. Again not automated. > > >Or is it time for a more efficient trial factor implementation (if > >possible ?). > > If someone wants to volunteer to improve factoring performance that > would be great. The P4 could use an SSE2 implementation. > CPU-specific factoring code over 64 bits could be written. I had a good look at this a couple of years ago. There are essentially two parts to the trial factoring "problem": one is generating candidate factors (or, rather, quickly avoiding those values which cannot for one reason or another possibly be factors), the other is actually trying the factor. Whilst I was able to get reasonably close to the performance of George's code for trying the factor - possibly even a tiny bit better for factors with only just over 2^64 - I got nowhere near the performance of his candidate elimination code. One of the lessons I learned from the effort is that multiple precision arithmetic is _hard work_ on systems which have only one carry flag. If SSE/SSE2 enables you to have multiple carry flags then you could effectively try two or more factors in parallel, this would yield a considerable performance increase. But I'm not sure offhand whether the instruction set supports this. In any case, slower systems (the ones that _should_ be running factoring?) don't in any case support SSE or SSE2. > > While factoring could probably be improved tens of percent, it has not > been a high priority item for me. A 10% boost in factoring speed lets > you factor (on average) 10% deeper, which finds about 1 more factor in > every 650 exponents. That isn't a great throughput improvement for > the GIMPS project. Indeed. The other way to look at this (same conclusion) is that factoring is way, way ahead of LL testing, so any perceived inefficiency is not critical. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
