Truncated match.
PICList
Thread
'divide by 3'
1998\02\23@224049
by
jhobbs
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
1998\02\26@120501
by
Mel Evans
On 23 Feb, jhobbs wrote:
/Date: Mon, 23 Feb 1998 15:08:04 -0000
/From: jhobbs <spam_OUTjhobbsTakeThisOuT
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
1998\02\26@151813
by
Andrew Warren
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 - fastfwd
KILLspamix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499
1998\02\26@155048
by
Morgan Olsson
>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 /
1998\02\26@160753
by
ERIC SCHLAEPFER
>>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_OUT
TakeThisOuTiname.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
1998\02\26@174101
by
Sean Breheny
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 \ \
>>
mrt
spam_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@shb7KILLspam
cornell.edu
Phone(USA): (607) 253-0315
1998\02\26@174118
by
Andy Kunz
> 1010
> + 101
> ------
> 1111
I think the question was how to divide by 3.
==================================================================
Andy Kunz - Montana Design
Go fast, turn right, and keep the wet side down!
==================================================================
1998\02\26@174839
by
Dan Walkowski
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
1998\02\26@180333
by
Martin R. Green
|
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.schlaepferKILLspam
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 \ \
>>
RemoveMEmrtTakeThisOuT
iname.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
spamBeGoneelimarspamBeGone
NOSPAMbigfoot.com
To reply, remove the NOSPAM from the return address.
Stamp out SPAM everywhere!!!
1998\02\26@191730
by
Steve Baldwin
> 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: TakeThisOuTstevebEraseME
spam_OUTkcbbs.gen.nz
New Lynn, Auckland ph +64 9 820-2221
New Zealand fax +64 9 820-1929
======================================================
1998\02\26@191738
by
ERIC SCHLAEPFER
|
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" <RemoveMEelimar
TakeThisOuTNOSPAMBIGFOOT.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 \ \
>>
EraseMEmrt
iname.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
RemoveMEelimarEraseME
EraseMENOSPAMbigfoot.com
To reply, remove the NOSPAM from the return address.
Stamp out SPAM everywhere!!!
1998\02\26@191933
by
Richard Nowak
|
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_OUT
KILLspaminame.com, ph: +46 (0)414 70741; fax +46 (0)414 70331 /
>
>
=========================================
= Abolish the Income Tax! Fire the IRS! =
= http://www.nrst.org/ =
=========================================
1998\02\26@191935
by
Regulus Berdin
To divide by 3, just subtract 3 from the number thru a loop
and count the number of iterations until it gets to zero.
Reggie.
1998\02\26@192045
by
Brian Schousek
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}
1998\02\26@192458
by
Peter van Hoof
1998\02\26@211440
by
Orin Eman
|
> 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.
1998\02\26@212007
by
sdattalo
|
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
1998\02\26@221214
by
Ray Gardiner
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) spamBeGoneraySTOPspam
EraseMEdsp-systems.com http://www.dsp-systems.com
private email to:- KILLspamrayspamBeGone
netspace.net.au
1998\02\26@223705
by
Andrew Warren
Ray Gardiner <EraseMEPICLIST
EraseMEMITVMA.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
1998\02\27@032150
by
Ray Gardiner
|
{Quote hidden}>Ray Gardiner <
spamBeGonePICLIST
KILLspamMITVMA.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_OUT
dsp-systems.com http://www.dsp-systems.com
private email to:- TakeThisOuTray.....
TakeThisOuTnetspace.net.au
1998\02\27@041012
by
Andrew Warren
|
Mel Evans <TakeThisOuTMEvans1027KILLspam
spamAOL.COM> jokingly wrote:
> To multiply by 3, double and add to original. To divide by 3,
> just do the inverse!
and Peter van Hoof <.....PICLIST
RemoveMEMITVMA.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 - RemoveMEfastfwd
spamBeGoneix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499
1998\02\27@041014
by
Andrew Warren
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 - TakeThisOuTfastfwdspam
ix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499
1998\02\27@124622
by
Matt Calder
|
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 <
PICLISTEraseME
MITVMA.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 -
RemoveMEfastfwdEraseME
spam_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.27526BRemoveME
EraseMEtlaloc.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);
}
}
1998\02\27@125535
by
John Halleck
|
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.
1998\02\27@134539
by
John Shreffler
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)
1998\02\27@160553
by
peter
John Shreffler wrote:
SNIP
And then * 2
> Name: WINMAIL.DAT
> Part 1.2 Type: unspecified type (application/octet-stream)
> Encoding: x-uuencode
Please divide this by 3
Peter Cousens
email: spamBeGonepeterEraseME
cousens.her.forthnet.gr phone: + 3081 324450, 380534
snailmail: Folia, Agia Fotini, Karteros, Heraklion Crete, Greece.
1998\02\28@001442
by
Eric Smith
Mel Evans <MEvans1027spamBeGone
AOL.COM> wrote;
> Simple. To multiply by 3, double and add to original. To divide by 3,
> just do the inverse!
Morgan Olsson <RemoveMEmrt@spam@
spamBeGoneINAME.COM> wrote:
> Could someone unfold that for a binary math newbie, please?
I think what Mel meant is that if you have a number x, and you want to
know y, which is 1/3 of x, all you have to do is take x and subtract 2y.
Not very useful though.
Maybe he meant something else.
1998\02\28@015336
by
Ray Gardiner
|
{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:- .....rayRemoveME
netspace.net.au
1998\02\28@020353
by
schupet
|
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
1998\02\28@074313
by
paulb
|
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.
1998\02\28@090804
by
Peter van Hoof
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}
'divide by 3'
1998\03\01@112129
by
Ray Gardiner
>
>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 RemoveMEray
spamBeGonenetspace.net.au
1998\03\01@231650
by
Rick Dickinson
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 |
+---------------------------------+---------------------------+
1998\03\04@230439
by
Rick Dickinson
|
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 |
+---------------------------------+---------------------------+
1998\03\04@233130
by
Rick Dickinson
|
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 RemoveMErtdEraseME
KILLspamnotesguy.com | into" -- Rick Adams, |
| http://www.eArchiTechs.com | in alt.folklore.urban |
+---------------------------------+---------------------------+
1998\03\05@103028
by
ERIC SCHLAEPFER
|
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_OUT
RemoveMEmicroserve.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}
1998\03\05@172509
by
MEvans1027
Here's a divide-by-3 routine that my son Paul (.....fmdesignpe
RemoveMEaol.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
1998\03\06@053415
by
Walter Banks
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
1998\03\07@224830
by
Rick Dickinson
|
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 EraseMErtdRemoveME
STOPspamnotesguy.com | into" -- Rick Adams, |
| http://www.eArchiTechs.com | in alt.folklore.urban |
+---------------------------------+---------------------------+
1998\03\09@210631
by
Ray Gardiner
|
<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) RemoveMErayKILLspam
TakeThisOuTdsp-systems.com http://www.dsp-systems.com
private email to:- spamBeGoneray
@spam@netspace.net.au
1998\03\12@114859
by
sdattalo
|
> 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
1998\03\14@025309
by
Vladimir M. Klochko
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
1998\03\14@185457
by
paulb
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.
1998\03\16@090610
by
Lauri Pirttiaho
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>
1998\03\16@122651
by
Matt Calder
|
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 */
/*****************************************/
1998\03\17@034928
by
Lauri Pirttiaho
|
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>
1998\03\18@051557
by
Lauri Pirttiaho
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>
1998\03\20@061824
by
Vladimir M. Klochko
|
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
1998\03\20@061824
by
Vladimir M. Klochko
|
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
1998\03\20@155720
by
sdattalo
|
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
1998\03\20@171735
by
Ray Gardiner
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_OUT
dsp-systems.com http://www.dsp-systems.com
private email to:- rayspam
netspace.net.au
More... (looser matching)
- Last day of these posts
- In 1998
, 1999 only
- Today
- New search...