Searching \ for 'Re[2]: 16bit divide by 10' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/method/math.htm?key=divide
Search entire site for: '16bit divide by 10'.

Truncated match.
PICList Thread
'Re[2]: 16bit divide by 10'
1996\05\28@182725 by Thomas Coonan

flavicon
face
>> I can save 600bytes in a lookup table if I can figure out a good way
>> to divide a 16 bit number by 10.
>....
>Here's a 16-bit divide-by-10 algorithm (y = x/10):
>
>    y = x/4
>
>    for i = 1 to 7
>        y = x - y
>        y = y/4
>    next i
>
>    y = y/2
I understand why powers of two are good... And I sort of see how you
divide down close to the target before you do too much shifting...

So, what's your general problem-solving technique for this class of
problem?  Are you applying some basic number theory tricks about rational
numbers, or is this trial-n-error?

1996\05\29@055015 by fastfwd

face
flavicon
face
Thomas Coonan <spam_OUTPICLISTTakeThisOuTspamMITVMA.MIT.EDU> wrote:

> So, what's your general problem-solving technique for this class of
> problem?

In general, my technique goes like this:

1.  Call all my friends and ask them how to do it.  Invariably, they
   don't know.
2.  Look through Donald Knuth's books for the solution.  Invariably,
   I won't find it.
3.  Sit down with a big sheet of paper and the TI-35 calculator I've
   had since I was in high school (one of these days, I'm gonna get
   me a calculator with built-in hex/binary/boolean operations),
   and launch QuickBASIC on my PC.
4.  Thrash around for a couple of hours, alternating mad scribbling
   with blowing smoke rings at the ceiling, until something clicks.
5.  Build a model in QuickBASIC, test it, then call all my friends
   back and gloat.
6.  Later that year, while looking through Knuth for something else,
   find the solution that I "discovered".  Sigh.

Step 4's kinda vague, I know...

> Are you applying some basic number theory tricks about rational
> numbers, or is this trial-n-error?

Every once in a while, I actually find a use for all the discrete
math and number theory I learned in school.  Usually, though, it's
just a matter of making the right "trial and error" connections.

In this case, my divide-by-10 code is just a divide-by-5 with an
extra divide-by-2 tacked on at the end.  I came up with the original
divide-by-5 routine by noticing the following:

   x      4x        x     5x
  --- =  ----, and --- = ----.
   5      20        4     20

Therefore,

   x      x     x
  --- =  --- - ----
   5      4     20

          x      x/4
      =  --- - -------
          4       5

          x       (x/4)     (x/4)/4
      =  --- - ( ------- - --------- )
          4         4          5

      etc...

I don't know if that's clear... The point is that you can expand
"x/5" into a form that INCLUDES a "/5" element, and THAT element
can be further expanded into ANOTHER equation that also includes a
"/5" element, etc.

This is pretty standard stuff; if you've spent any time at all in
advanced math classes, you've probably seen expansions like this.

Anyway, the expansion can go on as long as you like.  I suppose I
COULD have calculated the necessary depth of expansion to give
precise answers over the range [0-65535], but I'm lazy, so I just did
a little trial-and-error experimentation in QuickBASIC to arrive at
the conclusion that only seven iterations were necessary.

Sorry this is such an unsatisfying explanation...

-Andy

Andrew Warren - .....fastfwdKILLspamspam@spam@ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

1996\05\29@155408 by Scott Dattalo

face
flavicon
face
Thomas Coonan wrote:
>
> >Here's a 16-bit divide-by-10 algorithm (y = x/10):
> >
> >    y = x/4
> >
> >    for i = 1 to 7
> >        y = x - y
> >        y = y/4
> >    next i
> >
> >    y = y/2
> I understand why powers of two are good... And I sort of see how you
> divide down close to the target before you do too much shifting...
>
> So, what's your general problem-solving technique for this class of
> problem?  Are you applying some basic number theory tricks about rational
> numbers, or is this trial-n-error?

and

Andrew Warren wrote:
{Quote hidden}

Another way to skin Andy's cat is to return to the binary fraction of x/5 and do
some manipulation:

 x
--- = 0.001100110011001100110011...
 5
            3     3      3             3
    = x *( -- +  --- + ---- + ... + ------ )
           16    256   4096         2^(4*m)

    = x * 3 * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) )        (1)

Now, x * 3 can be rewritten as x<<2 - x (i.e. x*3 = x*4 - x)

 x
--- = (x<<2 - x) * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) )
 5

    = x * ( 1>>2 + 1>>6 + 1>>10 + ... + 1>>(4*m-2) ) -
      x * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) )

    = x * ( 1>>2 - 1>>4 + 1>>6 - 1>>8 + 1>>10 -+  ... -+ 1>>(2*m) )

Now, assuming x is a 16 bit integer we only need to keep terms up to m=7

 x
--- ~= x * ( 1>>2 - 1>>4 + 1>>6 - 1>>8 + 1>>10 - 1>>12 + 1>>14 )
 5

     = x * (1 - (1 - (1 - (1 - (1 - (1 - 1>>2)>>2)>>2)>>2)>>2)>>2)>>2
     =     (x - (x - (x - (x - (x - (x - x>>2)>>2)>>2)>>2)>>2)>>2)>>2

This is Andy's algorithm unrolled.


Just for grins, Pete Brink's cat can be skinned similarly:

First note that x * 3 can be rewritten as x<<1 + x. Substitute this into
equation (1) from above and you get:

 x
--- = (x<<1 + x) * ( 1>>4 + 1>>8 + 1>>12 + ... + 1>>(4*m) )
 5
    = x * (1>>3 + 1>>4 + 1>>7 + 1>>8 + ... )
    = (x>>3 + x>>4 + x>>7 + x>>8 + ...)
    = (x + x>>1 + x>>4 + x>>5 + ...) >> 3
or,
 x
--- = (x + x>>1 + x>>4 + x>>5 + ...) >> 4
 10


Everyone knows a cat has 9 lives. We have used three on this problem, so there
are probably six more solutions lurking out there.


Scott

1996\05\29@203352 by fastfwd

face
flavicon
face
Scott Dattalo <PICLISTspamKILLspamMITVMA.MIT.EDU> wrote:

> Another way to skin Andy's cat is to ....
>
> Just for grins, Pete Brink's cat can be skinned similarly ....

Nice, Scott.

-Andy

Andrew Warren - .....fastfwdKILLspamspam.....ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499

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