bug#78476: GNU 'factor' problems with 128-bit word
Paul Eggert <[email protected]>
| Newsgroups | gmane.comp.gnu.core-utils.bugs |
|---|---|
| Organization | UCLA Computer Science Department |
| Message-ID | <[email protected]> |
On 2025-07-27 01:51, Torbjörn Granlund wrote: > Thank you for merging the new mpn-based factoring code! > > The code looks good, I did not see anything which needs improvements. > > I believe the factoring speedup for numbers of 3 or more limb is quite > significant (2x-3x), even when not considering the time saved by not > proving primality of found factors. > > You might want mention that in the header about the 2025 improvements. Thanks for the review and for the kind words. I installed the attached further doc fix and am closing this bug report.
0001-doc-mention-2025-speedup-on-large-composites.patch
(text/x-patch, 1.4 KB)
From 4a2402dcfa8b705b63f43b76d7be8418e08f8f8f Mon Sep 17 00:00:00 2001 From: Paul Eggert <[email protected]> Date: Sun, 27 Jul 2025 07:30:29 -0700 Subject: [PATCH] doc: mention 2025 speedup on large composites --- NEWS | 3 ++- src/factor.c | 3 ++- 2 files changed, 4 insertions(+), 2 deletions(-) diff --git a/NEWS b/NEWS index 17a43b064..0b2be7116 100644 --- a/NEWS +++ b/NEWS @@ -4,7 +4,8 @@ GNU coreutils NEWS -*- outline -*- ** Changes in behavior - 'factor' is now much faster at identifying large prime numbers. + 'factor' is now much faster at identifying large prime numbers, + and significantly faster on composite numbers greater than 2^128. ** Bug fixes diff --git a/src/factor.c b/src/factor.c index 44c0deb6a..b3af25b5f 100644 --- a/src/factor.c +++ b/src/factor.c @@ -19,7 +19,8 @@ Arbitrary-precision code adapted by James Youngman from Torbjörn Granlund's factorize.c, from GNU MP version 4.2.2. In 2012, the core was rewritten by Torbjörn Granlund and Niels Möller. - In 2025, Torbjörn Granlund and Paul Eggert sped up primality checking. + In 2025, Torbjörn Granlund and Paul Eggert sped up primality checking, + and improved performance on composite numbers greater than 2^128. Contains code from GNU MP. */ /* Efficiently factor numbers that fit in one or two words (word = mp_limb_t), -- 2.48.1