Small operands gcd improvements

Torbjörn Granlund tg at
Wed Jul 31 11:57:24 UTC 2019

nisse at (Niels Möller) writes:

  The gcd_21 loop takes inputs (u1, u0, v), inputs odd, and all the limbs
  non-zero. It is a much simpler loop than gcd_22

        {u1, u0} <-- {u1, u0} - v   (always > 0)
        if (u0 == 0) { u0 = u1; break; }
        shift out trailing zeros
    while (u1 > 0)

The result is then either v (if u1 = 0) or gcd_11(u0 >> cnt,v) where
cnt needs to be computed here if gcd_11 only likes odd operands.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list