I'm pretty sure the division by B-1 algorithm itself is not new, I think Quercia's numerix library had it some time ago, from memory he used something basically equivalent to calling mpn_add_n with overlapping source and destination buffers (very sneaky). Also I believe Zimmerman + Bodrato + Zanoni independently came up with that idea (or something similar). I'm only claiming credit for the idea of combining it with multiplication to get fast division by divisors of B-1. I wouldn't be terribly surprised if that had been done before as well, but I don't know of any instances --- let me know if you find any. I also am not claiming credit for figuring out a good assembly implementation of this --- it looks like at least one MPIR developer has figured this out, and I know Torbjorn has done so as well on several chips (but I have not gone through the pain of trying to understand how his code works).
david On Feb 15, 3:15 pm, Bill Hart <goodwillh...@googlemail.com> wrote: > OK, I checked and the discussion about this paper was related to > something else. Sorry for the confusion. So it was indeed you that > came up with the divide by B-1 idea. > > Bill. > > 2009/2/15 Bill Hart <goodwillh...@googlemail.com>: > > > I'm talking about that paper. > > > I don't recall when we discussed this paper, but I recall you asking > > me "have you read this paper" at some point, and my memory of it was > > that you considered something we were discussing as essentially being > > present in there. Sorry if I have conflated two different issues here. > > > If you say so, then I'm happy to credit Harvey, Hart, Gladman, Moxham. > > > Bill. > > > 2009/2/15 David Harvey <dmhar...@cims.nyu.edu>: > > >> On Feb 15, 2:34 pm, Bill Hart <goodwillh...@googlemail.com> wrote: > >>> At some point we discussed where the original, original idea came > >>> from. At some point you read Granlund-Montgomery (after we had our > >>> discussion, I think) and at some point you may have decided that the > >>> idea was essentially already present in that work. > > >> I'm sorry Bill, I have no idea what you are talking about. Are you > >> talking about "division by invariant integers using > >> multiplication" (1994)? What does that paper have to do with this? > >> That would be rather odd, as GMP would have had this algorithm years > >> ago if Torbjorn had known about it. > > >> david --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-devel@googlegroups.com To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en -~----------~----~----~----~------~----~------~--~---
