GNU bug report logs - #42269
Remove non-GMP code from coreutils factor.c

Previous Next

Full log

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

From: tg <at> gmplib.org (Torbjörn Granlund)
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: nisse <at> lysator.liu.se, Pádraig Brady <P <at> draigBrady.com>,
 James Youngman <jay <at> gnu.org>, Coreutils bugs <bug-coreutils <at> gnu.org>,
 Jim Meyering <jim <at> meyering.net>
Subject: Re: Remove non-GMP code from coreutils factor.c
Date: Wed, 08 Jul 2020 18:57:53 +0200

Paul Eggert <eggert <at> cs.ucla.edu> writes:

  I recently modified GNU coreutils so that it can assume GMP, possibly
  by compiling and linking mini-gmp.c. This helps simplify the coreutils
  source code and makes coreutils behavior more portable.

  In doing so, I noticed that factor.c has special-purpose code to
  factor integers up to 127 bits. Although this code added functionality
  when coreutils could not assume GMP, it's no longer needed for
  that. And although it runs faster than the GMP code does, while doing
  the recent surgery on factor.c I began to wonder whether the hassle of
  maintaining the code outweighed its usefulness. So I wrote up the
  attached patch, which simply removes the non-GMP code and simplifies
  factor.c quite a bit.

  I assume the attached patch will hurt performance significantly in
  some cases for 127-bit numbers, so I did not install it. Perhaps it
  would be better to keep the non-GMP algorithm and recode it with
  GMP. Or perhaps it would be better to leave the factor.c code alone.

  Comments?

The GMP code in coreutils factor.c was writen by me as a demo (see
gmp/demos) over 25 years ago.  It was put into coreutils' factor.c
without consulting me.  I would have disagreed if I had been asked.

The non-GMP code of coreutils was extremely well-tuned by me and Niels
Möller a couple of years ago.  It is so fast that it has created some
stir in the mathematical community, or so I have been told

I expect the GMP code of factor.c to be pretty much unused.  Why?
Because Pollard rho is suitable only in the range currently covered by
the non-GMP code.  Iff we were to write well-tuned low-level GMP code,
that we could expend the practical range ever so slightly.

By leaving just the GMP code, you would create a pretty useless factor
command.  Any naive old factor command would often beat it.  It would
make much more sense to remove the factor command altogether.

If any code is to be removed, then that would be the GMP code of
coreutils factor.


-- 
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.