udiv_qr_3by2 vs divappr

[Niels Möller]

paul zimmermann <Paul.Zimmermann at inria.fr> writes:

> page 1: there is an extra ')' in the footnote

Fixed.

> page 3: can you detail the proof of R_{bignum} < D? If the algorithm would
> also take as input u_{-1} as in your 2011 paper, I am ok, but here I am not
> sure.

Good catch. I did look at these requirements in some of my earlier
notes, and I think I had it in mind for the second adjustment step. But
I had totally forgotten it now.

To accomodate for u_{-1}, it's not sufficient to have R <= {d_1, d_0} -
1. It seems we need R <= {d_1, d_0} - \beta.

I haven't seen any test failures, so maybe the adjustment gets this
right, maybe it needs some tweak.

> In the proof of Lemma 1, in u_0 (\beta^3 - \beta D - D), the term
> \beta^3 - \beta D - D is negative when D >= \beta^2 - \beta - 1, thus
> you cannot simply bound it by bounding u_0 by \beta-1.

Ooops. Needs to be handled as a special case (d_1 = \beta - 1, d_0 > 0,
v = 0, q = u_1 + 1, q_0 = u0), but I think the upper bound still holds.

Regards,
/Niels

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