Re: factor: new GMP slow down?

[Pádraig Brady]

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.