[PATCH 2/2] Document the MP changes to the factor command.

[James Youngman]

2008-07-29  James Youngman  <address@hidden>

        * 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.
---
 doc/coreutils.texi |   58 +++++++++++++++++++++++++++++++++------------------
 1 files changed, 37 insertions(+), 21 deletions(-)

diff --git a/doc/coreutils.texi b/doc/coreutils.texi
index 8eb8ac9..e2e3638 100644
--- a/doc/coreutils.texi
+++ b/doc/coreutils.texi
@@ -14359,36 +14359,52 @@ factor @var{option}
 If no @var{number} is specified on the command line, @command{factor} reads
 numbers from standard input, delimited by newlines, tabs, or spaces.
 
-The only options are @option{--help} and @option{--version}.  @xref{Common
-options}.
+The @command{factor} command supports only a small number of options:
 
-The algorithm it uses is not very sophisticated, so for some inputs
address@hidden runs for a long time.  The hardest numbers to factor are
-the products of large primes.  Factoring the product of the two largest 32-bit
-prime numbers takes about 80 seconds of CPU time on a 1.6 GHz Athlon.
address@hidden @samp
address@hidden --help
+Print a short help on standard output, then exit without further
+processing.
 
address@hidden
-$ p=`echo '4294967279 * 4294967291'|bc`
-$ factor $p
-18446743979220271189: 4294967279 4294967291
address@hidden example
address@hidden --use-mp
+Forces the use of the GNU MP library.   By default, @command{factor}
+selects between using GNU MP and using native operations on the basis
+of the length of the number to be factored.
 
-Similarly, it takes about 80 seconds for GNU factor (from coreutils-5.1.2)
-to ``factor'' the largest 64-bit prime:
address@hidden --nouse-mp
+Forces the use of native operations instead of GNU MP.  This causes
address@hidden to fail for larger inputs.
 
address@hidden
-$ factor 18446744073709551557
-  18446744073709551557: 18446744073709551557
address@hidden example
address@hidden --version
+Print the program version on standard output, then exit without further
+processing.
address@hidden table
 
-In contrast, @command{factor} factors the largest 64-bit number in just
-over a tenth of a second:
+Factoring the product of the eighth and ninth Mersenne primes
+takes about 30 milliseconds of CPU time on a 2.2 GHz Athlon.
 
 @example
-$ factor `echo '2^64-1'|bc`
-18446744073709551615: 3 5 17 257 641 65537 6700417
+M8=`echo 2^31-1|bc` ; M9=`echo 2^61-1|bc`
+/usr/bin/time -f '%U' factor $(echo "$M8 * $M9" | bc)
+4951760154835678088235319297: 2147483647 2305843009213693951
+0.03
 @end example
 
+Similarly, factoring the eighth Fermat number @math{2^{256}+1} takes
+about 20 seconds on the same machine.
+
+Factoring large prime numbers is, in general, hard.  The Pollard Rho
+algorithm used by @command{factor} is particularly effective for
+numbers with relatively small factors.  If you wish to factor large
+numbers which do not have small factors (for example, numbers which
+are the product of two large primes), other methods are far better.
+
+If @command{factor} is built without using GNU MP, only
+single-precision arithmetic is available, and so large numbers
+(typically @math{2^{64}} and above) will not be supported.  The 
single-precision
+code uses an algorithm which is designed for factoring smaller
+numbers.
+
 @exitstatus
 
 
-- 
1.5.6.3