On 7/8/20 12:34 PM, Torbjörn Granlund wrote:
Any number which does not happen to be B-smooth for, say B < 2^30, will
show easily measurable performance difference of 5x to 40x IIRC.
Ah, I had tried the example in the manual, (2^31 - 1) * (2^61 - 1). Even though
it isn't B-smooth for B <
ni...@lysator.liu.se (Niels Möller) writes:
I'm really not that familiar with state of the art factoring, but I'd
guess pollard rho is a bad algorithm choice for that range, and one
ought to use, e.g., some variant of the quadratic sieve.
Let me modify that statement somewhat.
Pollars rho
t...@gmplib.org (Torbjörn Granlund) writes:
> If any code is to be removed, then that would be the GMP code of
> coreutils factor.
I agree with Torbjörn. The GMP code in GNU factor might have made more
sense when most computers were 32-bit, and "bignums" were smaller.
But on 64-bit computers,
Paul Eggert writes:
Could you give an example of where the 128-bit code shines, compared
to the GMP code on the same arguments? I could add the example as a
comment in the factor.c code, to let me and future maintainers know
why it's useful for performance.
Any number which does not
On 7/8/20 9:57 AM, Torbjörn Granlund wrote:
The non-GMP code of coreutils was extremely well-tuned by me and Niels
Möller a couple of years ago.
How time flies! The code was merged in 2012.
By leaving just the GMP code, you would create a pretty useless factor
command. Any naive old factor
Paul Eggert writes:
I recently modified GNU coreutils so that it can assume GMP, possibly
by compiling and linking mini-gmp.c. This helps simplify the coreutils
source code and makes coreutils behavior more portable.
In doing so, I noticed that factor.c has special-purpose code to