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

From: Torbjorn Granlund <[email-masked]>
Date: Mon, 08 Oct 2012 14:12:46 +0200

> Please do, and let me and Niels know if it takes more than 45s.  Your
  > test case takes 28s on my 3.3 GHz Sandy bridge system with our current
  > code.  I'm a little disappointed the code doesn't beat the old code more
  > for small factorisations.
  
  So on my 2.1GHz i3-2310M, running over the range 452,930,477 to 472,882,027.
  
  old broken code = 14m
  old fixed code  = 18m
  new code        = 63s
  
OK, this is about 60% slower than I would have expected.  Our code at
http://gmplib.org:8000/factoring/ should run at about 39s on your
system.  (I am using gcc 4.7.1.)

I haven't looked at the final version that went into codeutils, so I
have no idea why it runs slower.  A wild guess is that its actual input
or tokenisation has been slowed down.  For smallish numbers, such things
can dominate over actually factoring the numbers.

I think the current coreutils factor performance for smallish numbers
might be sufficient.  (Larger numbers than 2^100 need a bit too much
time, but we are working on a fix.)

-- 
Torbjörn