## RE: [Sdcc-user] need a very fast 18bit / 15bit div

 RE: [Sdcc-user] need a very fast 18bit / 15bit div From: - 2002-03-22 10:00:33 Attachments: =?iso-8859-1?Q?Michael_S=F6gtrop.vcf?= ```Dear Bernard, A 16/16->16 is a bit different from a 32/16->16 algorithm like the algorithm shown. I just forgot how the shifting in a 16/16->16 bit algorithm works (i did this about ten years ago). If i remember right, you start with a and b in the same position, and shift a left on the run, while successive digits of a or cancelled out. The add OR subtract is in general similar to the usual compare/subtract algorithm regarding shifting of the operands. You just replace the compare by the sign of a, and add instead of subtract, if a is negative. The algorithms are really the same, except that the subtract is just done without asking any questions, and if it was wrong to do so (a gets negative) the mess is fixed by adding instead of subtracting in the next cycle. E.g. if you make a wrong -2b in cycle 1, you fix this by making +b instead of -b in cycle 2. -2b+b=-b so this has the same effect as not doing the -2b in cycle 1 and doing the -b in cycle 2 as you should (if this is wrong again, you fix it in the same way in cycle 3 ...). Otherwise the algorithm is identical to any kind of compare/subtract algorithm. The only problem is, that you must keep track, if a is negative or not, while shifting a to the left. It should work to shift the top bit of a into the carry bit, and then use the carry bit for the descision, if a has become negative. I tried this, but i just cannot remember all the details of the shifting in 16/16->16 division. Could you send me PC C-code for the normal 16/16->16 algorithm. I am sure, i can convert this quickly to the sub or add algorithm Best regards, Michael > -----Original Message----- > From: Bernhard Held [mailto:bernhard@...] > Sent: Friday, March 22, 2002 10:12 AM > To: Michael Sogtrop; Sdcc-user@... > Subject: Re: [Sdcc-user] need a very fast 18bit / 15bit div > > > > there is one more option besides compare/subtract, subtract > and restore > > by copy, subtract and restore by add, and this is subtract > OR add. You > > make one add or subtract in every cycle and no restore or > compare. This > > algorithm looks like this: > > > > int udivtst(int a, int b) { > > int c,q=0 > > > > b<<=(nBitsQ-1); > > for(c=0; c > if(a<0) a+=b; > > else a-=b; > > q<<=1; > > q+=a>=0; > > b>>=1; > > } > > > > return q; > > } > > Sounds very interesting. But I stopped implementing a 16 / 16 > bit = 16 bit > division for SDCC at this line: > b<<=(nBitsQ-1); > This shifts my 16 bit divisor by 15 bits to the left. To > avoid loss of MSBs > I would have to implement 31 (or 32) bit variables and > operations (!) for b > and a. This would be very ineffective on a 8051. Is this > correct or am I > wrong? > > Bernhard > ```