fast inversion

tg at tg at
Wed Apr 29 08:49:56 UTC 2015

nisse at (Niels Möller) writes:

  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?)
I think that style makes sense.

An assembly mpn_com is much faster than a pure C version can ever be,
since assembly will use wide memops.

  Not sure why we're doing this as an inline function in gmp.h.
Me neither.  Perhaps as it is tiny?

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list