Completely OT!: help with base-2 division

[Magnus Danielson]

From: "Trevor Page" <trevor at resonance.fsnet.co.uk>
Subject: Completely OT!: help with base-2 division
Date: Sun, 20 Feb 2000 13:51:17 -0000

> Hi,

Hi Trevor!

> This is a very off - topic question, so I would request that, if anyone
> could possibly help me in any way at all, please reply to me privately.
> Thanks!
> This message relates to my final year project.

Let's see here what we can do.

> Basically, I need some help regarding binary division. I know there will
> possibly be a few of you on the list who will be experienced with this sort
> of thing, and may be able to offer me some advice. I've tried elsewhere but
> not had that much luck. Any help would be much appreciated.

OK. First, there are a number of sources that you really should read, namely:

"The Art of Computer Programing" by Donald Knuth, especially the Seminumerical
Algorithm book would be of use, but I recommend all three of them. I naturally
have them ;)

"Computer Architecture - A Quantitative Approach" by Hennessy and Patterson.
Great book on computer architecture.

Both these references will hold very usefull material on how to implement
hardware and software algorithms for arithmetic.

> Here's the problem.
> 
> I need to perform the calculation: K = A1/B1
> 
> And following this: B2 = A2/K
> 
> 
> 
> (Ax = ADC reading , K = sensor constant, Bx = analyte concentration.)
> 
> The first calculation is to perform a calibration process. The A1 value
> comes from the analogue to digital converter, measuring the concentration of
> analyte in a liquid sample. B1 is the known concentration of that sample.
> >From these, the processor can work out K, which is the volt per unit
> concentration gradient for the sensor in use. (the sensitivity of the sensor
> is previously not known prior to calibration).
> 
> The second division is to calculate the unknown concentration, given the ADC
> reading from the sensor and the sensitivity gradient, K, for that sensor.
> >From these values, the actual concentration (B2) is calculated.
> 
> Now those specific details are not really relevant, but here is the problem:
> The final value needs to be very accurate. When performing the first
> calculation in binary, K is truncated (e.g. 11 / 5 would give 2). The second
> calculation would also have the same problem, and therefore the value B2
> would be very innaccurate.

OK.

> When performing division in binary, it is easy to produce a remainder. This
> could be done in the first calculation when finding K. However, if I were to
> do this, how could I perform the second binary division when the divisor (K)
> itself consists of a quotient *and* a remainder?
> 
> There is probably a straightforward, established way of doing this, but I
> have been unable to work out how.

First, one has to realize that the combination of these equations is really

     A2   A2             B1
B2 = -- = -- * B1 = A2 * --
     K    A1             A1

Since division is a expensive calculation as compared to multiplication in both
hardware and software we would like to avoid it. If I interprent you correctly
we only need to calculate K once, and after that it is stable until the next
calibration, right?

If so, we can convert the A2 -> B2 calculation from a division to a
multiplication. We use a new factor K':

     1   B1
K' = - = --
     K   A1

and we get

B2 = A2 * K'

Now, actually doing that multiplication isn't all that hard, I assume you can
do that.

Now, the precission issue...

You can have diffrent round-off methods, and truncation isn't really the best
one from a precission point of view. You may just want to round of to the
nearest or possibly save a number of bits below the decimal point.

There is an easy trick to use here, to rescale the values. This way you can
transform your integer arithmetic into fixed point arithmetic by simple means.

Let's say you want to save 4 bits in the division, then we start of with the
K' factor where division of B1 with A1 would drop bits, you can get 4 of those
at the bottom of your integer value by just multiplying B1 with 16 prior to use
it. This will result in

B1' = B1 * 16

     B1'
K" = ---
     A1

where K" is also scaled up with 4 bits. Great. It still doesn't round off, but
you have some extra bits. You can round of by using

                   B1'            B1'   1            B1' + 1/2 * A1
K" = Round_nearest(---) = Integer(--- + -) = Integer(--------------)
                   A1             A1    2                  A1

The last expression is easilly calculated in a CPU.

Then for the actual calculation you would use the new expression

B2' = A2 * K"

and B2' is now also has it's decimal point 4 bits shifted.

So, your CPU would have to do this:

Calibration:
B1' := B1 << 4
T := A1 >> 1
T := T + B1'
K" := T / A1

Calculation:
B2' := A2 * K"

Then, it's up to you to figure out how to deal with these extra 4 bits.

Remember to consider to upper and lower range of the scale for the value
with the range of the input variables (all three of them).

I hope you got some inspiration here.

Cheers,
Magnus (designed a DSP pipeline for a ASIC)