[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#42269: Remove non-GMP code from coreutils factor.c
From: |
Torbjörn Granlund |
Subject: |
bug#42269: Remove non-GMP code from coreutils factor.c |
Date: |
Wed, 08 Jul 2020 18:57:53 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/26.3 (berkeley-unix) |
Paul Eggert <eggert@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