mpn_invert implementing ApproximateReciprocal.

[Niels Möller]

bodrato at mail.dm.unipi.it 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.

Regards,
/Niels

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