[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: |
Jim Meyering |
Subject: |
bug#12350: Composites identified as primes in factor.c (when HAVE_GMP) |
Date: |
Sun, 30 Sep 2012 17:33:33 +0200 |
Torbjorn Granlund wrote:
> Jim Meyering <address@hidden> writes:
>
> > Thanks. Here's how I've integrated it so far.
> > This is not ready to push, but rather just to give you an idea
> > of what's coming. I'm sure I'll have to adjust things before pushing.
>
> There have been a few corrections, and I've fleshed out some log entries.
>
> The following series is ready:
>
> [PATCH 01/13] build: remove redundant dependency: $(PROGRAMS):
> [PATCH 02/13] factor: prepare for the new factor program
> [PATCH 03/13] factor: new implementation; not yet integrated
> [PATCH 04/13] build: add rules to build the new factor program
> [PATCH 05/13] factor: improvements from
> [PATCH 06/13] factor: merge with preexisting factor, integrate
> [PATCH 07/13] maint: use __builtin_expect only if __GNUC__
> [PATCH 08/13] maint: syntax-check: add make-prime-list exemptions
> [PATCH 09/13] factor: 25% speed-up, on output
> [PATCH 10/13] build: avoid warning about unused macro
> [PATCH 11/13] maint: mark set-but-not-used variables with
> [PATCH 12/13] maint: avoid -Wsuggest-attribute=const warning
> [PATCH 13/13] maint: make-prime-list: do not ignore write failure
>
> Torbjorn and Niels,
>
> I'd be happy to include more fine-grained changes to factor.c
> if you can convert the http://gmplib.org:8000/factoring commits
> and ChangeLog deltas to git commits where the ChangeLog delta
> appears in the commit log and passes coreutils' commit-log-checking hook.
> But that may be more trouble than it's worth.
>
> I think those change logs are not super relevant for the coreutils
> ChangeLog. "factor.c: Complete rewrite" seem sufficient to me...
>
> Both Niels and I mailed the paperwork to the FSF a week or two ago.
> Have you heard from them? Snail mail tend to disappear.
Not yet. I've just asked them.
> The only missing piece is a NEWS entry.
> Would one of you please write that?
>
> Sure. Do you have an example of an old one? Here is a start:
Here are a few years worth of NEWS entries:
http://git.sv.gnu.org/cgit/coreutils.git/tree/NEWS
That looks fine. Thanks.
> The 'factor' program has been completely rewritten for speed and to
> add range. It can now always factor numbers up to 2^128, even without
> GMP support. Its speed is from a few times better (for small numbers)
> to over 10,000 times better (just below 2^64). The new program also
> runs a proper prime criterion on found factors, not a probabilistic
> test.
How about this in place of the final sentence?
The new program also
runs a deterministic primality test for each prime factor, not just
a probabilistic test.
> As you might have spotted from our repo, I and Nisse Möller are working
> on a small Quadratic Sieve ("QS") factorer, for which we have two goals:
>
> (1) offer it as a HAVE_GMP dependent addition to GNU factor
> (2) make a more complex variant intended to be state-of-the-art
>
> QS is one of the most powerful factoring algorithms yet discovered.
> With our implementation, we will be able to factor even the most
> stubborn 128-bit composites within seconds, but with enough patience
> numbers of upp to 300 bits are within reach.
>
> The code is not very large, it will make 'factor' about 30% larger.
That sort of code size increase sounds perfectly
reasonable considering the algorithmic improvements.
> It should factor any 128-bit numbers in around 1 second. Any 30 bits
> extra take about 10 times more time.
That sounds great.
> I don't think these new developments should hold up a commit of our old
> factor.c developments.
I agree.
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), (continued)
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/17
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/17
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/17
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/17
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/18
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/18
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/18
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/24
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/30
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/30
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP),
Jim Meyering <=
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/30
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/17
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/14
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/14
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/14
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Jim Meyering, 2012/09/14
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/14
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Paul Eggert, 2012/09/06
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Torbjorn Granlund, 2012/09/07
- bug#12350: Composites identified as primes in factor.c (when HAVE_GMP), Niels Möller, 2012/09/07