Trig lookup table accuracy

[Centaur]

In one of the tutorials, I believe for an omni-wheeled robot it is mentioned that a trig lookup table is a solution to the problem of micro-controllers not being able to do trig calculations very fast, but you lose accuracy (10% is suggested).

Is there anything that prevents one from making a more detailed trig lookup table for higher accuracy?  Does anyone have a way to estimate how much memory a table would take up.

Let's say a table with sin and cos (since these two can derive everything else) ranging from 0 to 2pi in increments of 1 degree (which is 0.0174 rad).  2 x 360 matrix = 720 elements

[izua]

depends on how you define your accuracy.
you can have a sine table from 0 to pi, or from 0 to 180. The best way to have this for a microcontroller, is of course, from 0 to 0xFF, or from 0 to 0xFFFF.

If you go with 8 bits, you may have decent accuracy. Remember that you can only store half the cycle (since a sine is essentially made up of two symmetric elements, mirrored) and read the table in reverse order for cosine.

[paulstreats]

Also, rather than take up memory , if you have programming space left over then why not store it as an array pointer in the far rom. That way youre lookup table exists in code space and not ram space(considering that you would normlly populate the ram space by progrmming it into code spce and then copying it to ram then it seems the best wy to go). (dont forget that some mcu's also have extra eeprom space available that most people dont ever use)

Also dont forget that the accuracy and resolution of youre lookup tble will inevitably be an underlying concern when deciding on a resolution for maps etc..

[Webbot]

You only need values from 0 to 90 degrees as everything else is symmetrical about these values (see Admins tutorial on lookups). So if you want want 1 degree accuracy then you will need to store 90 values. So the next question is 'How accurate do you want the values'? This will dictate how may bytes you use to store each answer - typically this will be between 1 byte (8 bits) and 4 bytes (32 bits). So your table could take anywhere between 90 and 360 bytes.

As mentioned previously - this table is read only so would be better in flash memory (PROGMEM) as there is normally a lot more of this (ie 8k on an ATMega8) than the RAM used to store your variables (512 bytes on an ATMega8). If in doubt search the forum/Google about using PROGMEM on an AVR.

[JesseWelling]

I really need to write up that linear interpolation tutorial...

You don't need to store all 90 values, if you are willing to burn up some computation to calculate a y from 2 points and an x value.

[Webbot]

I really need to write up that linear interpolation tutorial...

You don't need to store all 90 values, if you are willing to burn up some computation to calculate a y from 2 points and an x value.

As Jesse says - if you are willing to lose some accuaracy then you can change the smooth sin wave into a series of straight lines. IE instead of 90 samples you could have just 10, say, and so when you want value 45degrees then this is half way between the 4th and 5th value so you can take these two value and interpolate between the two using something like:-

Code: [Select]

/*
* Interpolate between two numbers
* value - the current value to be used
*   minVal - the minimum that 'value' can be
*   maxVal - the maximum that 'value' can be
*   minRtn - the return value if 'value = minVal'
*   maxRtn - the return value if 'value = maxVal'
*   return a value in the range minRtn to maxRtn
*/
int interpolate(int value, int minVal, int maxVal, int minRtn, int maxRtn){
long int lRtnRange = maxRtn - minRtn;
long int lValRange = maxVal - minVal;
long int lRelVal = value - minVal;
lRtnRange =  minRtn + ( lRtnRange * lRelVal / lValRange );
return (int)lRtnRange;
}

It comes down to a trade off between space for the lookup table and how much accuracy you want

[Webbot]

Should have added that the amount of error will depend on the gradient of the sin curve. So if you are looking at 85 degrees then this is near the top of the sin curve, the gradient is small, so the error is less. But if you are looking at 5 degrees, where the gradient is steeper, than the error is greater.

[izua]

I don't think it's a good idea to interpolate sin() in a linear fashion. You can balance it, like 2/3 to first value, or 2/3 to the second one, but in the end, without a correction matrix you wouldn't get any good extra values.

[Webbot]

I don't think it's a good idea to interpolate sin() in a linear fashion. You can balance it, like 2/3 to first value, or 2/3 to the second one, but in the end, without a correction matrix you wouldn't get any good extra values.

As mentioned previously its a trade off between space and accuracy.

So here's a good mathematical conundrum and approximation (not aimed at you izua!) to keep you maths folk thinking:-

The hypotenuse, via Pythagoras is Hypotenuse = SQRT(  (side1 * side1) + (side2 * side2) )
ie if the sides are 3 and 4 then hypotenuse = SQRT( 3*3 + 4*4) = SQRT( 9 +16) = SQRT(25) =5

So here is an approximation:
'The hypotenuse is the longest side plus one third of the shortest side'.
So in the previous example: longest side=4, shortest side=3 so hypotenuse = 4 + (3/3) = 5

Correct answer requires: two multiplications, one addition, and a square root
Approximation requires: one division, one addition

So the approximation is much faster and doesn't mean having to do a computationally expensive square root. Is it 100% accurate - no. Is it accurate for most controllers - well probably 'yes'.

If nothing else then it may allow any folk out there taking a Maths exam to quickly work out an approximate answer in their heads to make sure that the answer on paper is in the correct ballpark.

P.S. If any of you Math genius' can explain 'why this works' then I'd love to know why. Seems the error increases the further you move from 45 degrees (I think).

[izua]

i don't get it i don't understand what you mean. Sine is the ratio between a cathetus and the hypothenuse, which allows you to compute the acute angles

lookup tables are always the catch between space and computing times. but adding a correction table it's worse, since you won't get much better accuracy, and you must also apply the matrix over the values.

[Admin]

'The hypotenuse is the longest side plus one third of the shortest side'.

starting with what you said:
hypotenuse = SQRT(  (side1 * side1) + (side2 * side2) ) = side1 + 1/3*side2

moving sqrt over:
(side1 * side1) + (side2 * side2) = (side1 + 1/3*side2)²

breaking it all apart, because (a + b)² = a² + 2ab + b²:
side1² + side2² = side1² + 2*side1*1/3*side2 + (1/3*side2)²

canceling out terms, bringing them out:
side2² = 2*side1*1/3*side2 + 1/3*1/3*side2²

getting rid of side2 and 1/3:
3*side2 = 2*side1 + 1/3*side2

and:
3*side2 - 1/3*side2 = 2*side1

is:
side2*(3 - 1/3) = 2*side1

so:
side2 = 0.75*side1

sides don't match up . . .

so therefore . . . hmmmm darnit not sure what I just solved . . . 

lol

[izua]

SQRT(  (side1 * side1) + (side2 * side2) ) = side1 + 1/3*side2

err.. now i really don't understand this one

[JesseWelling]

Should have added that the amount of error will depend on the gradient of the sin curve. So if you are looking at 85 degrees then this is near the top of the sin curve, the gradient is small, so the error is less. But if you are looking at 5 degrees, where the gradient is steeper, than the error is greater.

Unless your bound your error by what you need and then your data points in the piece wise table get closer and closer together.... I wrote a perl script to make my tables at work. I'll dig it up.

[Webbot]

'The hypotenuse is the longest side plus one third of the shortest side'.

starting with what you said:
hypotenuse = SQRT(  (side1 * side1) + (side2 * side2) ) = side1 + 1/3*side2

moving sqrt over:
(side1 * side1) + (side2 * side2) = (side1 + 1/3*side2)²

breaking it all apart, because (a + b)² = a² + 2ab + b²:
side1² + side2² = side1² + 2*side1*1/3*side2 + (1/3*side2)²

canceling out terms, bringing them out:
side2² = 2*side1*1/3*side2 + 1/3*1/3*side2²

getting rid of side2 and 1/3:
3*side2 = 2*side1 + 1/3*side2

and:
3*side2 - 1/3*side2 = 2*side1

is:
side2*(3 - 1/3) = 2*side1

so:
side2 = 0.75*side1

sides don't match up . . .

so therefore . . . hmmmm darnit not sure what I just solved . . . 

lol

My 'Maths student' son has kindly told me what you have proved.... You started with the left side as Pythagoras theorem (ie the exact answer) and my approximation on the right side. So your working out has proved that the approximation exactly equals the exact answer when, and only when, side2 = 0.75*side1. Hence the 3,4,5 triangle works fine but for other ratios of sides then the approximation would be less accurate.
Thanks to Admin for the workings and to Webbot Jnr for the reason !! (All beyond me)

[TrickyNekro]

Why, don't you use Taylor or McLaurin series for this...
Just compute how accurate is the output of your microcontroller to the motors... pwm and such...
Then see how "big" variable you need... I can imagine a 2 - 3 bytes is good...
Since PWM don't offer eeerrr don't know the word here... well they can't accept numbers like this: 123.5353
The only accept this 124 in that case...
Anyways, you won't have a real problem with floats...
So you can have something like this                  (  2 bytes       )  .  (   2 bytes  )
The pwm will only see the first 2 bytes...
But this is a hard way to do this...
So take a long variable let's say 3bytes...
multiply your every part of the Taylor or McLaurin series with let's say 1000 and let the processor do the math...
Then divide by 2 as many times as the zeros of the value you multiplied the series... In this case you divide by 2, 3 times... or you divide by 6 doesn't matter
Then you have a 16 bit value and that's it...

I'm sorry for the way I write all these but thinking and writing in a foreign language is hard sometimes....

Generally, if you don't want to trouble yourself you create a table, but if you want to solve any trig functions,
you can use either Taylor or Maclaurin series... ( Here is the part that I beg god you know how to solve them....)
They are easy really but helpful...
You can also calc the error you expect...
You can get the series from wiki for a relief.... don't really have to solve them yourself...


Best Regards,
Lefteris, Greece