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

Previous Next

Full log

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

From: Torbjörn Granlund <tg <at> gmplib.org>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: Coreutils bugs <bug-coreutils <at> gnu.org>
Subject: Re: GNU 'factor' problems with 128-bit word
Date: Sun, 18 May 2025 11:07:01 +0200

Just a quick note.

I don't think is makes much sense to handle two 128-bit words in this
code.  In fact, the use of uintmax_t was a mistake, it should use
"unsigned long" or "unsigned long long" whichever is efficiently
supported directly by the hardware.

While uintmax_t could be made to work also for the cases you report, it
will be inefficient.

A few months ago, I contributed a suggested new core factoring function
to GNU coreutils, which is, IIRC, 2-3 times faster than the current code
for the bignum range.  It uses GMP's mpn functions with "Montgomery
multiplication".

There were two problems with my new core code:

1. It will not work with mini-GMP, which I think is undesiable.

2. It did not optimise for smaller factoring tasks.  The fix for this
would be to merge that from the current coreutils factor.c.

-- 
Torbjörn
Please encrypt, key id 0xC8601622

Previous Next

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