GNU bug report logs - #12350
Composites identified as primes in factor.c (when HAVE_GMP)

Previous Next

Full log

Message #196 received at 12350 <at> debbugs.gnu.org (full text, mbox):

From: Pádraig Brady <P <at> draigBrady.com>
To: Torbjorn Granlund <tg <at> gmplib.org>
Cc: 12350 <at> debbugs.gnu.org, nisse <at> lysator.liu.se,
	Jim Meyering <jim <at> meyering.net>
Subject: Re: bug#12350: Composites identified as primes in factor.c (when
	HAVE_GMP)
Date: Mon, 08 Oct 2012 11:34:56 +0100

On 09/04/2012 10:55 PM, Torbjorn Granlund wrote:
> Pádraig Brady <P <at> draigBrady.com> writes:
>
>    Sure. I was just quantifying the performance change,
>    for others who may be referencing or noticing patches.
>    (Actually, I'd add a note to the commit message that,
>    this increases calculations by about 25%).
>
> And surely mode for certain cases. We spend 25/3 or about 8 times more
> effort in Miller Rabin.
>
>    > As I mentioned in the original post, we will replace the current code
>    > with code that is many times faster.  Your example above will run at
>    > less than a minute on your system.
>
>    I'd left my test files in place in anticipation ;)
>
> 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

cheers,
Pádraig.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.