fast inversion

[tg at gmplib.org]

nisse at lysator.liu.se (Niels Möller) writes:

  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?)
  
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?

-- 
Torbjörn
Please encrypt, key id 0xC8601622