bug#12350: Composites identified as primes in factor.c (when HAVE_GMP)

[Torbjorn Granlund]

Paul Eggert <address@hidden> writes:

  On 09/06/2012 02:33 PM, Jim Meyering wrote:
  >> > * We have some hardwired W_TYPE_SIZE settings for the code interfacing
  >> >   to longlong.h.  It is now 64 bits.  It will break on systems where
  >> >   uintmax_t is not a 64-bit type.  Please see the beginning of
  >> >   factor.c.
  > I wonder how many types of systems would be affected.
  
  It's only a matter of time.  GCC already supports 128-bit
  integers on my everyday host (Fedora 17, x86-64, GCC 4.7.1).
  Eventually uintmax_t will grow past 64 bits, if only for the
  crypto guys.
  
It should however be noted that uintmax_t stays at 64 bits even with
GCC's 128-bit integers.  I think the latter are declared as not being
integers, or something along those lines, to avoid the ABI-breaking
change of redefining uintmax_t.

  If the code needs exactly-64-bit unsigned integers, shouldn't
  it be using uint64_t?  That's the standard way of doing
  that sort of thing.  Gnulib can supply the type on pre-C99
  platforms.  Weird but standard-conforming platforms that
  don't have uint64_t will be out of luck, but surely they're out
  of luck anyway.
  
The code does not need any particular size of uintmax_t, except that we
need a preprocessor-time size measurement of it.  The reason for this is
longlong.h's tests of which single-line asm code to include.

The new factor program works without longlong.h, but some parts of it
will become 3-4 times slower.  To disable longlong.h, please compile
with -DUSE_LONGLONG_H=0. (The worst affected parts would probably be the
single-word Lucas code and all double-word factoring.)

I suppose that an autoconf test of the type size will be needed at least
for theoretical portability, if longlong.h is to be retained.

There is one other place where some (hypothetical) portability problems
may exist, and that's make-prime-list.c.  It prints a list of uintmax_t
literals.

We let the coreutils maintainers worry about the allowable complexity of
the factor program; I and Niels are happy to sacrifice some speed for
lowering the code complexity.  But first we will increase it by
retrofitting GMP factoring code.  :o)

-- 
Torbjörn