udiv_qr_3by2 vs divappr

[Niels Möller]

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.