Incidentally, whilst removing the basecase implementation I found and removed a bug in the asymptotically fast division code. Or rather, removing the basecase implementation also removed that bug. However, this could not have been what caused the bug we observed in the basecase code.
Bill. On 13 November 2015 at 22:02, Bill Hart <goodwillh...@googlemail.com> wrote: > > > On 13 November 2015 at 21:41, Jean-Pierre Flori <jpfl...@gmail.com> wrote: > >> >> >> On Friday, November 13, 2015 at 12:34:41 PM UTC-8, Bill Hart wrote: >>> >>> >>> >>> On 13 November 2015 at 19:10, Jean-Pierre Flori <jpf...@gmail.com> >>> wrote: >>> >>>> >>>> >>>> On Friday, November 13, 2015 at 9:40:27 AM UTC-8, Bill Hart wrote: >>>>> >>>>> Not in the published divide-and-conquer algorithm, no. >>>>> >>>>> There was a bug in the implementation of the new basecase algorithm, >>>>> which was not published, nor very important. On most machines it was >>>>> switched off. And even on the machines where it was used (with the >>>>> exception of itanium where it seemed to be used a lot), it was only used >>>>> for *very* small operands. >>>>> >>>>> To be verbose, do you mean the basecase schoolbook multiprecision >>>> division using 3by2 small division using a new 1 word precomputed inverse >>>> is broken? >>>> >>> >>> Yes it was a 3by2 version using a new 1 word precomputed inverse >>> (unrelated to the 3by2 division originally used in MPIR and GMP). >>> >> So do you still trust the 3by2 algorithm in your preprint? >> > > I don't have any reason to not trust it. I believe this was just an > implementation bug. > > If you look at the most recent commit to the MPIR repository from me, > you'll see why I think that. > > > https://github.com/wbhart/mpir/commit/8435273a1ae6c033bec43fc54966bf121b73cf62 > > >> >>> >>>> So is the code from BDSNT broken as wel? >>>> https://github.com/wbhart/bsdnt/blob/master/helper.c#L186 >>>> https://github.com/wbhart/bsdnt/blob/master/nn_quadratic.c#L240 >>>> >>>> >>> Doubtful. The implementation in MPIR was much, much more complex. >>> >>> The algorithm itself is quite straightforward. >>> >>> On the other hand, bsdnt does not have many users, so if bugs exist >>> there, it is much less likely they will be detected, so beware. >>> >>> Yup, I did an implementation myself for another project using your >> precomputed reciprocal and a naive schoolbook long division. >> I tested the values mentioned on http://trac.sagemath.org/ticket/19280 >> and get a correct remainder. >> > > Good to know. Thanks. > > >> Note that I don't store the quotient but it should be correct as well. >> If you are aware of any other values triggered wrong answer in MPIR, I'd >> be more than happy to pass them to my implementation. >> > > I'm not aware of other values that triggered it, though there may well > have been others. This was certainly a rare corner case. As I said, I had > tested the original implementation on a variety of inputs for hours. > > Bill. > >> -- >> You received this message because you are subscribed to the Google Groups >> "mpir-devel" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to mpir-devel+unsubscr...@googlegroups.com. >> To post to this group, send email to mpir-de...@googlegroups.com. >> Visit this group at http://groups.google.com/group/mpir-devel. >> For more options, visit https://groups.google.com/d/optout. >> > > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
