[sdiy] Accuracy with integer maths

[Tom Wiltshire]

> Tom, if you are going to truncate a 16-bit result to 8-bits accuracy you really should preserve the 9th bit so that you can test it and decide whether to round the value up or down.

What, you mean like *actual rounding* instead of brutal truncation?! <Gasps!> How modern!

> Think what you would do if you were going to round a decimal number like "317" to the nearest ten.  Although you're only going to keep the top two digits (the '3' and the '1',) you need to test the units digit to see if the result should be rounded up to 320 or down to 310.  (I usually implement rounding by adding in a half to produce a carry if the fractional part that you are going to chop off was greater than 0.5, then do a plain truncate.  This eliminates any branching in the code so the execution time is always constant, and you don't incurr any pipeline stalls, etc.)

Yeah, that makes sense. Nice trick. Better than doing a bit test on the 9th bit and then conditionally adding one, for sure.

> Most hardware multipliers will give you all of the bits of the result automatically, so unless you are hard-coding your own software-multiply routine I'm not sure where you would make optimisations if you don't need all the bits of the result.
> What are you actually using this multiply for?!?!?

It's doing the "Level VCA" calculation in one of my envelope generator programs.

The process is this:
You start with a phase accumulator value that represents how far through your envelope curve you are. You use the top X bits (8 in my case) to read the required value out of the envelope curve lookup table, and then read out the next value in the table too. Then you use some of the next lowest bits of the phase accumulator to interpolate between those two, to give you a smoother curve, especially at slow rates. I also use that interp to boost the resolution of the data from 8-bit to 10-bit.
Finally, that 10-bit value is multiplied by the 8-bit Level CV value to produce a 10-bit output.

So you see why I'm asking about the accuracy. I've got lots of bits of phase accumulator I could use for the interp, but I don't need all of them, and I've got an 10x8 = 18-bit multiplication result of which I only need 10-bits.

I've done more experiments (running the algorithms in PHP at various accuracies and spitting out the results to HTML tables) and found that if I need ten bits from the interpolation of two 8-bit numbers, I only need to use two extra bits for the interp. It doesn't look like any extra bits are required to guard against error - although I'm truncating everything at the moment, not rounding, so that might be why. Rounding would need the next bit to be accurate too, thereby requiring one guard bit.
Similarly with the multiply. For a 10-bit output I only need 2 bits beyond the 8 I've got already, but the problem here is that I'm reluctant to reduce the resolution of the Level CV or of the curve data. But then if I'm reducing the 18-bit output down to 10-bits at the end, that's what I'm doing anyway, right?

> Are you trying to do some clever DSP stuff on a general purpose CPU?

I don't know about "clever", but I'm still trying to do "serious" DSP on a "comedy" chip! (PIC 16F - no hardware multiply - only nutters need apply)

Thanks,
Tom