factor arbitrarily large numbers

* m4/gmp.m4: New file; adds cu_GMP, which detects GNU MP.
* configure.ac: Use cu_GMP.
* src/Makefile.am: Link factor against libgmp if available.
* src/factor.c: Use GNU MP if it is available.
(emit_factor, emit_ul_factor, factor_using_division,
factor_using_pollard_rho, extract_factors_multi,
sort_and_print_factors, free_factors): new functions
for the arbitrary-precision implementation, taken from an example
in GNU MP.
(factor_wheel): Renamed; was called factor.
(print_factors_single): Renamed; was called print_factors.
(print_factors): New function, chooses between the single- and
arbitrary-precision algorithms according to availability of GNU MP
and the length of the number to be factored.
(usage, main): New options --bignum and --no-bignum.
* coreutils.texi (factor invocation): Document new command-line
options for the MP implementation and update the performance
numbers to take into account the asymptotically faster algorithm.
* TODO: Remove item about factoring large primes (it's done).
* m4/gmp.m4: Add support for --without-gmp.
* NEWS: Mention the new feature.

1 files changed, 0 insertions, 3 deletions

diff --git a/TODO b/TODO
index e7f050821..c7bb820d2 100644
--- a/TODO
+++ b/TODO
@@ -127,9 +127,6 @@ Changes expected to go in, someday.
   an implicit --NO-dereference-command-line-symlink-to-dir meaning.
   Pointed out by Karl Berry.
 
-  A more efficient version of factor, and possibly one that
-  accepts inputs of size 2^64 and larger.
-
   dd: consider adding an option to suppress `bytes/block read/written'
   output to stderr.  Suggested here:
     http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=165045