On Sunday 15 February 2009 19:10:17 Bill Hart wrote: > The history of it is that I sent a copy of the correspondence you and > I had on this issue about 18 months ago to Brian and Jason. You asked > me if there was a fast way of doing this and I started blathering > about an algorithm. You turned it into one. > > With your permission I can post our email exchange on the subject to the > list. > > I don't know what Brian and Jason have done with the idea since, but > the timings seem pretty good. > > Certainly the idea to implement this came from both your Toom-3 branch > (I had forgotten what this branch was all about and thought it was > just the divexactby3 stuff) and the mention of the improvements on the > GMP list. > > Bill. > > 2009/2/15 David Harvey <dmhar...@cims.nyu.edu>: > > Is the algorithm based on the idea mentioned in Torbjorn's post from > > last year? > >
yes , that basically it I dont keep old emails , but i still have this //standard sub dst=dst-src mov (dst),ax sbb (src),ax mov ax,(dst) // standard submul dst=dst-cx*src mov 0(src),ax mov 0,t3 mul cx sub t1,-1(dst) adc ax,t2 adc dx,t3 // standard divexact by B-1 sbb (src),accum mov accum,(dst) So we get // new standard divexact by 3 8-macro-op where cx=(B-1)/3 mov 0(src),ax mov 0,t3 mul cx sub t1,accum mov accum,-1(dst) adc ax,t2 adc dx,t3 // this is clearly (src*cx)/(B-1) // src*(B-1)/3 = (dst)*(B-1) -ret*B^n and 0 <= ret < B-1 so ret=0 <=> 3|src Now this runs at about 2.8 to 3c/l , to get it to go faster we have to make some assumtions , which in a prevoius email I hinted at , and if anyone's still got it , then please post it to the list. jason > > http://gmplib.org/list-archives/gmp-devel/2008-August/000816.html > > > > david > > > > On Feb 15, 10:25 am, ja...@njkfrudils.plus.com wrote: > >> On Sunday 15 February 2009 14:13:23 David Harvey wrote: > >> > Hi, I'm curious to try this new divide-by-3 code, but I can't find it > >> > in the repo. Where do I look? How many c/l is it? > >> > > >> > david > >> > >> about 2.3c/l , I expect it could be tweeked some more > >> I never put it in the repo because I never got around to proving it. > >> I'll give it a look in the next few days. > >> > >> Brian did put a windows version in though, did you prove it ? > >> > >> Jason > >> > >> diveby3.asm > >> 1KViewDownload > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
