Ciao, Il Mar, 6 Agosto 2019 9:08 pm, Torbjörn Granlund ha scritto: > ni...@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/ _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
