diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/coreutils.texi | 58 |
1 files changed, 37 insertions, 21 deletions
diff --git a/doc/coreutils.texi b/doc/coreutils.texi index 76b22e44d..c789a6cc4 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 -@command{factor} 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. +@table @samp +@item --help +Print a short help on standard output, then exit without further +processing. -@example -$ p=`echo '4294967279 * 4294967291'|bc` -$ factor $p -18446743979220271189: 4294967279 4294967291 -@end example +@item --bignum +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: +@item --no-bignum +Forces the use of native operations instead of GNU MP. This causes +@command{factor} to fail for larger inputs. -@example -$ factor 18446744073709551557 - 18446744073709551557: 18446744073709551557 -@end example +@item --version +Print the program version on standard output, then exit without further +processing. +@end 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 |