fast inversion

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> mpn_neg id defined in gmp.h, where we can not check for HAVE_NATIVE, but I
> suspect that also the C version of mpn_com is faster than mpn_neg (in the
> former, limbs do not depend on one another, no "carry" propagation).

I'd suggest something like this (totally untested)

  mp_limb_t
  mpn_neg (mp_ptr rp, mp_srcptr up, mp_size_t n)
  {
    /* Low zero limbs are unchanged by negation. */
    while (*up == 0)
      {
        *rp++ = 0;
        up++;
        if (!--n)
          /* All zero */
          return 0;
      }
  
    /* First non-zero limb is negated. */
    *rp++ = - *up++;
  
    /* Higher limbs get complemented. */
    if (--n)
      mpn_com (rp, up, n);
  
    return 1;
  }

In the common case, the bulk of the work is the final mpn_com call. And
if there are many low zeros, the initial loop should make good progress
with reasonably few c/l. (Both mpn_neg and mpn_com require n > 0, right?)

Not sure why we're doing this as an inline function in gmp.h.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.