udiv_qr_3by2 vs divappr

paul zimmermann Paul.Zimmermann at inria.fr
Thu Aug 30 10:47:24 UTC 2018


       Dear Niels,

> I've updated the paper (same location,
> https://www.lysator.liu.se/~nisse/misc/schoolbook-divappr.pdf).

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

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.

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.

Paul




More information about the gmp-devel mailing list