Post by thread:divide by 3

jhobbs <.....PICLISTKILLspam@spam@MITVMA.MIT.EDU> wrote: > I once knew a fast trick for divide by 3, but now I am unable to > reproduce it. If someone can share it with me (and others) that > would be great. Jim: Here's a BASIC program to do a more-or-less correct division; it uses the fact that x/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64....: INPUT DIVIDEND QUOTIENT = 0 DIVIDE: DIVIDEND = INT(DIVIDEND/2): IF DIVIDEND = 0 THEN GOTO DONE QUOTIENT = QUOTIENT + DIVIDEND DIVIDEND = INT(DIVIDEND/2): IF DIVIDEND = 0 THEN GOTO DONE QUOTIENT = QUOTIENT - DIVIDEND GOTO DIVIDE DONE: PRINT QUOTIENT -Andy === Andrew Warren - fastfwdKILLspamix.netcom.com === Fast Forward Engineering - Vista, California === http://www.geocities.com/SiliconValley/2499

>>On 23 Feb, jhobbs wrote: >/I once knew a fast trick for divide by 3, but now I am unable to reproduce >>/it. If someone can share it with me (and others) that would be great. >>/ >>/Take care -Jim >> Simple. To multiply by 3, double and add to original. To divide by 3, >>just do the inverse! >>-- Mel Evans >Could someone unfold that for a binary math newbie, please? >/Morgan >/ Morgan Olsson, MORGANS REGLERTEKNIK, SE-277 35 KIVIK, Sweden \ \ >EraseMEmrtspam_OUTTakeThisOuTiname.com, ph: +46 (0)414 70741; fax +46 (0)414 70331 / Sure. Let's start with the number 5. In binary that is: 101 Since the place value of binary is two, you can double the number by shifting it left one bit, like this: Old: 101 New: 1010 Now you add it to the original number, like this 1010 + 101 ------ 1111 The result is the number 15, which is the answer to 5 * 3! Later, Eric

At 01:04 PM 2/26/98 -0800, you wrote: {Quote hidden}>>>On 23 Feb, jhobbs wrote: >>/I once knew a fast trick for divide by 3, but now I am unable to reproduce >>>/it. If someone can share it with me (and others) that would be great. >>>/ >>>/Take care -Jim > >>> Simple. To multiply by 3, double and add to original. To divide by 3, >>>just do the inverse! >>>-- Mel Evans > >>Could someone unfold that for a binary math newbie, please? >>/Morgan >>/ Morgan Olsson, MORGANS REGLERTEKNIK, SE-277 35 KIVIK, Sweden \ \ >>mrtspam_OUTiname.com, ph: +46 (0)414 70741; fax +46 (0)414 70331 / > >Sure. > >Let's start with the number 5. In binary that is: > > 101 > >Since the place value of binary is two, you can double the number by shifting it {Quote hidden}>left one bit, like this: > >Old: 101 >New: 1010 > >Now you add it to the original number, like this > > > 1010 > + 101 > ------ > 1111 > >The result is the number 15, which is the answer to 5 * 3! > > >Later, > >Eric > Yeah, fine for multiplication, but that neat relationship doesn't hold for division, at least as far as I can see. Take 10/3 for example: 10 shifted down one is 5 now, what can you do to 5 to get 3.3333? It seems to me that Andy Warren had the best solution, do a series of divisions by powers of two until you get the accuracy you need. Sean +--------------------------------+ | Sean Breheny | | Amateur Radio Callsign: KA3YXM | | Electrical Engineering Student | +--------------------------------+ Fight injustice, please look at http://homepages.enterprise.net/toolan/joanandrews/ Personal page: http://www.people.cornell.edu/pages/shb7 @spam@shb7KILLspamcornell.edu Phone(USA): (607) 253-0315

At 01:04 PM 2/26/98 -0800, you wrote: >>>On 23 Feb, jhobbs wrote: >>/I once knew a fast trick for divide by 3, but now I am unable to reproduce >>>/it. If someone can share it with me (and others) that would be great. >>>/ >>>/Take care -Jim > >Let's start with the number 5. In binary that is: > > 101 > >Since the place value of binary is two, you can double the number by shifting it {Quote hidden}>left one bit, like this: > >Old: 101 >New: 1010 > >Now you add it to the original number, like this > > > 1010 > + 101 > ------ > 1111 > >The result is the number 15, which is the answer to 5 * 3! > No kidding. I think the point of the question is how do you DIVIDE by 3 easily. The simple trick above is not applicable. The infinite sum solution posted earlier seems like a useful method, since it only involves dividing by two successively. Dan

Great, but I think the question really referred to the bit about "just do the inverse". This doesn't make sense to me. The original multiplication is the easy part. Martin. On Thu, 26 Feb 1998 13:04:09 -0800, ERIC SCHLAEPFER <KILLspameric.schlaepferKILLspamAUTODESK.COM> wrote: {Quote hidden}>>>On 23 Feb, jhobbs wrote: >>/I once knew a fast trick for divide by 3, but now I am unable to reproduce >>>/it. If someone can share it with me (and others) that would be great. >>>/ >>>/Take care -Jim > >>> Simple. To multiply by 3, double and add to original. To divide by 3, >>>just do the inverse! >>>-- Mel Evans > >>Could someone unfold that for a binary math newbie, please? >>/Morgan >>/ Morgan Olsson, MORGANS REGLERTEKNIK, SE-277 35 KIVIK, Sweden \ \ >>RemoveMEmrtTakeThisOuTiname.com, ph: +46 (0)414 70741; fax +46 (0)414 70331 / > >Sure. > >Let's start with the number 5. In binary that is: > > 101 > >Since the place value of binary is two, you can double the number by shifting it >left one bit, like this: > >Old: 101 >New: 1010 > >Now you add it to the original number, like this > > > 1010 > + 101 > ------ > 1111 > >The result is the number 15, which is the answer to 5 * 3! > > >Later, > >Eric > Martin R. Green spamBeGoneelimarspamBeGoneNOSPAMbigfoot.com To reply, remove the NOSPAM from the return address. Stamp out SPAM everywhere!!!

> The infinite sum solution posted earlier seems like a useful method, since > it only involves dividing by two successively. I haven't seen anyone mention repeated subtraction. A loop that subtracts 3 each time and counts how many times before the result is less than zero. Not efficient or elegant, but simple. Steve. ====================================================== Very funny Scotty. Now beam down my clothes. ====================================================== Steve Baldwin Electronic Product Design TLA Microsystems Ltd Microcontroller Specialists PO Box 15-680 email: TakeThisOuTstevebEraseMEspam_OUTkcbbs.gen.nz New Lynn, Auckland ph +64 9 820-2221 New Zealand fax +64 9 820-1929 ======================================================

Hello, Oops! I misunderstood the question. :-( Sorry about that. I think I have a book at home describing a neat answer to the division thing. I'll post back when I get it. Later, Eric ______________________________ Reply Separator _________________________________ Subject: Re: divide by 3 Author: "Martin R. Green" <RemoveMEelimarTakeThisOuTNOSPAMBIGFOOT.COM> at INTERNET Date: 2/26/98 9:50 PM Great, but I think the question really referred to the bit about "just do the inverse". This doesn't make sense to me. The original multiplication is the easy part. Martin. On Thu, 26 Feb 1998 13:04:09 -0800, ERIC SCHLAEPFER <eric.schlaepferEraseME.....AUTODESK.COM> wrote: {Quote hidden}>>>On 23 Feb, jhobbs wrote: >>/I once knew a fast trick for divide by 3, but now I am unable to reproduce >>>/it. If someone can share it with me (and others) that would be great. >>>/ >>>/Take care -Jim > >>> Simple. To multiply by 3, double and add to original. To divide by 3, >>>just do the inverse! >>>-- Mel Evans > >>Could someone unfold that for a binary math newbie, please? >>/Morgan >>/ Morgan Olsson, MORGANS REGLERTEKNIK, SE-277 35 KIVIK, Sweden \ \ >>EraseMEmrtiname.com, ph: +46 (0)414 70741; fax +46 (0)414 70331 / > >Sure. > >Let's start with the number 5. In binary that is: > > 101 > >Since the place value of binary is two, you can double the number by shifting it {Quote hidden}>left one bit, like this: > >Old: 101 >New: 1010 > >Now you add it to the original number, like this > > > 1010 > + 101 > ------ > 1111 > >The result is the number 15, which is the answer to 5 * 3! > > >Later, > >Eric > Martin R. Green RemoveMEelimarEraseMEEraseMENOSPAMbigfoot.com To reply, remove the NOSPAM from the return address. Stamp out SPAM everywhere!!!

Multiplication is quick addition. x + x + x = 3x and 2 * x + x = 3x Implemented in a PIC is very fast since it is a shift left (this is the binary part which doubles the number) and then add the original value. Dividing by 3 isn't as straight forward as suggested since the "original" value to subtract isn't known. Rich At 08:53 PM 2/26/98 +0100, you wrote: {Quote hidden}>>On 23 Feb, jhobbs wrote: >/I once knew a fast trick for divide by 3, but now I am unable to reproduce >>/it. If someone can share it with me (and others) that would be great. >>/ >>/Take care -Jim > >> Simple. To multiply by 3, double and add to original. To divide by 3, >>just do the inverse! >>-- Mel Evans > >Could someone unfold that for a binary math newbie, please? >/Morgan >/ Morgan Olsson, MORGANS REGLERTEKNIK, SE-277 35 KIVIK, Sweden \ >\ RemoveMEmrtspam_OUTKILLspaminame.com, ph: +46 (0)414 70741; fax +46 (0)414 70331 / > > ========================================= = Abolish the Income Tax! Fire the IRS! = = http://www.nrst.org/ = =========================================

Try, instead of division, doing an 8 bit by 8 bit -> 16 bit multiplication. X*Y=Z let X=your number. let Y=256/3 (85 decimal truncated) Now multiply X*Y to get 16 bit Z. The high order byte of Z now contains the integer portion of your result, and the low order byte contains the remainder (X MOD Y if you will) The fractional remainder has denominator of 256 so if you want rounding, simply add 128 to the 16 bit result, throw away low order byte and use high order byte as your number. (This is equivalent to adding .5 and truncating in decimal.) I just coded it up quick'n'ugly to consume 18 words of program memory using 608 cycles (both numbers including setup) Since it's now stock multiplication however, use your favorite 8*8->16 routine to optimize program memory, execution speed, etc. etc. Brian {Original Message removed}

Yeah subtract your answer and then devide by two to get your answer >:) Peter -----Original Message----- From: Mel Evans <RemoveMEMEvans1027TakeThisOuTspamAOL.COM> To: EraseMEPICLISTspamspamBeGoneMITVMA.MIT.EDU <RemoveMEPICLISTKILLspamMITVMA.MIT.EDU> Date: Thursday, February 26, 1998 12:47 PM Subject: Re: divide by 3 {Quote hidden}>On 23 Feb, jhobbs wrote: > >/Date: Mon, 23 Feb 1998 15:08:04 -0000 >/From: jhobbs <jhobbsSTOPspamspam_OUTQUIKNET.COM> >/Subject: divide by 3 >/ >/I once knew a fast trick for divide by 3, but now I am unable to reproduce >/it. If someone can share it with me (and others) that would be great. >/ >/Take care -Jim > >Jim -- > Simple. To multiply by 3, double and add to original. To divide by 3, >just do the inverse! >-- Mel Evans >

> Try, instead of division, doing an 8 bit by 8 bit -> 16 bit multiplication. > X*Y=Z > let X=your number. > let Y=256/3 (85 decimal truncated) > Now multiply X*Y to get 16 bit Z. > The high order byte of Z now contains the integer portion of your result, > and the low order byte contains the remainder (X MOD Y if you will) > The fractional remainder has denominator of 256 so if you want rounding, > simply add 128 to the 16 bit result, throw away low order byte and use high > order byte as your number. (This is equivalent to adding .5 and truncating > in decimal.) I do similar all the time for divide... multiply (16x16) by 65536/divisor and discard the lower 16 bits of the result. (Roundup is a matter of testing the highest of the discarded bits and incrementing the high 16 bits if it is set.) It is interesting to note that in the case of divide by 3, the multiplier in hex is 55 (8 bit), 5555 (16 bit) etc. The multiply in this case can be reduced to n shifts and n/2 adds where n is the number of bits of resolution you want. Roundup can be achieved by multiplying by ...56 rather than ...55 or by the above method. Multiplying by ...6 would be better for a generic multiply, by ...5 if you program a loop to do shift, shift, add. It's also possible to make a little state machine (3 states) to walk the dividend highest bit downwards, outputing one bit each time. You can get as many bits of result as you like this way! I figure about 8 instruction cycles plus a shift per bit of result this way. (The cost of the shift would depend on how many bits of result you want.) Orin.

Brian Schousek wrote: {Quote hidden}> > Try, instead of division, doing an 8 bit by 8 bit -> 16 bit multiplication. > X*Y=Z > > let X=your number. > let Y=256/3 (85 decimal truncated) > Now multiply X*Y to get 16 bit Z. > The high order byte of Z now contains the integer portion of your result, > and the low order byte contains the remainder (X MOD Y if you will) > The fractional remainder has denominator of 256 so if you want rounding, > simply add 128 to the 16 bit result, throw away low order byte and use high > order byte as your number. (This is equivalent to adding .5 and truncating > in decimal.) > > I just coded it up quick'n'ugly to consume 18 words of program memory using > 608 cycles (both numbers including setup) Since it's now stock > multiplication however, use your favorite 8*8->16 routine to optimize > program memory, execution speed, etc. etc. > > Brian This is the method I prefer too. However, there are a couple of observations that can reduce the speed from 608 cycles to just 21. First, observe the binary pattern of 256/3: 256/3 = 85.3333 = 0101 0101 . 0101 0101 0101 ... This repeating 0101 pattern means that it is possibly to multiply the dividend by 5 and then add shifted copies together. Shifting by 4 is particularly easy because of the SWAPF instruction. The routine shown below does something like this: unsigned char divide_by_3(unsigned char dividend) { unsigned int x; if(255 == dividend) return (0x55); x = 5*dividend; return( (x + (x>>4))>>4); } divide_by_3: ;Divide by 3 ; 'dividend' is the input ; result is returned in W MOVLW 1 ;255 is a special case ADDWF dividend,F SKPNC RETLW 0x55 CLRF quo_L ; RRF dividend,W ;(C=0) MOVWF quo_H RRF quo_L,F ;quo_H:L = dividend/2 RRF quo_H,W RRF quo_L,F ;quo_H:L = dividend/4 ADDWF dividend,W ; MOVWF quo_H RRF quo_H,F RRF quo_L,F ;quo_H:L = 5*dividend/8 ; note quo_L LSN is zero SWAPF quo_H,W ;divide quo_H by 16 ADDWF quo_L,F ;add upper nibble to quo_L. We ; really are only interested in the carry ANDLW 0x0f ;Remove upper nibble (was lower nibble of quo_H) SKPNC ; ADDLW 1 ;Add in carry from quo_L addition ADDWF quo_H,F ;quo_H = dividend *0x55 / 0x80 RRF quo_H,W ;W = dividend * 0x55 / 0x100 The C hack is untested, the PIC one IS tested (and works if I did the test correctly...). I bet though, it's possible to reduce the execution time even more. Anyone care to waste a little time? Scott

Andy Warren provided the following.... > ----------------------------------------------------------------- > >Here's a BASIC program to do a more-or-less correct division; it >uses the fact that x/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64....: > > basic program snipped > You can do this twice as fast (8 bit precision) Using... 1/3 = 1/4 + 1/16 + 1/64 + 1/256... Also no subtraction is required, Also it is interesting to note that 64+16+4+1 = 85, which is Brian Schousek's solution X*85/256. Ray Gardiner (DSP Systems) spamBeGoneraySTOPspamEraseMEdsp-systems.com http://www.dsp-systems.com private email to:- KILLspamrayspamBeGonenetspace.net.au

Ray Gardiner <EraseMEPICLISTEraseMEMITVMA.MIT.EDU> wrote: > Andy Warren provided the following.... > > ----------------------------------------------------------------- > > > >Here's a BASIC program to do a more-or-less correct division; it > >uses the fact that x/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64....: > > > > basic program snipped > > > > You can do this twice as fast (8 bit precision) Using... > > 1/3 = 1/4 + 1/16 + 1/64 + 1/256... Ray: If you try that method, I think you'll find that the rounding errors are too large to give acceptable results. -Andy === Andrew Warren - @spam@fastfwd@spam@spam_OUTix.netcom.com === Fast Forward Engineering - Vista, California === http://www.geocities.com/SiliconValley/2499

{Quote hidden}>Ray Gardiner <spamBeGonePICLISTKILLspamMITVMA.MIT.EDU> wrote: > >> Andy Warren provided the following.... >> > ----------------------------------------------------------------- >> > >> >Here's a BASIC program to do a more-or-less correct division; it >> >uses the fact that x/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64....: >> > >> > basic program snipped >> > >> >> You can do this twice as fast (8 bit precision) Using... >> >> 1/3 = 1/4 + 1/16 + 1/64 + 1/256... > > >Ray: > >If you try that method, I think you'll find that the rounding errors >are too large to give acceptable results. > >-Andy > Actually, the rounding errors are the same in both cases. I derived the algorithm by simplifying yours, as follows. x/2 - x/4 = x/4 x/8 - x/16 = x/16 x/32 - x/64 = x/64 x/128 - x/256 = x/256 So both algorithms are computationally equivalent. Except the simplified version is twice as fast. The algorithm can also be derived from Brian Schousek's solution X*85/256 by observing that 85 is 64+16+4+1, I should have explained further. If the first step is to multiply by 85 then divide by 256 then.. X*85 = X*64 + X*16 + X*4 + X*1 Now divide by 256 X*64/256 + X*16/256 + X*4/256 + X*1/256 Which of course gives.. X/4 + X/16 + X/64 + X/256 The rounding error will be X ( 1/3 - 85/256) or X*0.0013 which is about 0.3 of a bit in the worst case. Ray Gardiner (DSP Systems) .....rayspam_OUTdsp-systems.com http://www.dsp-systems.com private email to:- TakeThisOuTray.....TakeThisOuTnetspace.net.au

Mel Evans <TakeThisOuTMEvans1027KILLspamspamAOL.COM> jokingly wrote: > To multiply by 3, double and add to original. To divide by 3, > just do the inverse! and Peter van Hoof <.....PICLISTRemoveMEMITVMA.MIT.EDU> thought HE was joking, too, when he wrote: > Yeah subtract your answer and then devide by two to get your answer > >:) Actually, Peter, you CAN do it that way... It looks something like this: To find N/3: 1. Make an initial guess at the answer and call it Q. 2. Do just as you said... Subtract Q from N, then divide the result by two. If the result of that division is Q, you're done; Q = N/3. 3. Otherwise, you need to adjust Q; if the result of the division-by-2 was SMALLER than Q, Q = Q - Q/2. If the result was LARGER than Q, Q = Q + Q/2. 4. Loop back to Step 2. Note that, if your initial guess is N/2, this algorithm performs exactly the same steps as the one I posted earlier; it computes Q = N/2 - N/4 + N/8 - N/16 + N/32 - N/64.... etc. If you start with Q = 2^x, where x = log2(N) (i.e., x = the number of bits necessary to express N), the algorithm just steps through Q from MSB to LSB, setting or clearing each bit appropriately... In other words, it's guaranteed to terminate within x iterations. -Andy P.S. Since we're doing integer math, you probably need to add one more test to Step 2... Make it: "If the result of the division is Q, OR IF Q = 1, you're done." === Andrew Warren - RemoveMEfastfwdspamBeGoneix.netcom.com === Fast Forward Engineering - Vista, California === http://www.geocities.com/SiliconValley/2499

Ray Gardiner <spamBeGonePICLIST@spam@spam_OUTMITVMA.MIT.EDU> wrote: > Actually, the rounding errors are the same in both cases. I derived > the algorithm by simplifying yours, as follows. > > x/2 - x/4 = x/4 > x/8 - x/16 = x/16 > x/32 - x/64 = x/64 > x/128 - x/256 = x/256 Ray: It doesn't work that way. With integer division, x/2 - x/4 is NOT necessarily equal to x/4. An example: X = 15. My method computes X/2 - X/4 = 15/2 - 15/4 = 7 - 3 = 4. Your method computes X/4 = 3. Note that 4 is not equal to 3. -Andy === Andrew Warren - TakeThisOuTfastfwdspamix.netcom.com === Fast Forward Engineering - Vista, California === http://www.geocities.com/SiliconValley/2499

part 0 2694 bytes content-type:TEXT/PLAIN; charset=US-ASCII; name="div3.c" Alg1 Alg2 ========= ====== ====== 255 / 3 = 85 (0) 81 (-4) 254 / 3 = 85 (1) 81 (-3) 253 / 3 = 84 (0) 81 (-3) 252 / 3 = 84 (0) 81 (-3) 251 / 3 = 84 (1) 80 (-3) 250 / 3 = 84 (1) 80 (-3) 249 / 3 = 83 (0) 80 (-3) 248 / 3 = 83 (1) 80 (-2) 247 / 3 = 82 (0) 79 (-3) 246 / 3 = 82 (0) 79 (-3) 245 / 3 = 81 (0) 79 (-2) 244 / 3 = 81 (0) 79 (-2) 243 / 3 = 81 (0) 78 (-3) 242 / 3 = 81 (1) 78 (-2) 241 / 3 = 80 (0) 78 (-2) 240 / 3 = 80 (0) 78 (-2) 239 / 3 = 80 (1) 76 (-3) The Alg1 column is using add and sub, while the Alg2 column uses only add. ( The source for this program is attached). Matt On Fri, 27 Feb 1998, Andrew Warren wrote: {Quote hidden}> Ray Gardiner <PICLISTEraseMEMITVMA.MIT.EDU> wrote: > > > Actually, the rounding errors are the same in both cases. I derived > > the algorithm by simplifying yours, as follows. > > > > x/2 - x/4 = x/4 > > x/8 - x/16 = x/16 > > x/32 - x/64 = x/64 > > x/128 - x/256 = x/256 > > Ray: > > It doesn't work that way. With integer division, x/2 - x/4 is NOT > necessarily equal to x/4. > > An example: > > X = 15. > > My method computes X/2 - X/4 = 15/2 - 15/4 > = 7 - 3 > = 4. > > Your method computes X/4 = 3. > > Note that 4 is not equal to 3. > > -Andy > > === Andrew Warren - RemoveMEfastfwdEraseMEspam_OUTix.netcom.com > === Fast Forward Engineering - Vista, California > === http://www.geocities.com/SiliconValley/2499 > /*****************************************/ /* Matt Calder, Dept. of Statistics, CSU */ /* http://www.stat.colostate.edu/~calder */ /*****************************************/ Content-Type: TEXT/PLAIN; charset=US-ASCII; name="div3.c" Content-ID: <@spam@Pine.SUN.3.96.980227095513.27526BRemoveMEEraseMEtlaloc.stat.colostate.edu>> Content-Description: Source to generate full table #include <stdio.h> #include <stdlib.h> #include <math.h> int main() { int p, d1, d2, c; for (p=0; p < 100; p++) { d1 = (p >> 1) - (p >> 2) + (p >> 3) - (p >> 4) + (p >> 5) - (p >> 6) + (p >> 7) - (p >> 8); d2 = (p >> 2) + (p >> 4) + (p >> 6) + (p >> 8); c = floor(((double) p)/3.0 + 0.5); printf("%d / 3 \t= %d\t%d \t(%d) \t%d \t(%d)\n", p, c, d1, d1-c, d2, d2-c); } }

On Fri, 27 Feb 1998, Ray Gardiner wrote: > [... lots of stuff snipped ...] > >> > ----------------------------------------------------------------- > >> > > >> >Here's a BASIC program to do a more-or-less correct division; it > >> >uses the fact that x/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64....: > >> > [...] > >> You can do this twice as fast (8 bit precision) Using... > >> 1/3 = 1/4 + 1/16 + 1/64 + 1/256... > > > >If you try that method, I think you'll find that the rounding errors > >are too large to give acceptable results. > > Actually, the rounding errors are the same in both cases. I derived They are not the same. > the algorithm by simplifying yours, as follows. > > x/2 - x/4 = x/4 We are dealing here with INTEGER division. "Integer division" differs from what "division" usually means in a number of fundamental ways. (Such as reversibility) In terms of what division usually means (a integerdivide b) is really (a-(a mod b))/a so (x integerdivide 2) - ( x integerdivide 4) is really (x - (x mod 2))/2 - (x - (x mod 4))/4 Which can be simplified a bit to something like (x - 2*(x mod 2) + (x mod 4)) / 4 But does *NOT* reduce to x/4 at all. > [...] > So both algorithms are computationally equivalent. Except the > simplified version is twice as fast. And wrong. > [...] There are any number of good books on "Computer Arithmetic" availiable that discuss the details of machine computation. (They usually give more space to the properties of Floating point numbers, but they usually cover Integer numbers also.) I'm afraid it's been too many years since I did that, so I can't recomend any specific book.

Gotta go with Halleck on this one. -----Original Message----- From: John Halleck [SMTP:EraseMEJohn.Halleck@spam@CC.UTAH.EDU] Sent: Friday, February 27, 1998 12:23 PM To: @spam@PICLISTspam_OUT.....MITVMA.MIT.EDU Subject: Re: divide by 3 > [... lots of stuff snipped ...] > So both algorithms are computationally equivalent. Except the > simplified version is twice as fast. And wrong. > [...] There are any number of good books on "Computer Arithmetic" availiable that discuss the details of machine computation. (They usually give more space to the properties of Floating point numbers, but they usually cover Integer numbers also.) I'm afraid it's been too many years since I did that, so I can't recomend any specific book. Attachment converted: wonderland:WINMAIL.DAT 5 (????/----) (000137EE)

{Quote hidden}>> Actually, the rounding errors are the same in both cases. I derived >> the algorithm by simplifying yours, as follows. >> >> x/2 - x/4 = x/4 >> x/8 - x/16 = x/16 >> x/32 - x/64 = x/64 >> x/128 - x/256 = x/256 > >Ray: > >It doesn't work that way. With integer division, x/2 - x/4 is NOT >necessarily equal to x/4. > >An example: > > X = 15. > > My method computes X/2 - X/4 = 15/2 - 15/4 > = 7 - 3 > = 4. > > Your method computes X/4 = 3. > > Note that 4 is not equal to 3. > I stand corrected, to use the simplified version you need to keep the remainders of each division so that you can round the result correctly. If I re-write as follows.... X/3 = (X*256/4 + X*256/16 + X*256/64 + X*256/256 +128 )/256 which becomes... X/3 = (X*64 + X*16 + X*4 + X + 128)/256 I think the rounding errors become minimal. (not proven) The interesting point (which I missed completely!) was that with your method the rounding errors tend to cancel. Ray Gardiner (DSP Systems) .....ray@spam@EraseMEdsp-systems.com http://www.dsp-systems.com private email to:- .....rayRemoveMEnetspace.net.au

sssss Ray Gardiner wrote: {Quote hidden}> > >> Actually, the rounding errors are the same in both cases. I derived > >> the algorithm by simplifying yours, as follows. > >> > >> x/2 - x/4 = x/4 > >> x/8 - x/16 = x/16 > >> x/32 - x/64 = x/64 > >> x/128 - x/256 = x/256 > > > >Ray: > > > >It doesn't work that way. With integer division, x/2 - x/4 is NOT > >necessarily equal to x/4. > > > >An example: > > > > X = 15. > > > > My method computes X/2 - X/4 = 15/2 - 15/4 > > = 7 - 3 > > = 4. > > > > Your method computes X/4 = 3. > > > > Note that 4 is not equal to 3. > > > > I stand corrected, to use the simplified version you need to > keep the remainders of each division so that you can round > the result correctly. If I re-write as follows.... > > X/3 = (X*256/4 + X*256/16 + X*256/64 + X*256/256 +128 )/256 > > which becomes... > > X/3 = (X*64 + X*16 + X*4 + X + 128)/256 > > I think the rounding errors become minimal. (not proven) > > The interesting point (which I missed completely!) was that > with your method the rounding errors tend to cancel. > > Ray Gardiner (DSP Systems) .....raySTOPspam@spam@dsp-systems.com http://www.dsp-systems.com > private email to:- rayEraseME@spam@netspace.net.au

Now *there's* a man who knows his maths! Ray Gardiner wrote: {Quote hidden}> I stand corrected, to use the simplified version you need to > keep the remainders of each division so that you can round > the result correctly. If I re-write as follows.... > X/3 = (X*256/4 + X*256/16 + X*256/64 + X*256/256 +128 )/256 > which becomes... > X/3 = (X*64 + X*16 + X*4 + X + 128)/256 > I think the rounding errors become minimal. (not proven) But I can see why they *do*. Common sense. We've been through this *all* before in the thread on basic digital filtering. Remember? > The interesting point (which I missed completely!) was that > with your method the rounding errors tend to cancel. Sheer accident as it happens! The rule is you only *ever*, *ever* drop the precision (by right- shifting to free space) when you don't want it, usually at the point of output (display). Accumulators *must* hold all intermediate precision. I just read (killed) a posting on another list talking of 16-bit DSP processors with 32-bit intermediate tally processing. Cheers, Paul B.

> >which becomes... > > X/3 = (X*64 + X*16 + X*4 + X + 128)/256 > A few steps further. X/3 = ( X + 4X + 16X + 64X)/256 X/3 = ((X + 4X) + 16(X + 4X))/256 X/3 = ( 5X + 16(5X))/256 Here is the code for the above algorithm. No doubt someone can find a few ways to cut a cycle or two. Currently 22 cycles including rounding etc. 20 cycles if you can accept truncation rather than rounding. DIV3 ; Call with 8bit in Xl , exit with X/3 in W ; ; RAM: uses T and Xh:Xl ; CLRF Xh RLF Xl,F RLF Xh,F ; X*2 RLF Xl,F ; RLF Xh,F ; X*4 ADDWF Xl,F SKPNC INCF Xh,F ; 5*X ; X = 0J:KL SWAPF Xh,W ; W = J0 MOVWF T ; T = J0 SWAPF Xl,W ; W = LK ANDLW 0x0F ; W = 0K ADDWF T,F ; T = JK ; SWAPF Xl,W ; W = LK ANDLW 0xF0 ; W = L0 ** needed? ADDWF Xl,F ; MOVF Xh,W ; SKPNC ; ADDLW 1 ; ADDWF T,W ; BTFSC Xl,7 ; Round up if >128 ADDLW 1 ; ; result in W Ray Gardiner, Shepparton, Victoria, Australia RemoveMErayspamBeGonenetspace.net.au

At 03:08 PM 2/23/98 -0000, jhobbs wrote: >I once knew a fast trick for divide by 3, but now I am unable to reproduce >it. If someone can share it with me (and others) that would be great. > >Take care -Jim I'm not sure how much this will help, but.... 1/3 = 1/2 - 1/4 + 1/8 - 1/16 + 1/32 - 1/64 + 1/128 .... etc. Since all the divisions can be done with simple shifts, there should be a reasonable method in here, somewhere... - Rick "Infinite series ya us" Dickinson +---------------------------------+---------------------------+ | Enterprise ArchiTechs Company |"You can't reason someone | | Lotus Certified Notes | out of a position they | | Appl. Design & Administration | didn't reason themselves | |(818)563-1061 spamBeGonertdKILLspam@spam@notesguy.com | into" -- Rick Adams, | | http://www.eArchiTechs.com | in alt.folklore.urban | +---------------------------------+---------------------------+

At 10:57 AM 2/26/98 EST, Mel Evans wrote: >On 23 Feb, jhobbs wrote: > >/Date: Mon, 23 Feb 1998 15:08:04 -0000 >/From: jhobbs <jhobbsspam_OUT@spam@QUIKNET.COM> >/Subject: divide by 3 >/ >/I once knew a fast trick for divide by 3, but now I am unable to reproduce >/it. If someone can share it with me (and others) that would be great. >/ >/Take care -Jim > >Jim -- > Simple. To multiply by 3, double and add to original. To divide by 3, >just do the inverse! >-- Mel Evans > ROTFLMAO! Excellent! Best joke I've heard in a while! - Rick "Math geek" Dickinson +---------------------------------+---------------------------+ | Enterprise ArchiTechs Company |"You can't reason someone | | Lotus Certified Notes | out of a position they | | Appl. Design & Administration | didn't reason themselves | |(818)563-1061 spamBeGonertd@spam@notesguy.com | into" -- Rick Adams, | | http://www.eArchiTechs.com | in alt.folklore.urban | +---------------------------------+---------------------------+

At 09:50 PM 2/26/98 GMT, Martin R. Green wrote: >Great, but I think the question really referred to the bit about "just >do the inverse". This doesn't make sense to me. The original >multiplication is the easy part. Regarding confusion over the original suggestion: >>Simple. To multiply by 3, double and add to original. To divide by 3, >>just do the inverse! So let's see... double and add to multiply by three, so the inverse is just subtract and divide by two.... Okay.... let's do six. 6-2=4, 4/2 = 2. Wow, it works! Now, to divide n by three, I just need to figure out a quick way to calculate the number to subtract from n, which is n/3..... - Rick "Math is hard" Dickinson +---------------------------------+---------------------------+ | Enterprise ArchiTechs Company |"You can't reason someone | | Lotus Certified Notes | out of a position they | | Appl. Design & Administration | didn't reason themselves | |(818)563-1061 RemoveMErtdEraseMEKILLspamnotesguy.com | into" -- Rick Adams, | | http://www.eArchiTechs.com | in alt.folklore.urban | +---------------------------------+---------------------------+

Hi Everyone, I finally got around to looking it up. The book I have uses this method: Where x is the number to divide by 3 (In C) result = (x >> 2) + (x >> 4) + (x >> 6) + (x >> 8) Problem with this method is that the result is always too small. It would work better if you converted the source number to fixed point, and the result of the division could be rounded somehow, and converted back to an integer. Of course, we are dealing with a PIC that only works with 8 bits at a time. Later, Eric P.S. I got this method out of a game programming book, which is why it is meant for 32-bit integers. ______________________________ Reply Separator _________________________________ Subject: Re: divide by 3 Author: Peter van Hoof <spamBeGonepvhspam_OUTRemoveMEmicroserve.net> at INTERNET Date: 2/28/98 9:02 AM SO! use the fast method BUT start with shifting left a number of times and shift back afterwards , always the easiest way to reduce rounding errors in integer calculations Peter {Original Message removed}

Here's a divide-by-3 routine that my son Paul (.....fmdesignpeRemoveMEaol.com) reminded me of when I admitted I couldn't remember. It's not fast, but is real simple to understand, and can easily be generalized to divide by any integer. Number (unsigned byte) to divide in X. Scratch files L (little) and B (big), both initialized to 0. Loop add 3 to B is B greater than X ? if so: we're done, with answer in L if not: add 1 to L and go to Loop We're filling B three times as fast as we are L, so when B exceeds X, L is one third of X. Here's the code: btst movlw 3 addwf B,F ;add 3 to B movf B,W subwf X,W ;compare B to X btfss STATUS,C ;if Carry set, B <= X, so increment L and loop goto done ;if not, we're done incf L,F ;add 1 to L goto btst ; and loop again done ;result is in L Works with any divisor. To divide by 13, just change the first instruction to "movlw 13". -- Mel Evans mevans1027@spam@aol.com 813/595-7685

At 05:30 AM 3/6/98 -0500, Walter Banks wrote: >At least for the 16bit core with multiply the quickest divide by 3 >is to multiply by 0x55 and use the MS byte and add 1 if the LS byte >is greater than 7F. > >This is ((256 / 3) / 256) > >Walter Banks Since 0x55 is %01010101 in binary, try the following algorithm: A is a 16-bit register N is the 8-bit initial value, padded to 16 bits by adding a zero MSByte Shift N left 1 bit Put N in A Shift N left 2 bits Add N to A Shift N left 2 bits Add N to A Shift N left 2 bits Add N to A Answer is now in high byte of A. - Rick "What's the fastest PIC implementation?" Dickinson +---------------------------------+---------------------------+ | Enterprise ArchiTechs Company |"You can't reason someone | | Lotus Certified Notes | out of a position they | | Appl. Design & Administration | didn't reason themselves | |(818)563-1061 EraseMErtdRemoveMESTOPspamnotesguy.com | into" -- Rick Adams, | | http://www.eArchiTechs.com | in alt.folklore.urban | +---------------------------------+---------------------------+

<snip> > >Since 0x55 is %01010101 in binary, try the following algorithm: > <snip> Hi Rick, It seems an infinite series of algorithms converges. :-) This is about where we got to a week ago. Maybe you missed it. It was probably buried under bovine something or other. All methods posted so far converge on the multiply by 85 method. Here is the code that Scott Dattalo posted, very fast and clean. ------<cut>----------- ;Divide by 3 ; 'dividend' is the input ; result is returned in W MOVLW 1 ;255 is a special case ADDWF dividend,F SKPNC RETLW 0x55 CLRF quo_L ; RRF dividend,W ;(C=0) MOVWF quo_H RRF quo_L,F ;quo_H:L = dividend/2 RRF quo_H,W RRF quo_L,F ;quo_H:L = dividend/4 ADDWF dividend,W ; MOVWF quo_H RRF quo_H,F RRF quo_L,F ;quo_H:L = 5*dividend/8 ; note quo_L LSN is zero SWAPF quo_H,W ;divide quo_H by 16 ADDWF quo_L,F ;add upper nibble to quo_L. We ; really are only interested in the carry ANDLW 0x0f ;Remove upper nibble (was lower nibble of quo_H) SKPNC ; ADDLW 1 ;Add in carry from quo_L addition ADDWF quo_H,F ;quo_H = dividend *0x55 / 0x80 RRF quo_H,W ;W = dividend * 0x55 / 0x100 ------<cut>----------- Here is one method I posted, slightly slower than Scott Dattalo's but closer to your algorithm. Still the same basic method. Arrived at by going the long way round. ------<cut>----------- Here is the code for the above algorithm. No doubt someone can find a few ways to cut a cycle or two. Currently 23 cycles including rounding etc. 21 cycles if you can accept truncation rather than rounding. DIV3 ; Call with 8bit in W , exit with X/3 in W ; ; RAM: uses T and Xh:Xl ; MOVWF Xl ; CLRF Xh ; RLF Xl,F RLF Xh,F ; X*2 RLF Xl,F ; RLF Xh,F ; X*4 ADDWF Xl,F SKPNC INCF Xh,F ; 5*X ; X = 0J:KL SWAPF Xh,W ; W = J0 MOVWF T ; T = J0 SWAPF Xl,W ; W = LK ANDLW 0x0F ; W = 0K ADDWF T,F ; T = JK ; SWAPF Xl,W ; W = LK ANDLW 0xF0 ; W = L0 ** needed? ADDWF Xl,F ; MOVF Xh,W ; SKPNC ; ADDLW 1 ; ADDWF T,W ; BTFSC Xl,7 ; Round up if >128 ADDLW 1 ; ; result in W ------<cut>----------- Ray Gardiner (DSP Systems) RemoveMErayKILLspamTakeThisOuTdsp-systems.com http://www.dsp-systems.com private email to:- spamBeGoneray@spam@netspace.net.au

> Here is the code that Scott Dattalo posted, very fast and clean. <snip> And here is the code Ray posted... > DIV3 > ; Call with 8bit in W , exit with X/3 in W > ; > ; RAM: uses T and Xh:Xl > ; <snip> Here's another routine that does the job just ever so slightly faster. (And it's been tested). It takes advantage of the often forgotten Digit Carry flag. ; Divide by 3 ; Input in W , Output W/3 ; ADDLW 1 SKPNC RETLW 0x55 MOVWF quo_L CLRF quo_H RLF quo_L,F RLF quo_H,F RLF quo_L,F RLF quo_H,F ;quo_L:H = 4*dividend ADDWF quo_L,F SKPNC INCF quo_H,F ;quo_L:H = 5*dividend ;At this point, we have dividend * 5. We actually need ;dividend * 0x55. So the next instructions will add ;add 0x10*quo_L:H to quo_L:H. SWAPF quo_H,W ;quo_H * 0x10 ADDWF quo_H,F ;quo_H += quo_H*0x10 SWAPF quo_L,W ;quo_L * 0x10 ANDLW 0x0f ; ADDWF quo_L,F ;quo_L += quo_L*0x10 SKPNDC ;Note the 'DC' ADDLW 1 ; ADDWF quo_H,W ;quo_H += quo_L*0x10 (plus stuff) 19 cycles/instructions It works on the same 'multiply by 0x55 and divide by 0x100' concept. It's kind of interesting to see how much error is incurred by this method. If you simply multiply by 0x55 and divide by 0x100 you'll discover that the result is often too low. That can be explained by the fact that an infinite series has been truncated. Or equivalently, 85/256 = 0.3320 and 1/3 = 0.33333... So my implementation of the algorithm has a slight modification: n/3 ~ (n+1)*85/256 To see if this really works, you can either test by brute force all 256 values of n (yeah, that's what I did at first) OR try to find a relationship that proves the approximation is valid. So in the spirit of my recently purchased 3rd edition of Knuth's 'Art of Computer Programming: Seminumerical Algorithms'(*), I thought it would be interesting to try the proof thingy. (*) See http://www-cs-faculty.stanford.edu/~knuth/taocp.html for info on Knuth's books. Recall John Halleck's post on integer division: (a integerdivide b) = (a-(a mod b))/b (Note that there was a slight typo [as opposed to a thinko] in John's post) Or in C jargon: = (a -(a % b)) /b And since I'm interested in the error, I want to find the result of : e = (n integerdivide 3) - ( (n+1)*85 integerdivide 256) where e = the error in the algorithm n = input between 0 and 255 e = (n - (n%3))/3 - ( (n+1)*85 - ((n+1)*85 % 256))/256 = n/3 - (n+1)*85/256 - (n%3)/3 + ((n+1)*85 % 256) /256 256*n - 255*(n+1) -256*(n%3) + 3*(((n+1)*85)%256) = ----------------- + -------------------------------- 768 768 mod identity: c*(a%b) = (a*c) % (b*c) n - 255 -((256*n)%768 + ((n+1)*255)%768) e = ------- + ----------------------------------- 768 768 n - 255 (-n + 255) % 768 e = ------- + ---------------- (**) 768 768 n - 255 - (n - 255) % 768 e = -------------------------- 768 Now, since the input, n, is between 0 and 255, the mod term in the numerator: (n - 255) % 768 = n - 255 and so the error is e = 0 ! In fact, the approximation is exact for all values of n between -512 and 1023 (**) In general, a % c + b % c != (a+b) % c. However, in this case, the difference always results in an integer that's less than 768. Lucky. Scott

Hi! 1-Mar-98 20:15 Rick Dickinson wrote about "Re: divide by 3": >> At 03:08 PM 2/23/98 -0000, jhobbs wrote: >> >I once knew a fast trick for divide by 3, but now I am unable to reproduce >> >it. If someone can share it with me (and others) that would be great. >> > >> >Take care -Jim >> >> I'm not sure how much this will help, but.... >> >> 1/3 = 1/2 - 1/4 + 1/8 - 1/16 + 1/32 - 1/64 + 1/128 .... etc. 1/3 =(1/2 - 1/4)+(1/8 - 1/16)+(1/32 - 1/64)+ 1/128 .... etc. 1/3 = 1/4 + 1/16 + 1/64 + .... etc. Or in other words 1/3 = 0.01010101010101010.... (using BINARY notation for result) Or in another words 0x100/3=0x55+1 0x10000/3=0x5555+1 0x100000000/3=0x55555555+1 Furthermore, it's possible to use the same method to divide by 5: 1/5=0.0011001100110011... And so on. Are these methods (quick and not exact) usefull? May be. I have a doubt. -- Vladimir M. Klochko

Vladimir M. Klochko wrote: > Furthermore, it's possible to use the same method to divide by 5: > 1/5=0.0011001100110011... Which is of course quite useful in decimal conversion. > Are these methods (quick and not exact) usefull? > May be. I have a doubt. You misunderstand something here. They *are* quick, and they *are* exact. They are the fastest way to perform constant divisions. They are *as* accurate as but much faster than "long division" algorithms. In either case, you must perform *all* intermediate calculation without truncation, that is, you have to retain and perform addition on the *whole* of any right-shifted value. As with long division, adding half the divisor to the dividend before the division is the easiest way to perform rounding, i.e., add 1 if dividing by three, add 2 if dividing by 5 and so on. Cheers, Paul B.

I hate to beat a dead horse, but isn't this solution the same as the one that was offered up by an Andy?, ie. a/3 = a/2 - a/4 + a/8 ... Matt On Mon, 16 Mar 1998, Lauri Pirttiaho wrote: {Quote hidden}> The most accurate approximate arithmetic is done by using > convergent iteration. > > An iteration to divide by 3 is based on the identity > > a/3=a/2-(1/2)(a/3) > > Approximate a/3 by a/2 and repeat > > (new a/3) = a/2 - (old a/3) /2. > > until (new (new a/3)) == old a/3 > > The iteration converges rather fast. > > Notice that you need to compare results over two iterations > to "filter" the last bit oscillation. > > In the same way you can divide by 5 by iteration based on > identity > > a/5=a/4-(1/4)(a/5) > > etc. > > -- Lauri > > --- > <a href="http://www.ee.oulu.fi/~lapi/">For more info.</a> > /*****************************************/ /* Matt Calder, Dept. of Statistics, CSU */ /* http://www.stat.colostate.edu/~calder */ /*****************************************/

Re my: > The most accurate approximate arithmetic is done by using > convergent iteration. > An iteration to divide by 3 is based on the identity > a/3=a/2-(1/2)(a/3) Matt Calder asks: > I hate to beat a dead horse, but isnt this solution the same as >the one that was offered up by an Andy?, ie. > a/3 = a/2 - a/4 + a/8 ... Basically yes. The difference between the series summation and the iteration is that the error is not accumulated but instead reduced. You can do rather well with 8 bits in iteration while you need more bits when doing the series as has been show in other postings. For comparison, you get accurate result via series summation in 16 bits using 24 words of program (see Ray Gardiner on Mar. 2., the program needs BCF STATUS,C before the first RLF) with as many cycles and 8 bytes of data space. Iteratively you can get the same in 13 words of program with max of 56 cycles and 3 bytes of data space (or less, that was just my first quick and dirty iteration code). -- Lauri --- <a href="http://www.ee.oulu.fi/~lapi/">For more info.</a>

In the contest! :) movwf reg0 ;reg0=3w/8 bcf status,c rrf reg0,f addwf reg0,f rrf reg0,f bcf status,c rrf reg0,f movf reg0,w movwf reg1,f ;iteratively refine twice bcf status,c ;w/3=3w/8-(2(w'/3))/16 rlf reg1,f swapf reg1,w andlw 0x0f subwf reg0,w movwf reg1,f bcf status,c rlf reg1,f swapf reg1,w andlw 0x0f subwf reg0,w Enter with a byte in w, exit with the byte divided by 3 in w. 20 words program, 20 cycles, 2 register bytes. If you want to save 3 words make the iteration a subroutine, this will cost you 8 cycles in execution time. Anyone came up with a better code? (I quit this subject...) ;) -- Lauri --- <a href="http://www.ee.oulu.fi/~lapi/">For more info.</a>

Hi! 15-Mar-98 00:54 Paul B. Webster VK2BZC wrote about "Re: divide by 3": >> Vladimir M. Klochko wrote: >> >> > Furthermore, it's possible to use the same method to divide by 5: >> > 1/5=0.0011001100110011... >> >> Which is of course quite useful in decimal conversion. Yes, but for indication only. Not for further computations. And Bin2Dec need both quotient and reminder (this method doesn't give the reminder). >> > Are these methods (quick and not exact) usefull? >> > May be. I have a doubt. >> >> You misunderstand something here. They *are* quick, and they *are* >> exact. They are the fastest way to perform constant divisions. They >> are *as* accurate as but much faster than "long division" algorithms. >> In either case, you must perform *all* intermediate calculation without >> truncation, that is, you have to retain and perform addition on the >> *whole* of any right-shifted value. Well, let us check the formula N/3=(N*0x55+128)/256. The best method is a brutal force, because it helpes me to reduce a quantity of English words. :) Here the output of the simple C program. The first column is N, the second is (N*0x55+128)/256, the third N-3*((N*0x55+128)/256) (it should be named "reminder"), the 4-th and 5-th are N/3 and N%3. 0 0, 0 0, 0 1 0, 1 0, 1 2 1, -1 0, 2 3 1, 0 1, 0 4 1, 1 1, 1 5 2, -1 1, 2 6 2, 0 2, 0 Reminder of fast algorithm is {-1,0,1} since we use rounding. Okay. Let us continue. . . . 126 42, 0 42, 0 127 42, 1 42, 1 128 43, -1 42, 2 129 43, 0 43, 0 130 43, 1 43, 1 131 43, 2 43, 2 132 44, 0 44, 0 133 44, 1 44, 1 Note that reminder became TWO! And both (128/3) and (131/3) (i.e.((128+3)/3)) are 43! . . . 252 84, 0 84, 0 253 84, 1 84, 1 254 84, 2 84, 2 255 85, 0 85, 0 And up to N=255 there are no more surprises. Any exact division algorithm should give a reminder in range 0,1,...(K-1) for any divisor K. Of course, using rounding we can shift this range. But there are only K different legal values for reminder. The above table shows FOUR values {-1,0,1,2} for reminder of division by THREE using this algorithm. So, is it an "*exact* algorithm"? The reason is quite clear. The exact formula is N/3=(N*0x55+128)/255 (not .../256!). 128 (or 127, or 0 -- no matter) represent only the method of rounding and no more. Using division by 256 instead of division by 255 we found the fast method. :) And loose precision. :( Though it is possible to vary the constant 128 and try to restore precision (but for limited range of N only!). Scott Dattalo did it. And it's work. Exellent! -- Vladimir M. Klochko

Vladimir M. Klochko wrote: > > Well, let us check the formula N/3=(N*0x55+128)/256. <SNIP> > So, is it an "*exact* algorithm"? No, but... <SNIP> > Though it is possible to vary the constant 128 and try to > restore precision (but for limited range of N only!). > Scott Dattalo did it. And it's work. Exellent! Actually, my change to the approximation was this: N/3 ~= (N+1)*0x55/0x100 Which I proved was exact for INTEGER DIVISION, which (to reiterate) is defined (correctly) by John Halleck as: a integer_divide b = (a -(a % b)) /b Integer division does not provide rounding. For those of you who are C-junkies, integer division is the same thing as this: int integer_divide(int a, int b) { return(a/b); } if you want rounding, then you'll need to do something like: return(a/b + ( (a>=b/2) ? 1 : 0) ) or slightly more accurate but less safe: return(a/b + ( (2*a>=b) ? 1 : 0) ) ---------- Out of some kind of perverse enjoyment I've shown that the general formula holds true. a // b = ((a+1) * (b//N)) // N on the condition that b<N and a < b*N. For brevity, I defined '//' to be integer division. For the divide-by-3 case, b = 3 N = 256 b//N = 85 For the divide-by-5 case, b = 5 N = 256 b//N = 55 The divide-by-5 case can be implemented in 19 cycles (it may've been 17... my notes are not with me now). If anybody is interested in the proof, then send me an e-mail and I'll get it to you next week (when I have my notes). Scott -- If you believe everything you read then you shouldn't read. Japanese Proverb

DIV3 ;---------------------------------------------- ; ; N 3N 3N 3N ; --- = ---- - ---- + ----- - ... ; 3 8 8*8 8*8*8 ; ; Enter with N in W exit with N/3 in W ; Executes in 13 cycles, Uses X and T ; ; Thanks to Lauri Pirttiaho for the idea! ;---------------------------------------------- MOVWF X ; CLRC ; RRF X,F ; X = N/2 ADDWF X,F ; C:X = 3N/2 RRF X,F ; X = 3N/4 C=LSB SWAPF X,W ; W = XL:XH ANDLW 0x0F ; W = XH = 3N/64 MOVWF T ; T = 3N/64 CLRC ; RRF X,F ; X = 3N/8 SUBWF X,W ; W = 3N/8 -3N/64 BTFSC T,3 ; ADDLW 1 ; ADD 1 if 3N/64 >= 8 I think this is the fastest so far...13 cycles Maximum error is +-1bit. (either truncated or rounded) Yes, I know +-1 bit is important, but sometimes speed is even more important!. Ray Gardiner (DSP Systems) RemoveMErayspam_OUTdsp-systems.com http://www.dsp-systems.com private email to:- rayspamnetspace.net.au