On Thu, 9 Nov 2000, Dwayne Reid wrote:

> At 08:51 AM 11/9/00 -0500, M. Adam Davis wrote:
> >I'm somewhat confused...  You want the ratio of A to B (ratio = A/B) and
> >you are instead using the equation ratio = (A+B)/B ?
> >
> >-Adam
> >
> >Dwayne Reid wrote:
> > >
> > > Good day to all.
> > >
> > > I've got another little challenge to throw out:  I have 2 - 9 bit numbers
> > > that I need to find the ratio of, where the ratio is expressed as a number
> > > from 00 to FF.
> > >
> > > Its the usual thing: x = (remainder of) (a+b) / b  and I'm doing it with
> > > the standard 16 bit divide routines.  But I figure there has to be an
> > > easier / shorter / quicker method.
>
> You are right - I wrote in a confusing manner.  I have 2 quantities, where
> a goes increases when b decreases, similar to the wiper on a pot.  In
> effect, I want to find the position of the wiper expressed as a number from
> 00 to FF.
>
> One other thing: since a + b is a constant, the sum of the two will also
> fit in 9 bits.
>
> Like I said, I am using a relatively clunky 16 bit divide routine that I'd
> really like to optimise for 9 bits.  I've already modified it to use only 9
> shifts / iterations instead of 16 but I can't help think that there is a
> better way.

Without cranking out the code, I don't how much more efficient this will be.

But, suppose you write b as a sum of two integers:

b = x*16 + y

i.e. x is the high order 5 bits, y the low 4.

If x is 0, then just branch to a 4-bit divide routine. If x is not zero then
apply this formula:


  1 / (16*x + y) = 1/x/16 * (1 - (y/x/16) + (y/x/16)^2 - ...)

Since x is a 5 bit number, you only need a 5-bit division routine. Furthermore,
you only need two terms (okay maybe three) since y/(x*16)^3 is less than an
8-bit result.

You might be able to optimize.

  ~= 1/(16*x) * ( 1 - y/(16*x) + ( y/(16*x))^2 )

  = 1/(16*x) * ( (1 - y/(16*x))^2 + y/(16*x) )

The division y/(16*x) only needs to be performed once. Now the approximation
isn't fantastic. For example, suppose b = 24

 1/24 = 1/(1*16 + 8) = 0.0416666

where as for x=1, y=8 you get:

 1/24 ~= 1/16 *( (1 - 1/2)^2 + 1/2) = 0.046875

It's kind of close. If you care this example out to three terms:

 1/24 ~= 1/16 * (1 - 1/2 + (1/2)^2 - (1/2)^3)
       = 0.0390625

closer, but now on the low side. Now, 1/24 is an extreme example. Ideally you
want a large x and a small y. Lets take b = 500 = 31*16 + 4. Well,

  1/500 = 0.002

  1/500 ~= 1/(31*16) * ( (1 - 4/(31*16))^2 + 4/(31*16) )
         = 0.00201607

A little better.

Scott

--
http://www.piclist.com hint: The list server can filter out subtopics
(like ads or off topics) for you. See http://www.piclist.com/#topics