Does your hardware support 8 x 8 or 16 x 16 bit Multiply?
Does your hardware support 16 / 16 bit?
For most cases work out the precision and accuracy you require in BINARY places, then multiply up numbers that are used in the divide and multiply by at LEAST that number of places do the calculation and remove fixed point multiplier to give integer result you need.
Remember 6 binary bits of precision is not the same as 6 binary bits of accuracy as some fractions are always awkward (prime numbers especially).
Depends on the target and what instructions it has. Also what register and data sizes it supports in assembler. As well as the points above.
That is the least of your worries, you need to trap for divide by zero. negative slope just means you add a negative number! Remember that a positive / negative gives a negative number so does a negative / positive number, similarly a positive * negative number gives a negative number.
You need to give more info as on controllers I use (H8 series) a lot of this is easy because it has 32bit registers as well hardware mult and div instructions.
On some processors you will need to do multi byte arithmetic as they only support 8 bit data types.
--
Paul Carpenter | paul@pcserv.demon.co.uk
Main Site
GNU H8 & mailing list info.
For those web sites you hate.
Or more properly (taking into account finite precision, elementary numerical analysis and the fact that 60-40 = 20 ;) )
X = 37 + (11*15)/20 X = 37 + 165/20 X = 37 + 8 X = 45
Of course this chops rather than rounds so the question of precision still comes up. Also you need an intermediate value of 2n+1 bits (where n is the number of bits in your original values), check against overflows and of course against divide by zero. You also need to be careful that the table step size isn't too large. Some of those checks can be eliminated if you can guarantee the composition of the table.
As long as you don't need better than +-1 than there is no need to have any representation other than whole numbers.
Mind you if the OP needs better than +/- 1 the first thing to address is the data representation in the table.
I don't know if the AVR has (or has a SW library that has) an 8bit x 8bit to 16bit multiply and a 16bit / 8 bit -> 8bit divide but if it does than with a few 'reasonble restrictions' on the table there will be no worry about overflows or loss of precision.
Just a suggestion or three: if you drop the index and add a value for 20, you'll use less eeprom space. you will know that index = offset * 20. Your values are very coarse. and the result is not likely to be very accurate. This appears to be a complex curve (at least a cubic). I would throw in some extra values. You could insert a value every 10, or perhaps 8 (the arithmetic becomes simpler/faster/cheaper if the index is a power of 2 as multiplies and particularly divides can be replaced by shifts. ..... but I'm not going to write the assembler for you, sorry.
You'll notice that the denominator is a constant. There are two ways of handling this simply. The first is to multiply by a constant of the reciprocal of the denominator (i.e. 1/20 - or 2^N * 1/20 in the exemplar case), or better still change the interval to 2^N (e.g. 8 or 16) and shift right N to accomplish the division.
In the subject of my posting the type of MC is given, AVR ATMega32. This device does not support DIV, and has only 8 bit Registers. But math software routines are available.
Unfortunately i'm not an good asm-programmer. Due to that fact, to write such an interpol function in asm, it will take the rest of my life. So i need a piece of code, which i can use as "black box". Values in, result out...
Anyway many thanks for your answer, it shows me some significant details and explain the principle.
And, of course, also thanks do Mel and Robert.
Regards and greetings from Petershagen, Rolf
begin 666 wink.gif M1TE&.#EA#P`/`+,``````+^_O___```````````````````````````````` M`````````````````````"'Y! $```$`+ `````/``\```0T,$@):ITX5,'Y MQ4 G>E,XC@`EF.MJIJSEQ>PI;C9:YZYGOQK?C12
You have already got several good answers, but there are two things which might help you:
#1 Can the intervals in the EEPROM be a power of two? #2 There is a simple way for proper rounding of the results.
If you could make this table so that the intervals are powers of two, then you can replace the division by a simple shift (arithmetic shift right, ASR). Then you can also find the table position by shifting instead of dividing. This will save a lot of time and code.
Let's say you have the tabulated data with 32-unit intervals. Then when you need to find the value for f(x):
-1 -1 (bin average -0.5) 0 0 (bin average 0.5) 1 1 (bin average 1.5)
The results are half-step lower than they should be (they should coincide with the bin averages). This can be corrected by adding 8 (that is 0.5 * 2^4) to the initial value:
Everything is rounded to the nearest integer, halves are rounded up.
So, the plain ASR works fine apart from the average -0.5 bias in the result. The bias can be compensated for in the tabulated data or by adding the half before shifting.
The worst thing you may do is to unsignedify the number, round it down, and then put the sign back. Because:
The function becomes dead around zero! The result is zero over two units, and everything linear becomes non-linear. Cross-over distortion sets in...
Unfortunately, this is exactly what C does when you write:
int z, x, y;
z = x / y;
There is a technical reason for this; division is easier to do, if you do not need to write different branches for different signs. C rounds towards zero. Not up, not down, but towards zero. (This may even be a desired behaviour in some cases, but with measurements it is a very bad thing.)
One simple way around this is to use biased unsigned divisions:
// bias by 15: z = (x + 15 * y) / y - 15;
If x + 15 * y always >= 0. This is rather easy with constant divisors. With variable divisors finding a suitable constant is very difficult. Pick a too low one, and the sum will underflow. Pick a too high one, and the sum will overflow. The case with the possibility of a negative divisor is even more complicated. Then the only alternative is to branch the calculations by the signs before doing anything;
int x, y, z; unsigned int ax, ay, az; bool sign;
// find out the sign of the result and the absolute values of x, y if (x < 0) { ax = -x; sign = false; } else { ax = x; sign = true; }
if (y < 0) { ay = -y; sign = ~sign; } else ay = y;
// if the sign of the result is negative, round away from zero if (sign == false) { az = (ax + ay - 1) / ay; z = -az; } else { az = ax / ay; z = az; }
Yes, there are a lot of extra variables which may be avoided by using type casts. However, I think it is better avoid the type casts and let the compiler get rid of the extra variables.
So, twenty-something lines of code to achive a very simple thing. The good thing is that this does not give a very large performance hit, as the signed division algorithm does this anyway.
To make the algorithm round right (towards nearest, halves up) requires only the following changes:
negative branch: az = (ax + ay - 1 - ay/2) / ay
positive branch: az = (ax + ay/2) / ay
Even though it is very tempting to say:
ay - 1 - ay/2 == ay/2 - 1,
don't. Because it isn't. For, e.g., ay = 17:
17 - 1 - 8 == 8 - 1 8 == 7
Oops.
I know this is somewhat complicated. The effect of false rounding is usually quite small. I personally crashed into this well-known (generally, that is, not well-known by me) problem when I was looking at a F-transform of some real-world data. There were some harmonics there shouldn't've been. I scratched through the skin of my head before finding out the problem.
If off-by-one is bad, off-by-half is not much nicer, either.
Hi Most high level languages round towards zero, mostly because it is traditional. Doing floored rounding makes more sense but even that has to be done carefully. In something like DSP, one can accumulate a DC offset because of floored rounding. As you point out, you get a cross over distortion for rounding towards zero so there is no absolutely right way to do this. One has to look carefully at the application one intends to use it in before determining which way to go on this. One might even use both methods in the same stretch of code. I once designed a XY table that requires 24 bit math that a fellow was doing 16 bit math by simply extending it to 32 bits while using the round towards zero. It was a disaster. The table would occasionally jump by a sizable amount while incrememnting by a joy stick. This was a table that should have positioned to about two 10/1000th of an inch. This was traced to his round towards zero math in the Pascal he was using to do the extended math. It would have been nice if the uP makes had included both types in the hardware so we could choose which to use and where. Dwight
I think it should be more appropriate to talk about truncation in this case and this behaviour makes sense in many situations.
IMHO, rounding should be reserved for rounding towards the nearest integer.
At least old Pascal did not allow direct assignment of floating point values to integer, but instead the trunc or round functions had to be used.
This is a third method and makes sense in this interpolation case, however, this is more of a special case.
It should be noted that if the hardware uses 1's complement or sign/magnitude representation, there is the problem with +0 and -0 and thus the potential for "cross over distortion".
Here's a suggestion. Do you have a C compiler for your CPU. If not try to get a demo version. THen write the solution is C and look at the asm output. Then you have the asnwer you're looking for.
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.