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

Previous Next

Full log

View this message in rfc822 format

From: tg <at> gmplib.org (Torbjörn Granlund)
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: nisse <at> lysator.liu.se, P <at> draigBrady.com, jay <at> gnu.org, 42269 <at> debbugs.gnu.org, jim <at> meyering.net
Subject: bug#42269: Remove non-GMP code from coreutils factor.c
Date: Wed, 08 Jul 2020 21:34:44 +0200

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

  Could you give an example of where the 128-bit code shines, compared
  to the GMP code on the same arguments? I could add the example as a
  comment in the factor.c code, to let me and future maintainers know
  why it's useful for performance.

Any number which does not happen to be B-smooth for, say B < 2^30, will
show easily measurable performance difference of 5x to 40x IIRC.

A semantic difference which sometimes makes the speed difference less
pronounced is that the non-GMP code proves that the printed factors are
indeed prime.  We use a criterion which requires factoring of p-1 for
any assumed prime factor p.  In unlucky cases that recursive
factorisation is costlier than the main factorisation.

I have a patch which makes the non-GMP code some 2x - 3x faster.  It's
been maturing for several years now, so I suppose I should really finish
it.  (It got tangled with code which improves the GMP case by letting it
fall into the non-GMP code as numbers get smaller.  That sounds simple
but is quite messy for various reasons.  It is also not clear how much
complexity we could defend for this command of limited utility.)

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