On 10/08/2012 21:46 PM, Torbjörn Granlund wrote: > On 10/08/2012 05:01 PM, Pádraig Brady wrote:
> With the new factor rewrite I've noticed a large slowdown, > with the GMP path. No time to investigate at present... > > $ time ~/git/coreutils/src/factor '44444444444444444444444444444444444444444444444444444444444444444444444444444' > gmp > 44444444444444444444444444444444444444444444444444444444444444444444444444444: 2 2 239 4649 5237 21649 42043 513239 29920507 136614668576002329371496447555915740910181043 > > real 0m0.385s > user 0m0.381s > sys 0m0.002s > > $ time factor '44444444444444444444444444444444444444444444444444444444444444444444444444444' > 44444444444444444444444444444444444444444444444444444444444444444444444444444: 2 2 239 4649 5237 21649 42043 513239 29920507 136614668576002329371496447555915740910181043 > > real 0m0.019s > user 0m0.016s > sys 0m0.003s
> > Please try disabling prime proving, using the new -w switch. > I feel pretty confident it will then beat the old code. > > Prime proving sometimes takes a lot of time. It needs to factor p-1 for > each factor p found. Each factor of p-1 is also proven prime, > recursively. > > One might take a more optimistic path, and rely on probabilitic tests. > > We have written Quadratic Sieve code that will at some point probably be > adapted to GNU factor use. It will make factoring speed much less > varying, and furthermore allow practical factoring of much larger > numbers.
Yep you're right. Note -w is not currently exposed in the new GNU version. Tweaking that manually we have: $ time ~/git/coreutils/src/factor -w '44444444444444444444444444444444444444444444444444444444444444444444444444444' 44444444444444444444444444444444444444444444444444444444444444444444444444444: 2 2 239 4649 5237 21649 42043 513239 29920507 136614668576002329371496447555915740910181043 real 0m0.013s user 0m0.010s sys 0m0.003s pb-n5110:primes$ time ~/git/coreutils/src/factor '44444444444444444444444444444444444444444444444444444444444444444444444444444' 44444444444444444444444444444444444444444444444444444444444444444444444444444: 2 2 239 4649 5237 21649 42043 513239 29920507 136614668576002329371496447555915740910181043 real 0m0.387s user 0m0.383s sys 0m0.002s thanks! Pádraig.
