div_qr_1 interface

Niels Möller nisse at lysator.liu.se
Sun Oct 20 16:58:16 CEST 2013

Torbjorn Granlund <tg at gmplib.org> writes:

> Which tail call?

In the normalized case, the checked in mpn_div_qr_1 does something like

  *qh = ...;
  return mpn_div_qr_1n_pi1(...);

Which is a nice tail call. With the struct-returning version one
gets instead

  res.qh = ...;
  res.r = mpn_div_qr_1n_pi1(...);
  return res;

which I don't think the compiler has any chance of turning into a tail

> Should we unconfuse ourselves and users about what type of inverse is to
> be passed?  The "pi1" moniker might be replaced.  How many one-limb
> inverse types do we currently consider?

It would make some sense to me to do like the mod_1_* functions, and
have a corresponding _cps function precomputing anything needed. The ABI
then says nothing about the details, only that a maximum of 4 (say)
precomputed limbs will be used.

For the fancy div_qr_1 algorithm, what's needed is the same old
reciprocal dinv = (B^2-1)/d - B, and B^2 - d*(B+dinv), same as for
mod_1_1. And shiftcount, in the unnormalized case.


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