mpn_invert implementing ApproximateReciprocal.

Niels Möller nisse at
Fri Dec 11 17:10:05 CET 2009

bodrato at writes:

> I finally had some time to implement and test a version of mpn_invert
> using Newton iteration, the code is attached.

Cool. And very nice performance.

I have one comment after a first quick look at thecode. You compute the
initial approximation using mpn_tdiv_qr,

  /* Compute a base value of rn limbs. */
  { /* Maximum scratch needed by this branch: 3*n + 2 */
    mp_size_t i;
    xp = scratch + rn + 2;				/* 2 * rn limbs */
    for (i = rn - 1; i >= 0; i--)
      xp[i] = ~CNST_LIMB(0);
    mpn_com_n (xp + rn, dp - rn, rn);
    mpn_tdiv_qr (rp, ip - rn, 0, xp, 2 * rn, dp - rn, rn);
    MPN_COPY (ip - rn, rp, rn);

Maybe you can use {sb|dc}pi1_divappr_q here? (But not the mu variant,
since that would give a circular dependency...) According to the
comments, these functions return a quotient which is correct or one unit
too large, so you'd have to compensate for that.


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