Small operands gcd improvements

[Marco Bodrato]

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/