divappr tests
Niels Möller
nisse at lysator.liu.se
Mon Dec 14 23:08:58 CET 2009
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.
More information about the gmp-devel
mailing list