udiv_qr_3by2 vs divappr

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> paul zimmermann <Paul.Zimmermann at inria.fr> writes:
>
>> 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.

I think the algorithm got it right, but analysis was wrong.

>> 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.

Fixed.

Updated paper available at
http://www.lysator.liu.se/~nisse/misc/schoolbook-divappr.pdf.
Also fixes one other slight bug in the analysis, it uses that

  (R - 1) mod \beta^2 = { \tilde r, \beta - 1 - p_0}

and then assumes that need R - 1 > -\beta^2. New version rules out R - 1
= -  2 \beta, which could happen if D = \beta^2 - 1 and u_1 = u_0 = 0.
Analyzing u1 = u_0 = 0 as a special case allows us to strengthen the
bound \tilde R \geq -D to a strict inequality \tilde R > -D.

Regards,
/Niels

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