/Date: Mon, 23 Feb 1998 15:08:04 -0000
/From: jhobbs <spam_OUTjhobbsTakeThisOuTQUIKNET.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
>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 \
\ .....mrtKILLspam.....iname.com, ph: +46 (0)414 70741; fax +46 (0)414 70331 /
>>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!
>>>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
>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/
==================================================================
Andy Kunz - Montana Design
Go fast, turn right, and keep the wet side down!
==================================================================
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.
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.
>>>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
>
> 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
======================================================
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.
>>>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
>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
>
>>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.
>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.)
>
> 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?
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.
> 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.
>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.
> 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."
> 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.
> >> > -----------------------------------------------------------------
> >> >
> >> >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.
> 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.
>> 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....
>
> >> 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.comhttp://www.dsp-systems.com
> private email to:- rayEraseME@spam@netspace.net.au
> 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....
> 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.
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
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
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
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 |
+---------------------------------+---------------------------+
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
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".
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.
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
> 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
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.
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.
> 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.
> 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).
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.
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!
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.
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!
> 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!.
QUIKNET.COM>
