From 2ce3fc0c1b912aeed99f610cec392ba5d68dd5f5 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Thu, 3 Jul 2025 09:24:27 -0700 Subject: [PATCH] =?utf8?q?doc:=20update=20=E2=80=98factor=E2=80=99=20bench?= =?utf8?q?marks?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- doc/coreutils.texi | 12 ++++++------ src/factor.c | 5 +---- 2 files changed, 7 insertions(+), 10 deletions(-) diff --git a/doc/coreutils.texi b/doc/coreutils.texi index 0648463dfb..7fc2db571c 100644 --- a/doc/coreutils.texi +++ b/doc/coreutils.texi @@ -19158,7 +19158,7 @@ $ factor --exponents 3000 If the number to be factored is small (less than @math{2^{127}} on typical machines), @command{factor} uses a faster algorithm. -For example, on a circa-2017 Intel Xeon Silver 4116, factoring the +For example, on a circa-2021 Intel Xeon W-1350, factoring the product of the eighth and ninth Mersenne primes (approximately @math{2^{92}}) takes about 4 ms of CPU time: @@ -19169,16 +19169,16 @@ $ n=$(echo "$M8 * $M9" | bc) $ bash -c "time factor $n" 4951760154835678088235319297: 2147483647 2305843009213693951 -real 0m0.004s +real 0m0.006s user 0m0.004s -sys 0m0.000s +sys 0m0.002s @end example For larger numbers, @command{factor} uses a slower algorithm. On the same platform, factoring the eighth Fermat number @math{2^{256} + 1} -takes about 14 seconds, and the slower algorithm would have taken -about 750 ms to factor @math{2^{127} - 3} instead of the 50 ms needed by -the faster algorithm. +takes about 6400 ms. However, large primes are identified quickly: +it takes just 420 ms to factor the Mersenne prime @math{2^{11213} - 1} +into itself and 1. Factoring large numbers is, in general, hard. The Pollard--Brent rho algorithm used by @command{factor} is particularly effective for diff --git a/src/factor.c b/src/factor.c index 849c684e61..bb2347e829 100644 --- a/src/factor.c +++ b/src/factor.c @@ -51,10 +51,7 @@ Pollard-Brent rho code, use Montgomery's trick of multiplying all n-residues by the word base, allowing cheap Hensel reductions mod n. - The GMP code uses an algorithm that can be considerably slower; - for example, on a circa-2017 Intel Xeon Silver 4116, factoring - 2^{127}-3 takes about 50 ms with the two-word algorithm but would - take about 750 ms with the GMP code. + The GMP code uses an algorithm that can be considerably slower. Improvements: -- 2.47.3