Small operands gcd improvements
Marco Bodrato
bodrato at mail.dm.unipi.it
Sat Aug 10 11:12:45 UTC 2019
Ciao,
Il Mar, 6 Agosto 2019 9:08 pm, Torbjörn Granlund ha scritto:
> nisse at lysator.liu.se (Niels Möller) writes:
> Perhaps it would be worthwhile to do a tailcall for when the leftshift
> is 0? I think most gcd calls, irrespective of operand size, will not
> have any factor of two, let alone a common one!
Why? If one is using GCD to search small factors in a number, I agree. It
is better to remove factors 2 before starting any other search... But what
about GCDs used during common mpq operations?
For random numbers, I'd expect a probability 3/4 that at least one of the
operands have a factor 2, and a probability 1/4 for a common factor 2.
I know it is not a good statistical source, but looking at the coverage
https://gmplib.org/devel/lcov/shell/gmp/mpz/divegcd.c.gcov.html
I see 71'781 calls to mpz_divexact_gcd.
35'168 of them use a call to mpz_tdiv_q_2exp ...
> > I suppose some hardwired stuff for the case u >> v (not bitshift, the
> > mathematical meaning of >>!) might want to be parameterised and also
> > ideally tune/tuneup'ed.
>
> Should that be done by gcd_1 only? Or do we need some variant of gcd_11
> with an initial division?
>
> I suppose we should have a lowest level without that (conditional or
> unconditional) and that that level is gcd_11.
I'm aware of two functions using "mpn_gcd_1 (&n, 1, m)":
mpn_perfect_power_p and mpz_mfac_uiui .
They both need to handle even numbers and possibly unbalanced operands.
I mean, the proposed interface is not usefull for those pieces of code.
If we want them to directly call mpn_gcd_11, we should replicate half of
the code in mpn/generic/gcd_1.c in both functions.
I agree, the "case u >> v" should be handled with a per-architecture
tuning, and I do not think we should replicate the thresholds checking in
any function needing the gcd of two limbs...
So, I do not really like the proposed low-level-only interface for gcd_11.
Ĝis,
m
--
http://bodrato.it/papers/
More information about the gmp-devel
mailing list