From 00c6aacf318a6ef0db4895b08d572d924eab90d0 Mon Sep 17 00:00:00 2001 From: James Youngman Date: Thu, 31 Jul 2008 09:58:10 +0200 Subject: 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. --- doc/coreutils.texi | 58 ++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 37 insertions(+), 21 deletions(-) (limited to 'doc') 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 -- cgit v1.2.3-54-g00ecf