Searching \ for 'divide by 3' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: massmind.org/techref/method/math.htm?key=divide
Search entire site for: 'divide by 3'.

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

flavicon
face
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

picon face
On 23 Feb, jhobbs wrote:

/Date:    Mon, 23 Feb 1998 15:08:04 -0000
/From:    jhobbs <spam_OUTjhobbsTakeThisOuTspamQUIKNET.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

face
flavicon
face
jhobbs <.....PICLISTKILLspamspam@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 - fastfwdspamKILLspamix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499

1998\02\26@155048 by Morgan Olsson

picon face
>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 \
\  .....mrtKILLspamspam.....iname.com, ph: +46 (0)414 70741; fax +46 (0)414 70331    /

1998\02\26@160753 by ERIC SCHLAEPFER

flavicon
face
>>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_OUTspamTakeThisOuTiname.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

face picon face
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 |
+--------------------------------+
Fight injustice, please look at
http://homepages.enterprise.net/toolan/joanandrews/

Personal page: http://www.people.cornell.edu/pages/shb7
@spam@shb7KILLspamspamcornell.edu
Phone(USA): (607) 253-0315

1998\02\26@174118 by Andy Kunz

flavicon
face
>     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

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

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

flavicon
face
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.schlaepferKILLspamspamAUTODESK.COM> wrote:

{Quote hidden}

Martin R. Green
spamBeGoneelimarspamBeGonespamNOSPAMbigfoot.com

To reply, remove the NOSPAM from the return address.
Stamp out SPAM everywhere!!!

1998\02\26@191730 by Steve Baldwin

flavicon
face
> 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: TakeThisOuTstevebEraseMEspamspam_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

flavicon
face
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" <RemoveMEelimarspamTakeThisOuTNOSPAMBIGFOOT.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.schlaepferEraseMEspam.....AUTODESK.COM> wrote:

{Quote hidden}

it
{Quote hidden}

Martin R. Green
RemoveMEelimarEraseMEspamEraseMENOSPAMbigfoot.com

To reply, remove the NOSPAM from the return address.
Stamp out SPAM everywhere!!!

1998\02\26@191933 by Richard Nowak

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

=========================================
= Abolish the Income Tax! Fire the IRS! =
= http://www.nrst.org/                  =
=========================================

1998\02\26@191935 by Regulus Berdin

flavicon
face
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

picon face
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

flavicon
face
Yeah subtract your answer and then devide by two to get your answer  >:)

Peter

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


{Quote hidden}

1998\02\26@211440 by Orin Eman

flavicon
face
> 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

face
flavicon
face
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
       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

flavicon
face
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) spamBeGoneraySTOPspamspamEraseMEdsp-systems.com http://www.dsp-systems.com
private email to:- KILLspamrayspamBeGonespamnetspace.net.au

1998\02\26@223705 by Andrew Warren

face
flavicon
face
Ray Gardiner <EraseMEPICLISTspamEraseMEMITVMA.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@spamspam_OUTix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499

1998\02\27@032150 by Ray Gardiner

flavicon
face
{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) .....rayspam_OUTspamdsp-systems.com http://www.dsp-systems.com
private email to:- TakeThisOuTray.....spamTakeThisOuTnetspace.net.au

1998\02\27@041012 by Andrew Warren

face
flavicon
face
Mel Evans <TakeThisOuTMEvans1027KILLspamspamspamAOL.COM> jokingly wrote:

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

and Peter van Hoof <.....PICLISTspamRemoveMEMITVMA.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 - RemoveMEfastfwdspamspamBeGoneix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499

1998\02\27@041014 by Andrew Warren

face
flavicon
face
Ray Gardiner <spamBeGonePICLIST@spam@spamspam_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 - TakeThisOuTfastfwdspamspamix.netcom.com
=== Fast Forward Engineering - Vista, California
=== http://www.geocities.com/SiliconValley/2499

1998\02\27@124622 by Matt Calder

flavicon
face
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: <@spam@Pine.SUN.3.96.980227095513.27526BRemoveMEspamEraseMEtlaloc.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

flavicon
face
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

flavicon
face
Gotta go with Halleck on this one.

-----Original Message-----
From:   John Halleck [SMTP:EraseMEJohn.Halleckspam@spam@CC.UTAH.EDU]
Sent:   Friday, February 27, 1998 12:23 PM
To:     @spam@PICLISTspam_OUTspam.....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

flavicon
face
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: spamBeGonepeterEraseMEspamcousens.her.forthnet.gr  phone: + 3081 324450, 380534
snailmail:  Folia, Agia Fotini, Karteros, Heraklion  Crete, Greece.

1998\02\28@001442 by Eric Smith

flavicon
face
Mel Evans <MEvans1027spamBeGonespamAOL.COM> wrote;
> Simple.  To multiply by 3, double and add to original.  To divide by 3,
> just do the inverse!

Morgan Olsson <RemoveMEmrt@spam@spamspamBeGoneINAME.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

flavicon
face
{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) .....ray@spam@spamEraseMEdsp-systems.com http://www.dsp-systems.com
private email to:- .....rayRemoveMEspamnetspace.net.au

1998\02\28@020353 by schupet

flavicon
face
sssss

Ray Gardiner wrote:
{Quote hidden}

1998\02\28@074313 by paulb

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

1998\02\28@090804 by Peter van Hoof

flavicon
face
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
flavicon
face
>
>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  RemoveMErayspamspamBeGonenetspace.net.au

1998\03\01@231650 by Rick Dickinson

flavicon
face
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  spamBeGonertdKILLspamspam@spam@notesguy.com  |  into" -- Rick Adams,     |
|   http://www.eArchiTechs.com    |   in alt.folklore.urban   |
+---------------------------------+---------------------------+

1998\03\04@230439 by Rick Dickinson

flavicon
face
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_OUTspam@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@spamnotesguy.com  |  into" -- Rick Adams,     |
|   http://www.eArchiTechs.com    |   in alt.folklore.urban   |
+---------------------------------+---------------------------+

1998\03\04@233130 by Rick Dickinson

flavicon
face
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  RemoveMErtdEraseMEspamKILLspamnotesguy.com  |  into" -- Rick Adams,     |
|   http://www.eArchiTechs.com    |   in alt.folklore.urban   |
+---------------------------------+---------------------------+

1998\03\05@103028 by ERIC SCHLAEPFER

flavicon
face
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_OUTspamRemoveMEmicroserve.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

picon face
   Here's a divide-by-3 routine that my son Paul (.....fmdesignpespamRemoveMEaol.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    mevans1027spam@spam@aol.com    813/595-7685

1998\03\06@053415 by Walter Banks

picon face
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

flavicon
face
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  EraseMErtdRemoveMEspamSTOPspamnotesguy.com  |  into" -- Rick Adams,     |
|   http://www.eArchiTechs.com    |   in alt.folklore.urban   |
+---------------------------------+---------------------------+

1998\03\09@210631 by Ray Gardiner

flavicon
face
<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) RemoveMErayKILLspamspamTakeThisOuTdsp-systems.com http://www.dsp-systems.com
private email to:- spamBeGonerayspam@spam@netspace.net.au

1998\03\12@114859 by sdattalo

face
flavicon
face
> 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

flavicon
face
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

flavicon
face
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

flavicon
face
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

flavicon
face
       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 */
/*****************************************/

1998\03\17@034928 by Lauri Pirttiaho

flavicon
face
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

flavicon
face
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

flavicon
face
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

flavicon
face
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

face
flavicon
face
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

flavicon
face
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_OUTspamdsp-systems.com http://www.dsp-systems.com
private email to:- rayspamspamnetspace.net.au

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