udiv_qr_3by2 vs divappr
Niels Möller
nisse at lysator.liu.se
Tue Aug 28 16:58:24 UTC 2018
paul zimmermann <Paul.Zimmermann at inria.fr> writes:
> if you need to save \beta with respect to the proof of [4], yes maybe you need
> to repeat that proof to explain how you save the extra +1.
I think we can make it work. We have the reciprocal v, and a
corresponding "remainder"
K = \beta^3 - {d_1, d_0} (\beta + v)
in the range 0 < K < {d_1, d_0}.
In the expression for the remainder, one of the terms is
u_1 K / \beta
In [4], we only assume that {u_1_u_0} < D = {d_1, d_0} (the u's are numbered
differently, though).
Then we have
u_1 < (D - u_0) / \beta
which is used to bound the u_1 K / \beta term.
But thanks to the upfront handing of large {u_1, u_0}, in the current
case we have
{u_1, u_0} < D - d_1
and
u_1 < D - d_1 - u_0
I think this is sufficient to get
R' < max(\beta ^2 - {d_1, d_0} - \beta
with some margin.
I hope I get some time for the paper the next few days.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel
mailing list