GNU bug report logs - #78476
GNU 'factor' problems with 128-bit word

Previous Next

Full log

Message #26 received at 78476 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Torbjörn Granlund <tg <at> gmplib.org>
Cc: 78476 <at> debbugs.gnu.org
Subject: Re: bug#78476: GNU 'factor' problems with 128-bit word
Date: Wed, 9 Jul 2025 22:44:32 -0700

[Message part 1 (text/plain, inline)]

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.

[1]: https://lists.gnu.org/r/coreutils/2025-01/msg00000.html
[2]: https://git.savannah.gnu.org/git/coreutils.git

[factor1.patch (text/x-patch, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.