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

Previous Next

Full log

View this message in rfc822 format

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: bug#12350: Composites identified as primes in factor.c (when HAVE_GMP)
Date: Tue, 04 Sep 2012 20:26:45 +0100

On 09/04/2012 07:10 PM, Torbjorn Granlund wrote:
> Pádraig Brady<P <at> draigBrady.com>  writes:
>
>    On 09/04/2012 03:46 PM, Jim Meyering wrote:
>    >  There are 9008992 composites of the form with s=2 below 2^64.  With 3
>    >  Miller-Rabin test, one would expect about 9008992/4^64 = 140766 to be
>
>    s/4^64/64/ ?
>
>    For what it's worth I checked the million primes in
>    the range 452,930,477 to 472,882,027 and they're
>    now identified correctly (465658903 was included previously).
>
>    Note processing time has increased with the patch.
>    On my 2.1GHz i3-2310M, running over the above range
>    used to take 14m, but now takes 18m.
>
> It sometimes takes more time to do things correctly.

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%).

> 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 ;)

thanks,
Pádraig.

Previous Next

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