Searching \ for 'divide by 3' in subject line. ()
Help us get a faster server
FAQ page: techref.massmind.org/techref/method/math.htm?key=divide
Search entire site for: 'divide by 3'.

Truncated match.
'divide by 3'
1998\02\23@224049 by

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
On 23 Feb, jhobbs wrote:

/Date:    Mon, 23 Feb 1998 15:08:04 -0000
/From:    jhobbs <jhobbsQUIKNET.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
jhobbs <PICLISTMITVMA.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 - fastfwdix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499
>On 23 Feb, jhobbs wrote:
/I once knew a fast trick for divide by 3, but now I am unable to reproduce
>/it.  If someone can share it with me (and others) that would be great.
>/
>/Take care -Jim

>    Simple.  To multiply by 3, double and add to original.  To divide by 3,
>just do the inverse!
>-- Mel Evans

Could someone unfold that for a binary math newbie, please?
/Morgan
/  Morgan Olsson, MORGANS REGLERTEKNIK, SE-277 35 KIVIK, Sweden \
\  mrtiname.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 \ \
>mrtiname.com, ph: +46 (0)414 70741; fax +46 (0)414 70331    /

Sure.

101

Since the place value of binary is two, you can double the number by shifting it
left one bit, like this:

Old:  101
New: 1010

Now you add it to the original number, like this

1010
+  101
------
1111

The result is the number 15, which is the answer to 5 * 3!

Later,

Eric
At 01:04 PM 2/26/98 -0800, you wrote:
{Quote hidden}

shifting it
{Quote hidden}

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 |
+--------------------------------+
http://homepages.enterprise.net/toolan/joanandrews/

Personal page: http://www.people.cornell.edu/pages/shb7
shb7cornell.edu
Phone(USA): (607) 253-0315
>     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!
==================================================================
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
>
>
> 101
>
>Since the place value of binary is two, you can double the number by
shifting it
{Quote hidden}

No kidding.  I think the point of the question is how do you DIVIDE by 3
easily.  The simple trick above is not applicable.

The infinite sum solution posted earlier seems like a useful method, since
it only involves dividing by two successively.

Dan
Great, but I think the question really referred to the bit about "just
do the inverse".  This doesn't make sense to me.  The original
multiplication is the easy part.

Martin.

On Thu, 26 Feb 1998 13:04:09 -0800, ERIC SCHLAEPFER
<eric.schlaepferAUTODESK.COM> wrote:

{Quote hidden}

Martin R. Green
elimarNOSPAMbigfoot.com

Stamp out SPAM everywhere!!!
> The infinite sum solution posted earlier seems like a useful method,
since
> it only involves dividing by two successively.

I haven't seen anyone mention repeated subtraction.
A loop that subtracts 3 each time and counts how many times before the
result is less than zero.
Not efficient or elegant, but simple.

Steve.

======================================================
Very funny Scotty.  Now beam down my clothes.
======================================================
Steve Baldwin                Electronic Product Design
TLA Microsystems Ltd         Microcontroller Specialists
PO Box 15-680                email: stevebkcbbs.gen.nz
New Lynn, Auckland           ph  +64 9 820-2221
New Zealand                  fax +64 9 820-1929
======================================================
Hello,

Oops! I misunderstood the question. :-( Sorry about that. I think I have a book
at home describing a neat answer to the division thing. I'll post back when I
get it.

Later,

Eric

Subject: Re: divide by 3
Author:  "Martin R. Green" <elimarNOSPAMBIGFOOT.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.schlaepferAUTODESK.COM> wrote:

{Quote hidden}

it
{Quote hidden}

Martin R. Green
elimarNOSPAMbigfoot.com

Stamp out SPAM everywhere!!!

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}

=========================================
= Abolish the Income Tax! Fire the IRS! =
= http://www.nrst.org/                  =
=========================================
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.
Try, instead of division, doing an 8 bit by 8 bit -> 16 bit multiplication.
X*Y=Z

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}

Peter

-----Original Message-----
From: Mel Evans <MEvans1027AOL.COM>
To: PICLISTMITVMA.MIT.EDU <PICLISTMITVMA.MIT.EDU>
Date: Thursday, February 26, 1998 12:47 PM
Subject: Re: divide by 3

{Quote hidden}

> Try, instead of division, doing an 8 bit by 8 bit -> 16 bit multiplication.
> X*Y=Z

> 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

It's also possible to make a little state machine (3 states) to walk
the dividend highest bit downwards, outputing one bit each time.  You
can get as many bits of result as you like this way!

I figure about 8 instruction cycles plus a shift per bit of result this way.
(The cost of the shift would depend on how many bits of result
you want.)

Orin.
Brian Schousek wrote:
{Quote hidden}

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
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
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
; really are only interested in the carry
ANDLW   0x0f         ;Remove upper nibble (was lower nibble of
quo_H)
SKPNC                ;
ADDWF   quo_H,F      ;quo_H = dividend *0x55 / 0x80
RRF     quo_H,W      ;W = dividend * 0x55 / 0x100

The C hack is untested, the PIC one IS tested (and works if I did the
test correctly...). I bet though, it's possible to reduce the
execution time even more. Anyone care to waste a little time?

Scott
Andy Warren provided the following....
> -----------------------------------------------------------------
>
>Here's a BASIC program to do a more-or-less correct division; it
>uses the fact that x/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64....:
>
> basic program snipped
>

You can do this twice as fast (8 bit precision) Using...

1/3 = 1/4 + 1/16 + 1/64 + 1/256...

Also no subtraction is required, Also it is interesting to note that
64+16+4+1 = 85, which is Brian Schousek's solution X*85/256.

Ray Gardiner (DSP Systems) raydsp-systems.com http://www.dsp-systems.com
private email to:- raynetspace.net.au
Ray Gardiner <PICLISTMITVMA.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 - fastfwdix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499
{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

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) raydsp-systems.com http://www.dsp-systems.com
private email to:- raynetspace.net.au
Mel Evans <MEvans1027AOL.COM> jokingly wrote:

> To multiply by 3, double and add to original.  To divide by 3,
> just do the inverse!

and Peter van Hoof <PICLISTMITVMA.MIT.EDU> thought HE was
joking, too, when he wrote:

> >:)

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 - fastfwdix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499
Ray Gardiner <PICLISTMITVMA.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 - fastfwdix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499
part 0 2694 bytes content-type:TEXT/PLAIN; charset=US-ASCII; name="div3.c"                Alg1    Alg2
=========       ======  ======
255 / 3 =       85 (0)  81 (-4)
254 / 3 =       85 (1)  81 (-3)
253 / 3 =       84 (0)  81 (-3)
252 / 3 =       84 (0)  81 (-3)
251 / 3 =       84 (1)  80 (-3)
250 / 3 =       84 (1)  80 (-3)
249 / 3 =       83 (0)  80 (-3)
248 / 3 =       83 (1)  80 (-2)
247 / 3 =       82 (0)  79 (-3)
246 / 3 =       82 (0)  79 (-3)
245 / 3 =       81 (0)  79 (-2)
244 / 3 =       81 (0)  79 (-2)
243 / 3 =       81 (0)  78 (-3)
242 / 3 =       81 (1)  78 (-2)
241 / 3 =       80 (0)  78 (-2)
240 / 3 =       80 (0)  78 (-2)
239 / 3 =       80 (1)  76 (-3)

The Alg1 column is using add and sub, while the Alg2 column uses
only add. ( The source for this program is attached).

Matt

On Fri, 27 Feb 1998, Andrew Warren wrote:

{Quote hidden}

/*****************************************/
/* Matt Calder, Dept. of Statistics, CSU */
/* http://www.stat.colostate.edu/~calder */
/*****************************************/

Content-Type: TEXT/PLAIN; charset=US-ASCII; name="div3.c"
Content-ID: <Pine.SUN.3.96.980227095513.27526Btlaloc.stat.colostate.edu>> Content-Description: Source to generate full table

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
int p, d1, d2, c;

for (p=0; p < 100; p++) {

d1 = (p >> 1) - (p >> 2) +
(p >> 3) - (p >> 4) +
(p >> 5) - (p >> 6) +
(p >> 7) - (p >> 8);

d2 = (p >> 2) + (p >> 4) +
(p >> 6) + (p >> 8);

c = floor(((double) p)/3.0 + 0.5);

printf("%d / 3 \t= %d\t%d \t(%d) \t%d \t(%d)\n",
p, c, d1, d1-c, d2, d2-c);
}
}

On Fri, 27 Feb 1998, Ray Gardiner wrote:

> [... lots of stuff snipped ...]

> >> > -----------------------------------------------------------------
> >> >
> >> >Here's a BASIC program to do a more-or-less correct division; it
> >> >uses the fact that x/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64....:

> >> > [...]

> >> You can do this twice as fast (8 bit precision) Using...
> >>     1/3 = 1/4 + 1/16 + 1/64 + 1/256...
> >
> >If you try that method, I think you'll find that the rounding errors
> >are too large to give acceptable results.
>
> Actually, the rounding errors are the same in both cases. I derived

They are not the same.

> the algorithm by simplifying yours, as follows.
>
>         x/2   - x/4     = x/4

We are dealing here with INTEGER division.
"Integer division" differs from what "division" usually means
in a number of fundamental ways. (Such as reversibility)

In terms of what division usually means

(a integerdivide b)

is really

(a-(a mod b))/a

so (x integerdivide 2) - ( x integerdivide 4)
is really

(x - (x mod 2))/2 - (x - (x mod 4))/4

Which can be simplified a bit to something like

(x - 2*(x mod 2) + (x mod 4)) / 4

But does *NOT* reduce to x/4 at all.

> [...]

> So both algorithms are computationally equivalent. Except the
> simplified version is twice as fast.

And wrong.

> [...]

There are any number of good books on "Computer Arithmetic" availiable
that discuss the details of machine computation.  (They usually give
more space to the properties of Floating point numbers, but they
usually cover Integer numbers also.)
I'm afraid it's been too many years since I did that, so I can't
recomend any specific book.
Gotta go with Halleck on this one.

-----Original Message-----
From:   John Halleck [SMTP:John.HalleckCC.UTAH.EDU]
Sent:   Friday, February 27, 1998 12:23 PM
To:     PICLISTMITVMA.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)
John Shreffler wrote:

SNIP

And then * 2

>                    Name: WINMAIL.DAT
>     Part 1.2       Type: unspecified type (application/octet-stream)
>                Encoding: x-uuencode

Peter Cousens
email: petercousens.her.forthnet.gr  phone: + 3081 324450, 380534
snailmail:  Folia, Agia Fotini, Karteros, Heraklion  Crete, Greece.
Mel Evans <MEvans1027AOL.COM> wrote;
> Simple.  To multiply by 3, double and add to original.  To divide by 3,
> just do the inverse!

Morgan Olsson <mrtINAME.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.
{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)

The interesting point (which I missed completely!) was that
with your method the rounding errors tend to cancel.

Ray Gardiner (DSP Systems) raydsp-systems.com http://www.dsp-systems.com
private email to:- raynetspace.net.au
sssss

Ray Gardiner wrote:
{Quote hidden}

Now *there's* a man who knows his maths!

Ray Gardiner wrote:

{Quote hidden}

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.
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
>
>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
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?
MOVF    Xh,W    ;
SKPNC           ;

BTFSC   Xl,7    ; Round up if >128
; result in W

Ray Gardiner, Shepparton, Victoria, Australia  raynetspace.net.au
At 03:08 PM 2/23/98 -0000, jhobbs wrote:
>I once knew a fast trick for divide by 3, but now I am unable to reproduce
>it.  If someone can share it with me (and others) that would be great.
>
>Take care -Jim

I'm not sure how much this will help, but....

1/3 = 1/2 - 1/4 + 1/8 - 1/16 + 1/32 - 1/64 + 1/128 .... etc.

Since all the divisions can be done with simple shifts, there should be a
reasonable method in here, somewhere...

- Rick "Infinite series ya us" Dickinson

+---------------------------------+---------------------------+
| Enterprise ArchiTechs Company   |"You can't reason someone  |
|     Lotus Certified Notes       |  out of a position they   |
|  Appl. Design & Administration  | didn't reason themselves  |
|(818)563-1061  rtdnotesguy.com  |  into" -- Rick Adams,     |
|   http://www.eArchiTechs.com    |   in alt.folklore.urban   |
+---------------------------------+---------------------------+
At 10:57 AM 2/26/98 EST, Mel Evans wrote:
>On 23 Feb, jhobbs wrote:
>
>/Date:    Mon, 23 Feb 1998 15:08:04 -0000
>/From:    jhobbs <jhobbsQUIKNET.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  rtdnotesguy.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  rtdnotesguy.com  |  into" -- Rick Adams,     |
|   http://www.eArchiTechs.com    |   in alt.folklore.urban   |
+---------------------------------+---------------------------+
Hi Everyone,

I finally got around to looking it up. The book I have uses this method:

Where x is the number to divide by 3
(In C)

result = (x >> 2) + (x >> 4) + (x >> 6) + (x >> 8)

Problem with this method is that the result is always too small. It would work
better if you converted the source number to fixed point, and the result of the
division could be rounded somehow, and converted back to an integer. Of course,
we are dealing with a PIC that only works with 8 bits at a time.

Later,

Eric

P.S. I got this method out of a game programming book, which is why it is meant
for 32-bit integers.

Subject: Re: divide by 3
Author:  Peter van Hoof <pvhmicroserve.net> at INTERNET
Date:    2/28/98 9:02 AM

SO! use the fast method BUT start with shifting left a number of times and
shift back afterwards , always the easiest way to reduce rounding errors in
integer calculations

Peter

{Original Message removed}
Here's a divide-by-3 routine that my son Paul (fmdesignpeaol.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.
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
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    mevans1027aol.com    813/595-7685
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
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
Shift N left 2 bits
Shift N left 2 bits

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  rtdnotesguy.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
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
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
; really are only interested in the carry
ANDLW   0x0f         ;Remove upper nibble (was lower nibble of
quo_H)
SKPNC                ;
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
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?
MOVF    Xh,W    ;
SKPNC           ;

BTFSC   Xl,7    ; Round up if >128
; result in W

------<cut>-----------

Ray Gardiner (DSP Systems) raydsp-systems.com http://www.dsp-systems.com
private email to:- raynetspace.net.au
> Here is the code that Scott Dattalo posted, very fast and clean.

<snip>

And here is the code Ray posted...
> DIV3
> ; Call with 8bit in W , exit with X/3 in W
> ;
> ;       RAM: uses T and Xh:Xl
> ;

<snip>

Here's another routine that does the job just ever so slightly
faster. (And it's been tested). It takes advantage of the
often forgotten Digit Carry flag.

; Divide by 3
; Input in W  , Output W/3
;
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

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

SWAPF   quo_H,W  ;quo_H * 0x10

SWAPF   quo_L,W  ;quo_L * 0x10
ANDLW   0x0f     ;

SKPNDC           ;Note the 'DC'

ADDWF   quo_H,W  ;quo_H += quo_L*0x10 (plus stuff)

19 cycles/instructions

It works on the same 'multiply by 0x55 and divide by 0x100' concept.
It's kind of interesting to see how much error is incurred by this
method. If you simply multiply by 0x55 and divide by 0x100 you'll
discover that the result is often too low. That can be explained
by the fact that an infinite series has been truncated. Or
equivalently, 85/256 = 0.3320 and 1/3 = 0.33333... So my
implementation of the algorithm has a slight modification:

n/3 ~ (n+1)*85/256

To see if this really works, you can either test by brute force
all 256 values of n (yeah, that's what I did at first) OR try to
find a relationship that proves the approximation is valid.
So in the spirit of my recently purchased 3rd edition of
Knuth's 'Art of Computer Programming: Seminumerical Algorithms'(*),
I thought it would be interesting to try the proof thingy.

(*) See http://www-cs-faculty.stanford.edu/~knuth/taocp.html for
info on Knuth's books.

Recall John Halleck's post on integer division:

(a integerdivide b) = (a-(a mod b))/b   (Note that there was a
slight typo [as opposed to
a thinko] in John's post)
Or in C jargon:
= (a -(a % b)) /b

And since I'm interested in the error, I want to find the result
of :

e = (n integerdivide 3)  - ( (n+1)*85 integerdivide 256)

where
e = the error in the algorithm
n = input between 0 and 255

e = (n - (n%3))/3 - ( (n+1)*85 - ((n+1)*85 % 256))/256

= n/3 - (n+1)*85/256 - (n%3)/3 + ((n+1)*85 % 256) /256

256*n - 255*(n+1)   -256*(n%3)  + 3*(((n+1)*85)%256)
= ----------------- + --------------------------------
768                   768

mod identity:

c*(a%b) = (a*c) % (b*c)

n - 255    -((256*n)%768  +  ((n+1)*255)%768)
e = ------- + -----------------------------------
768                   768
n - 255    (-n + 255) % 768
e = ------- +  ----------------     (**)
768          768

n - 255 -  (n - 255) % 768
e = --------------------------
768

Now, since the input, n, is between 0 and 255, the mod term
in the numerator:

(n - 255) % 768 = n - 255

and so the error is

e = 0  !

In fact, the approximation is exact for all values of n between
-512 and 1023

(**) In general,  a % c +  b % c != (a+b) % c. However, in this
case, the difference always results in an integer that's less
than 768. Lucky.

Scott
Hi!
1-Mar-98 20:15 Rick Dickinson wrote about "Re: divide by 3":

>> At 03:08 PM 2/23/98 -0000, jhobbs wrote:
>> >I once knew a fast trick for divide by 3, but now I am unable to reproduce
>> >it.  If someone can share it with me (and others) that would be great.
>> >
>> >Take care -Jim
>>
>> I'm not sure how much this will help, but....
>>
>> 1/3 = 1/2 - 1/4 + 1/8 - 1/16 + 1/32 - 1/64 + 1/128 .... etc.
1/3 =(1/2 - 1/4)+(1/8 - 1/16)+(1/32 - 1/64)+ 1/128 .... etc.
1/3 =       1/4 +       1/16 +        1/64 +       .... etc.
Or in other words
1/3 = 0.01010101010101010.... (using BINARY notation for result)
Or in another words
0x100/3=0x55+1
0x10000/3=0x5555+1
0x100000000/3=0x55555555+1

Furthermore, it's possible to use the same method to divide by 5:
1/5=0.0011001100110011...
And so on.

Are these methods (quick and not exact) usefull?
May be. I have a doubt.

--

> 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.
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

---
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}

/*****************************************/
/* 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)

>        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

---
In the contest! :)

movwf  reg0      ;reg0=3w/8
bcf    status,c
rrf    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

---
Hi!
15-Mar-98 00:54 Paul B. Webster VK2BZC wrote about "Re: divide by 3":

>>
>> > 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!

--

Hi!
15-Mar-98 00:54 Paul B. Webster VK2BZC wrote about "Re: divide by 3":

>>
>> > 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!

--

>

>     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!

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

--

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     ;

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) raydsp-systems.com http://www.dsp-systems.com
private email to:- raynetspace.net.au

More... (looser matching)
- Last day of these posts
- In 1998 , 1999 only
- Today
- New search...