[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[PATCH 2/2] Document the MP changes to the factor command.
From: |
James Youngman |
Subject: |
[PATCH 2/2] Document the MP changes to the factor command. |
Date: |
Tue, 29 Jul 2008 10:08:12 +0100 |
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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [PATCH 2/2] Document the MP changes to the factor command.,
James Youngman <=