fast inversion

Niels Möller nisse at
Wed Apr 29 07:34:01 UTC 2015

bodrato at 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)

  mpn_neg (mp_ptr rp, mp_srcptr up, mp_size_t n)
    /* Low zero limbs are unchanged by negation. */
    while (*up == 0)
        *rp++ = 0;
        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.


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

More information about the gmp-devel mailing list