Re: factor inconsistencies/limits?

[James Youngman]

On Fri, Jul 25, 2008 at 11:57 AM, Jim Meyering <address@hidden> wrote:
> Actually, I've wanted coreutils' factor program to work
> with arbitrary-precision numbers for a long time.
> This is mentioned briefly in TODO.  For more detail, see these
> search results:
>
>  
> http://search.gmane.org/search.php?group=gmane.comp.gnu.coreutils.bugs&query=factor+gmp

I have a working GMP-based version (essentially, it's the example
taken from the GMP docs that you mentioned earlier).  For the moment,
the code always uses GMP if it's available.  The GMP version is
dramatically faster for the pathalogical case mentioned in the docs,
and about 2x slower for "easy" cases with small integers.

~/source/GNU/coreutils/coreutils$ time ./src/factor 18446744073709551557
18446744073709551557: 18446744073709551557

real    0m0.003s
user    0m0.000s
sys     0m0.008s
~/source/GNU/coreutils/coreutils$ time factor 18446744073709551557
18446744073709551557: 18446744073709551557

real    0m34.792s
user    0m34.794s
sys     0m0.004s

~/source/GNU/coreutils/coreutils$ wc -l 1m
1000000 1m
~/source/GNU/coreutils/coreutils$ time factor < 1m >/dev/null

real    0m2.668s
user    0m2.660s
sys     0m0.012s
~/source/GNU/coreutils/coreutils$ time ./src/factor < 1m >/dev/null

real    0m5.607s
user    0m4.012s
sys     0m1.584s
~/source/GNU/coreutils/coreutils$ uniq < 1m
1000000000


Given these performance characteristics, I would not be adverse to
using the GMP implementation for all sizes of input.  However, there
is also the maintenance consideration.   We must maintain a non-GMP
implementation for systems which lack GMP (or decline to use it).  I
would in general be concerned about bit-rot in the non-GMP
implementation, so I guess it's worth using it unconditionally for
some subset of inputs in order to be sure it really works for those
who must use it.

What do you think?

Thanks,
James.