coreutils
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Improvements to factor.c


From: Torbjörn Granlund
Subject: Re: Improvements to factor.c
Date: Sat, 04 Jan 2025 16:40:44 +0100
User-agent: Gnus/5.13 (Gnus v5.13)

Pádraig Brady <P@draigBrady.com> writes:

  Well it's certainly a lot simpler.
  Do you have perf figures comparing the new code?

For the "early" bignum range, meaning just over 128 bits, it is about 3
times faster.  For truly huge numbers which are still factorisable
(i.e., smooth numbers), the speedup factor slowly goes to 1.  (It might
even ultimately become slower, for say million-bit smooth numbers, but I
would expect it to be extremely rare for anybody to use coreutils
factor.c for the factorisations of huge smooth numbers.)

Without the special single-word and double-word code in the current
factor.c, it is slower for those number ranges.  That's why I suggest to
merge this new bignum code to the old code (or the other way around;
keeping the struct factors would streamline things).  IIRC, the old
code, once it starts calling GMP, it will finish the factorisation using
GMP. That's undesriable; once the cofactors fit in two words, the
double-word code should be invoked.

The single-limb code of course takes just milliseconds always, even in
some worst-case scenario, but I still think it is worth keeping the old
code for that range.  It is not impossible that somebody uses coreutils
factor in a script, where it is called a large number of times.

For the range where the double-word code is used, the new code is also
slower, but I haven't measured by how much.

-- 
Torbjörn
Please encrypt, key id 0xC8601622



reply via email to

[Prev in Thread] Current Thread [Next in Thread]