PIC C divide by 100

[BradC]

G'day all,

I have a Webasto heater in my car. It reports battery voltage in mV.
Among other things, I have an interface where an external status LED flashes stuff out on request of a remote, and I wanted to add battery voltage as one of the parameters. I figured 3 digits was enough, so I needed to divide the voltage by 100 (or thereabouts).

I don't use anything other than addition or subtraction anywhere in the code, so the challenge was to do a "near enough" divide by 100 with close enough rounding to give me +/- 100mV on the output without pulling any maths routines. The limitations are :
- Voltage is in a 16 bit register in mV, so it's never going to be high enough to hit the MSB.
- Result is in an 8 bit register because if it exceeds 160 then I have bigger things to worry about.

This is what I came up with :
- heater_voltage is the raw result from the heater (u16). Both volt and vtemp are u8.

Code: [Select]

// Hacky divide by 98.81
vtemp=heater_voltage >> 7 & 0xff; // 7
volt=vtemp;
vtemp=vtemp >> 2; // 9
volt += vtemp;
vtemp=vtemp >> 3; // 12
volt += vtemp;
vtemp=vtemp >> 1; // 13
volt += vtemp;

It does the job because precision is not a requirement. I wanted to see if I could minimise the generated code size and stay within a "yeah, that's useful".
This isn't a contest of any kind, I'm more interested to see of someone comes up with a "yeah, here's how to do it better".

[ledtester]

Just using the first 3 of your bit positions might yield a better result:

1/(1/128+1/512+1/4096) = 99.90243902439024390244

and it'll be faster!

Update: I decided to write a program to compare the two methods against the true divide by 100 value and here the results over the range 0 to 16383. The diff column is true value minus algorithm value and the table shows the number of times each of the diff values were attained.

Code: [Select]

        7-9-12  7-9-12-13
diff
-2        2600       1444
-1        9904       6140
0         3856       6680
1           24       2100
2            0         20
total:   16384      16384

So the 7-9-12 scheme tends to underestimate the true value more than the 7-9-12-13 scheme. After some thought I guess this makes sense as we are omitting the fractional parts when we divide by shifting and those fractional parts can add up. The contribution of the 13th-bit compensates for that truncation.

[artag]

If you only want an 8-bit (or less  - 160 counts) then you could shift right by 6 bits and then put the remaining bits through a lookup table.
Faster but more codespace, though I wouldn't imagine speed is an issue.

[mariush]

You could adapt this code to your needs, basically, doing it twice to perform two divisions by 10

Code: [Select]

unsigned divu10(unsigned n) {
  unsigned q, r;
  q = (n >> 1) + (n >> 2);
  q = q + (q >> 4);
  q = q + (q >> 8);
  q = q + (q >> 16);
  q = q >> 3;
  r = n - (((q << 2) + q) << 1); return q + (r > 9);
}

From : https://hackaday.com/2020/06/12/binary-math-tricks-shifting-to-divide-by-ten-aint-easy/


From a post on that same page ... If you can use a 32 bit register/variable, division by 10 is basically  :  ($n * 6554 ) >> 16;

[BradC]

So the 7-9-12 scheme tends to underestimate the true value more than the 7-9-12-13 scheme. After some thought I guess this makes sense as we are omitting the fractional parts when we divide by shifting and those fractional parts can add up. The contribution of the 13th-bit compensates for that truncation.

Yep. That was exactly the reason I went with the 7-9-12-13. For the range values required the truncation always resulted in an "under" so adding the extra element got it "closer". I also played with 7-9-13-13 which was mathematically more of a midway point, but the 12-13 seemed to give more "consistent" results.

You could adapt this code to your needs, basically, doing it twice to perform two divisions by 10
 ... If you can use a 32 bit register/variable, division by 10 is basically  :  ($n * 6554 ) >> 16;

Yes, I looked at a few of those, but I was trying to minimise the math, and both 16 and 32bit uses a lot of space on an 8 bit processor. That's why after the first shift I broke it down to 8 bit values, because I can for the range of inputs expected and it halves the code size.

Of course the smallest way to do it in code terms was iterative subtraction, but it was only fractionally smaller than the multiple shift/add method and a *lot* slower.

More an exercise of optimising the routine for the task rather than general purpose. When you can say with certainty your input is going to be between 10800 and 15000 it becomes an exercise in "how accurate does it have to be for the available level of precision".

Something different than the usual "homework" questions anyway.

Appreciate the input!

[Nominal Animal]

The iterative subtraction is

Code: [Select]

u16 udiv100(u16 n)
{
    u16 d = 0;

    while (n >= 10000) {
        n -= 10000;
        d += 100;
    }

    while (n >= 1000) {
        n -= 1000;
        d += 10;
    }

    while (n >= 100) {
        n -= 100;
        d += 1;
    }

    /* Round (ties upwards) */
    d += (n >= 50);

    return d;
}
and it is exact:
    udiv100(u) == ((u+50) / 100)

It tends to be useful only on 8-bit microcontrollers with add and subtract with carry instructions, but no two-byte multi-bit shifts, et cetera.
The maximum iteration count is 6+9+9=24, so it isn't insanely slow.  Since it really is the number of comparisons it does (max. 28) that is the bottleneck, using intermediate values (like say 3000 and 30) won't speed it up either.

What does the compiler generate for ((u16+50)/100), anyway?

[Ian.M]

Ledtester's suggestion's main deficiency is it fails to accumulate the fractional part.

Try:  (x+x +x/2 +x/16)/256
which is his series expansion refactored to accumulates the fractional part in the low byte.  You'll have to check whether the compiler generates better code if you turn the /2 and /16  into shifts.  The compiler should recognize /256 as return the high byte.

Over your range of interest 10800 to 15000, approx. 38% of the values will be one less than the correct result (x/100 rounded to the nearest integer), and the rest are exact.

If you use: (x+x +x/2 +x/16 +97)/256
within your range, approx. 0.48% will be over by 1 and 0.57% will be under by 1, for a total of approx. 1% of the values differing by +/-1 from the correct result.

[Zero999]

How much flash space do you have?

Does it have to be fast?

If you've got room and speed is unimportant, then why not simply use a divide? It will make your code easier to understand and write.

[BradC]

How much flash space do you have?

Loads.

Does it have to be fast?

Nope.

If you've got room and speed is unimportant, then why not simply use a divide? It will make your code easier to understand and write.

Mainly because I didn't want to. I wanted to come up with a smaller, faster solution that was "good enough". I then posted it here as a bit of a "does anyone know a better way?".

Thus far there have been a number of cool solutions posted which I intend to explore, so I'm learning. A bad day when you don't learn something.

[jpanhalt]

Mainly because I didn't want to. I wanted to come up with a smaller, faster solution that was "good enough". I then posted it here as a bit of a "does anyone know a better way?".

Have you tried PicList (piclist.com)?  Most of the code is old and is written for early PIC's, but the algorithms shown may give some ideas.  There is a nice discussion of divide by 10.  Here is a link to one of the algorithms: http://www.piclist.com/techref/microchip/math/div/16byconst15-dk.htm

[BradC]

Have you tried PicList (piclist.com)?

Indeed. For optimised PIC code it's usually my first port of call.

[snarkysparky]

(X*41)>>12 =  x * 0.010009765625000


close enough for most things

[Ian.M]

(X*41)>>12 =  x * 0.010009765625000

close enough for most things

That's an excellent choice for numbers less than 1599 on any PIC18, which have an 8x8bit hardware multiplier, but on any PIC12 or PIC16 (i.e. the baseline, midrange and enhanced midrange families) which don't have a hardware multiplier,  *41 implies two multi-bit shifts and three additions, which with the final multi-bit  shift to scale the result, is no better than the solutions above, and possibly worse as it needs a three bit left shift, then another two bits left to do the multiplication.

Also, with the O.P.'s number range (10800 to 15000) you'd need 24 bit arithmetic, which obviously adds another 50% overhead handling the additional byte.  To get it to fit in 16 unsigned bits you'd have to shift right by four bits before multiplying, giving: ((X>>4)*41)>>8, which looses accuracy.

[Zero999]

How much flash space do you have?

Loads.

Does it have to be fast?

Nope.

If you've got room and speed is unimportant, then why not simply use a divide? It will make your code easier to understand and write.

Mainly because I didn't want to. I wanted to come up with a smaller, faster solution that was "good enough". I then posted it here as a bit of a "does anyone know a better way?".

Thus far there have been a number of cool solutions posted which I intend to explore, so I'm learning. A bad day when you don't learn something.

Genuine question: why optimise, when there's no need to?

[SiliconWizard]

Ahah, yeah.

Well, if speed is of no concern whatsoever, and you don't have access to hardware division, you can implement the division using a simple radix-2 division without resorting to any tricks. But the compiler will do it better than you will. So why bother.

[MikeK]

Divide by 100:

Code: [Select]

Requested(0.010000) attained(0.010000) error(0.000002%)

-- basic equation
1/128x + 1/512x + 1/4096x - 1/65536x + 1/262144x + 1/524288x - 1/4194304x + 1/134217728x + 1/536870912x

-- factored equation
( ( ( ( ( ( ( ( (  + x ) / 4 + x ) / 32 - x ) / 8 + x ) / 2 + x ) / 4 - x ) / 16 + x ) / 8 + x ) / 4 + x ) / 128

tmp = x
x = x + tmp
x = x >> 2
x = x + tmp
x = x >> 5
x = x - tmp
x = x >> 3
x = x + tmp
x = x >> 1
x = x + tmp
x = x >> 2
x = x - tmp
x = x >> 4
x = x + tmp
x = x >> 3
x = x + tmp
x = x >> 2
x = x + tmp
x = x >> 7

[BradC]

How much flash space do you have?

Loads.

Does it have to be fast?

Nope.

If you've got room and speed is unimportant, then why not simply use a divide? It will make your code easier to understand and write.

Mainly because I didn't want to. I wanted to come up with a smaller, faster solution that was "good enough". I then posted it here as a bit of a "does anyone know a better way?".

Thus far there have been a number of cool solutions posted which I intend to explore, so I'm learning. A bad day when you don't learn something.

Genuine question: why optimise, when there's no need to?

A couple of reasons primarily, both of them related to Mount Everest : "Because it's there".

- Right now on this project I have enough flash space to be able to pull in the maths library. This PIC (with built in regulator and LIN) doesn't come in a larger model, so as the code expands on a "feature" basis, I'm likely to eventually hit the wall.
- It's not uncommon for me to "use what I have in stock" for quick projects, and in some cases that's a uC that doesn't have the resources available to "just use what the compiler generates". In the old days I'd revert to assembler to pack it as tight as necessary. This is a bit of a compromise.

So when I get the opportunity (time mainly) to look at a smaller and/or faster way to skin the cat, I take it as a learning exercise because it'll absolutely come in handy in the future.