Torbjorn Granlund wrote: > 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.
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.
