Jim Meyering <j...@meyering.net> 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.
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:
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.
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.
It should factor any 128-bit numbers in around 1 second. Any 30 bits
extra take about 10 times more time.
I don't think these new developments should hold up a commit of our old
factor.c developments.
--
Torbjörn
