divappr tests

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> Fixing this is the next item on http://gmplib.org/devel/GMP44.html I
> intend to address.

Nice. Then I'll write that email right away...

I think an interface like the following would make sense:

  mp_limb_t
  mpn_divappr (mp_ptr qp, mp_size_t qn,
               mp_srcptr_t np, mp_srcptr_t dp, mp_size_t dn);

qn is an input argument, and specifies computing qn quotients limbs
(plus returned hi word, maybe). Input n is of size qn+1, input d is of
size dn, 1 <= dn <= qn + 1.

If dn = qn + 1, the function should return a q such that for all n' and
d' of appropriate sizes with n and d as the most significant limbs,

  q <= floor(n'/d') <= q + 1.

If dn <= qn, d is considered untruncated, and the requirement on q is
instead that

  q <= floor(n'/d) <= q + 1

for all n' of the right size and with n as the most significant part.

Not sure if any tweaks are needed to make this mathematically possible
and computationally practical... If un-normalized d are supported, I
imagine one might need dn = qn + 2 to get sufficient precision.

I suspect it may not be possible to make sure that the probability of q
being one-off (for fixed d and n and random n', d') is very small.

PS. And I'd consider dropping the _q from the name of the function,
since we won't have any divappr_qr, will we?

Regards,
/Niels

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