[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#12350: Composites identified as primes in factor.c (when HAVE_GMP)
From: |
Torbjorn Granlund |
Subject: |
bug#12350: Composites identified as primes in factor.c (when HAVE_GMP) |
Date: |
Mon, 08 Oct 2012 14:12:46 +0200 |
User-agent: |
Gnus/5.11 (Gnus v5.11) Emacs/22.3 (berkeley-unix) |
> 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
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Pádraig Brady, 2012/10/08
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP),
Torbjorn Granlund <=
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/10/08
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Pádraig Brady, 2012/10/08
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/10/08
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/10/08
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/10/08
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Pádraig Brady, 2012/10/08
bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Philipp Thomas, 2012/10/17