bug#78476: GNU 'factor' problems with 128-bit word
From:
Paul Eggert
Subject:
bug#78476: GNU 'factor' problems with 128-bit word
Date:
Wed, 9 Jul 2025 22:44:32 -0700
User-agent:
Mozilla Thunderbird
On 2025-05-20 00:04, Torbjörn Granlund wrote:
I am too busy to take care of this. Sorry.
Understandable. Thanks for taking the time to look at my email.
Preferably, this problem should be fully understood.
Yes, that'd be better but it appears that nobody has the time to do so.
However, we can address this in a different way, by removing the buggy
code instead of understanding it. I did so by re-reading this bug report
along with your January proposal[1], looking at factor.c again, and
committing changes mostly along the lines you suggested, as follows:
* Merge the January proposed factor.c into GNU coreutils.
* Port to mini-gmp.c, which lacks mpn_tdiv_qr.
* Don't use uintmax_t or unsigned __int128 as a word; just use the same
mp_limb_t type that GMP uses.
* Remove the USE_SQUFOF code (which was unused).
* Don't try to prove primality; trust Baillie-PSW as being good enough.
Use mpz_probab_prime_p for that, even for numbers that fit into two
limbs or less.
* Port to unlikely platforms lacking 32- or 64-bit words.
* Minor speedups, e.g., convert strings to uuint faster, and decrement
MR_REPS from 25 to 24 as that's a sweet spot in GMP.
* Statically check for unsupported (and unlikely) build configurations.
* Add some comments.
Two FIXMEs remain in factor.c. To address the first one, would GMP
accept longlong.h changes to make it standalone even with
-Wunused-macros? Currently longlong.h is not standalone in that sense,
even if LONGLONG_STANDALONE is defined. The changes should be minor.
You can grab all the coreutils updates from Savannah by cloning [2] as
usual. For convenience in reviewing I am attaching the factors-related
changes between the old and new Coreutils as a single patch. Comments
are of course welcome.