Hi Kevin,

I haven't played with Pade approximants.  I find with most projects I do
that including the atan2() float function is a workable solution.
Especially if there is floating point math already happening.  These are
mostly low volume fault or signal detection products where I couldn't
justify amortising my development time to save a chip or die size.

I wasn't perturbed by the tone of your reply.  It is helpful to warn people
about problems and issues that could affect the outcome for them but which
they may not be aware of.

Thanks again for the tip.

Ray



-----Original Message-----
From: kevinisanonymous [mailto:kevinisanonymous@kevi...]
Sent: Friday, 12 November 2004 12:03 PM
To: msp430@msp4...
Subject: [msp430] Re: Integer arctan calculation




I wasn't sure about the exact link but there is a bunch of good stuff
there.  The real pain is computing e^x or a^x quickly wo a quick
ln(x).  Sorry if I sounded a bit richous, just didn't want people to
start blindly truncating power series (not that you were)....

Have you played with Pade Approximants?  You can produce really nice
approximations with them but it's a bit of a pain in the butt make
peace with what's actually going on there.  There is some followable
info on Mathworks somewhere.

Also there is a library for abitrairly percision floating point math,
which i believe is pretty optimized.  If so that code could probably
be hacked to make nice small 'reasonable' percision embedded code.....




--- In msp430@msp4..., "Raymond Keefe" <ray@b...> wrote:
> Hi Kevin,
>
> I haven't played with the arctan version but the sin() approximation
I gave
> has less than 1.5% error in the 0 - 90 degrees
quadrant within the maths
> space I defined.
>
> You will notice I didn't just truncate it but used it as the
starting point.
> sin(x) = x -x^3/7 is a slight variation on sin(x)
= x - x^3/3! +
x^5/5! ...
> which provided a small enough error for a low
overhead of code space.
>
> Thanks for the site reference you gave.  The specific link bombed
out but
> http://jove.prohosting.com/~skripty worked fine. 
Lots of useful info.
>
> Ray
>
>
> -----Original Message-----
> From: kevinisanonymous [mailto:kevinisanonymous@y...]
> Sent: Friday, 12 November 2004 10:54 AM
> To: msp430@msp4...
> Subject: [msp430] Re: Integer arctan calculation
>
>
>
>
> I know that this thread has wandered off the origional question which
> was integer approximations but since it has gotten here....
>
> Recall that a Tayor series (or rather a power series) may have VERY
> poor convergence qualities for some points.  You are much better off
> to use continued fractions or Pade approximants.  There are also
> numerious truncated polynomials that can give you sin and cos, etc,
> with relatively small error (many of these rational approximations
> have degrtee <10) and error < 10-6.  Try
> http://jove.prohosting.com/~skripty/page_76.html
> for some examples.
>
> DO NOT JUST TRUNCATE A TAYLOR SERIES.  You may need 200 terms to
> converge within your needed accuracy.  Also I have seen the following
> done and it is very dangerous,
>
>   If abs(current term - next term) < tolerance then stop.
>
> This will not work because although the difference is less than your
> error this could add up over succesive terms and become signifigant.
> If you are going to try to use a truncated taylor series (assuming it
> is not a alternating series with decreasing terms which is a happy
> scenearo) you must approximate the remainder.  See Taylor's Remainder
> Theorem for info on this.
>
> As far as CORDIC goes there is an abundance of info out there and I
> think I have seen a TMS6x assembly port out there somewhere, which
> could probably easilty be adapted to an MSP430.
>
> Cheers,
>
> kevin
>
>
>
>
> --- In msp430@msp4..., "Raymond Keefe" <ray@b...> wrote:
> > You can also use the taylors series expansion for trig functions and
> > simplify them a bit.  Use symmetry to make life easier so you only
> have to
> > work out one quadrant.
> >
> > A very good approximation of sin(x) is x - x^3/7 though x - x^3/6 +
> x^5/120
> > is even better.
> >
> > For tan() you have tan(x) = x + x^3/3 + 2x^5/15
> >
> > And atan(x) = x - x^3/3 + x^5/5
> >
> > You can truncate the accuracy and therefore the maths to suit the
> need.  I
> > used the simpler sin() method on a processor with 1K of Flash memory
> because
> > a lookup table was too large as was including the float function and
> sin(x)
> > = x wasn't accurate enough.  I limited the space to 0-90 degrees
85 as
> > that was all the accuracy I actually needed. I was already using the
> > multiply byte*byte=word library function so it worked out well and
> was easy
> > to implement.
> >
> > Regards,
> >
> > Ray
> >
> >
> > -----Original Message-----
> > From: michelqv [mailto:michel@q...]
> > Sent: Friday, 12 November 2004 7:39 AM
> > To: msp430@msp4...
> > Subject: [msp430] Re: Integer arctan calculation
> >
> >
> >
> >
> > The presenter for the Cordic algorithms was Dr. Titi Trandafir of
> > Microtrend Systems, Inc.
> > www.microtrendsys.com
> > I don't know what the copyright of the source code is (it was
> > available to all ATC participants), but I'm sure Microtrend would
be
> > willing to email it to any requester.
> > For those who don't know, the cordic routines, in the case of
trig
> > functions, use trig formulas with angles whose trig functions (tan,
> > in general) are successive negative powers of 2 (1/2, 1/4, 1/8,
> > etc...) so that by successive approximations, using only shifts and
> > adds, you can get a pretty good approximation of any trig functions.
> > The devil is in the details, as usaul.
> >
> > Michel
> >
> > --- In msp430@msp4..., Jonathan Kirwan <jkirwan@e...> wrote:
> > > On Wed, 10 Nov 2004 19:49:42 -0000, Mike wrote:
> > >
> > > >I need to do an arctan calculation from the readings of a
pair of
> > A/D
> > > >converters.
> > >
> > > Sine and cosine ADCs, I suppose.
> > >
> > > >I, of course, can use the built in arctan function with
> > > >the compiler but that takes up a lot of code space and is way
more
> > > >accurate than I need. My sin and cos values are 10 bit
numbers (0 -
> >
> > > >1023) and I need a result that is also a 10 but number. E.g.
0
> > > >degrees gives 0, pi/2 gives 256, pi gives 512, you get the
> > picture. I
> > > >have searched a lot but most routines using least squares
> > technique
> > > >give much more precision than I need. So, I don't want
to do it in
> > > >floating point just with integer math. Any suggestions?
> > >
> > > Okay, so the output is from 0 to 1023, with 0 being 0 degrees and
> > 1023 being
> > > (1023/1024)*360 or 359.65 degrees.  I have to assume here that
your
> > two 10 bit
> > > inputs aren't predivided into a single scalar input, because
if
> > they were there
> > > would be no way to produce all four quadrants in the result.
> > (Quadrant 1 and
> > > quadrant 4 are the usual returns from atan() when a single value
is
> > passed.)
> > > So, your desired function must look like:
> > >
> > >   result = arctan2( sinval, cosval )
> > >
> > > And both 'sinval' and 'cosval' must be signed
or else it isn't
> > possible to
> > > produce a 'result' that can span from 0 to 1023.
> > >
> > > Some quick observations that may help examine (or write) code.
> > >
> > > 1)  Quadrant 3 and quadrant 1 look alike and quadrant 4 and
> > quadrant 2 look
> > > alike.  This reduces the need for code from 4 quadrants to just 2
--
> >  quadrant 1
> > > and quadrant 4, for example.  You'll still need a way to
examine
> > both input
> > > values to decide whether it's in 2 or 4, or in 1 or 3, of
course.
> > But that's
> > > simple and it just means adding a PI value (512, in your angle
unit
> > terms.)
> > >
> > > 2)  Quadrant 1 and quadrant 4 can be merged by realizing that tan
-
> > x = -tan x.
> > > This folds both of these together, so you only have to deal now
> > with values
> > > representing the tangent from 0 to 90 degrees.  (0 to infinity,
> > yes, but just
> > > positive values, at least.)
> > >
> > > 3)  Quadrant 1 can now be folded in half by also realizing that
tan
> > x > > > cot(PI/2-x), which is just the same as 1/tan(PI/2-x).
 The result
> > is that arctan
> > > x = PI - arctan(1/x).  Again, just a constant away, after you
> > invert the ratio
> > > (which was originally sin/cos and now would become cos/sin for
> > calculating and
> > > afterwards with PI added.)
> > >
> > > This gets you to only having to handle ratios of your two input
> > values that are
> > > (a) positive only, and (b) where the ratio itself is <= 1. 
Only
> > angles from 0
> > > degrees to 45 degrees or just the first octant.
> > >
> > > 4)  You can go even further and realize that tan(a+b) = (tan
a +
> > tan b) / (1 -
> > > tan a * tan b) and use this to either 'rotate' your
argument a bit
> > to aid your
> > > calculating polynomial (or rational polynomial fraction) error
> > bounds or else to
> > > further fold the sections into tinier and tinier segments, with
the
> > extra cost
> > > of keeping the books.
> > >
> > > Anyway, getting back to (3) above [before worrying over (4)],
also
> > note that the
> > > tangent slope is 1/(cos a)^2.  This means the slope varies from
> > about 1:1 (at 0)
> > > to 1:2 (at 45 degrees).  The mean slope remains fairly close to
1,
> > though, at
> > > about 1.27.  Let's just call it "about 1," for
now.  A span of 45
> > degrees
> > > corresponds to about 1/8th of 1024, or 128 counts of angle.  This
> > suggests that
> > > you'd need to compute out 7 bits of your (sin/cos) fraction
with
> > one more for
> > > rounding.  (Also, if you rotate your 45 degree span by 22.5
> > degrees, between the
> > > range of -22.5 degrees to +22.5 degrees, that slope varies
from
> > about 1:1 to
> > > about 1:1.17, with an average of 1:1.05.  Even better for any
> > calculation
> > > formula you may design.)  In a perfect micro programmer world,
> > arctan x = x, but
> > > although it is close, it's not quite that simple.  (If you
choose
> > to make a 22.5
> > > degree prerotation, the ratio of x to arctan x varies from
> > about .95 to 1.00.)
> > > So, you will need to do some shift/adds after the division.  But
it
> > won't be
> > > hard to work out the details, I think.
> > >
> > > Are you able to work through the details of developing your own
> > algorithm?  I'm
> > > looking forward to seeing Michel's addition, if he can find
the
> > source and post
> > > it.
> > >
> > > Jon
> >
> >
> >
> >
> >
> >
> > .
> >
> >
> > Yahoo! Groups Links
>
>
>
>
>
>
> .
>
>
> Yahoo! Groups Links






.


Yahoo! Groups Links

Hi,

> Recall that a Tayor series (or rather a power
series) may have VERY
> poor convergence qualities for some points. 

I've seen this with smooth 3D-data and tried to fit a two-dimensional
Taylor
series but because of the bad convergence i ended with a complicated 2D-linear
interpolation
of the measured data (x, y, z), although i have tried several transformations,
e. g. x=I*I instead
of x=I.
The major  problem of interpolation of 3D-data is that a plane is defined by 3
points but an 
input value (x, y) is in an x-y-rectangle of measured data and therefore you
have 4 point for 
interpolation. The solution i took is to calculate the nearest three x-y-points
and to calculate the
z-projection of the input value onto the plane which is defined by the three
points. But this is not
simple and takes some CPU time.

Rolf

I wasn't sure about the exact link but there is a bunch of good stuff
there.  The real pain is computing e^x or a^x quickly wo a quick
ln(x).  Sorry if I sounded a bit richous, just didn't want people to
start blindly truncating power series (not that you were)....

Have you played with Pade Approximants?  You can produce really nice
approximations with them but it's a bit of a pain in the butt make
peace with what's actually going on there.  There is some followable
info on Mathworks somewhere.

Also there is a library for abitrairly percision floating point math,
which i believe is pretty optimized.  If so that code could probably
be hacked to make nice small 'reasonable' percision embedded code.....




--- In msp430@msp4..., "Raymond Keefe" <ray@b...> wrote:
> Hi Kevin,
> 
> I haven't played with the arctan version but the sin() approximation
I gave
> has less than 1.5% error in the 0 - 90 degrees
quadrant within the maths
> space I defined.
> 
> You will notice I didn't just truncate it but used it as the
starting point.
> sin(x) = x -x^3/7 is a slight variation on sin(x)
= x - x^3/3! +
x^5/5! ...
> which provided a small enough error for a low
overhead of code space.
> 
> Thanks for the site reference you gave.  The specific link bombed
out but
> http://jove.prohosting.com/~skripty worked fine. 
Lots of useful info.
> 
> Ray
> 
> 
> -----Original Message-----
> From: kevinisanonymous [mailto:kevinisanonymous@y...]
> Sent: Friday, 12 November 2004 10:54 AM
> To: msp430@msp4...
> Subject: [msp430] Re: Integer arctan calculation
> 
> 
> 
> 
> I know that this thread has wandered off the origional question which
> was integer approximations but since it has gotten here....
> 
> Recall that a Tayor series (or rather a power series) may have VERY
> poor convergence qualities for some points.  You are much better off
> to use continued fractions or Pade approximants.  There are also
> numerious truncated polynomials that can give you sin and cos, etc,
> with relatively small error (many of these rational approximations
> have degrtee <10) and error < 10-6.  Try
> http://jove.prohosting.com/~skripty/page_76.html
> for some examples.
> 
> DO NOT JUST TRUNCATE A TAYLOR SERIES.  You may need 200 terms to
> converge within your needed accuracy.  Also I have seen the following
> done and it is very dangerous,
> 
>   If abs(current term - next term) < tolerance then stop.
> 
> This will not work because although the difference is less than your
> error this could add up over succesive terms and become signifigant.
> If you are going to try to use a truncated taylor series (assuming it
> is not a alternating series with decreasing terms which is a happy
> scenearo) you must approximate the remainder.  See Taylor's Remainder
> Theorem for info on this.
> 
> As far as CORDIC goes there is an abundance of info out there and I
> think I have seen a TMS6x assembly port out there somewhere, which
> could probably easilty be adapted to an MSP430.
> 
> Cheers,
> 
> kevin
> 
> 
> 
> 
> --- In msp430@msp4..., "Raymond Keefe" <ray@b...> wrote:
> > You can also use the taylors series expansion for trig functions and
> > simplify them a bit.  Use symmetry to make life easier so you only
> have to
> > work out one quadrant.
> >
> > A very good approximation of sin(x) is x - x^3/7 though x - x^3/6 +
> x^5/120
> > is even better.
> >
> > For tan() you have tan(x) = x + x^3/3 + 2x^5/15
> >
> > And atan(x) = x - x^3/3 + x^5/5
> >
> > You can truncate the accuracy and therefore the maths to suit the
> need.  I
> > used the simpler sin() method on a processor with 1K of Flash memory
> because
> > a lookup table was too large as was including the float function and
> sin(x)
> > = x wasn't accurate enough.  I limited the space to 0-90 degrees
85 as
> > that was all the accuracy I actually needed. I was already using the
> > multiply byte*byte=word library function so it worked out well and
> was easy
> > to implement.
> >
> > Regards,
> >
> > Ray
> >
> >
> > -----Original Message-----
> > From: michelqv [mailto:michel@q...]
> > Sent: Friday, 12 November 2004 7:39 AM
> > To: msp430@msp4...
> > Subject: [msp430] Re: Integer arctan calculation
> >
> >
> >
> >
> > The presenter for the Cordic algorithms was Dr. Titi Trandafir of
> > Microtrend Systems, Inc.
> > www.microtrendsys.com
> > I don't know what the copyright of the source code is (it was
> > available to all ATC participants), but I'm sure Microtrend would
be
> > willing to email it to any requester.
> > For those who don't know, the cordic routines, in the case of
trig
> > functions, use trig formulas with angles whose trig functions (tan,
> > in general) are successive negative powers of 2 (1/2, 1/4, 1/8,
> > etc...) so that by successive approximations, using only shifts and
> > adds, you can get a pretty good approximation of any trig functions.
> > The devil is in the details, as usaul.
> >
> > Michel
> >
> > --- In msp430@msp4..., Jonathan Kirwan <jkirwan@e...> wrote:
> > > On Wed, 10 Nov 2004 19:49:42 -0000, Mike wrote:
> > >
> > > >I need to do an arctan calculation from the readings of a
pair of
> > A/D
> > > >converters.
> > >
> > > Sine and cosine ADCs, I suppose.
> > >
> > > >I, of course, can use the built in arctan function with
> > > >the compiler but that takes up a lot of code space and is way
more
> > > >accurate than I need. My sin and cos values are 10 bit
numbers (0 -
> >
> > > >1023) and I need a result that is also a 10 but number. E.g.
0
> > > >degrees gives 0, pi/2 gives 256, pi gives 512, you get the
> > picture. I
> > > >have searched a lot but most routines using least squares
> > technique
> > > >give much more precision than I need. So, I don't want
to do it in
> > > >floating point just with integer math. Any suggestions?
> > >
> > > Okay, so the output is from 0 to 1023, with 0 being 0 degrees and
> > 1023 being
> > > (1023/1024)*360 or 359.65 degrees.  I have to assume here that
your
> > two 10 bit
> > > inputs aren't predivided into a single scalar input, because
if
> > they were there
> > > would be no way to produce all four quadrants in the result.
> > (Quadrant 1 and
> > > quadrant 4 are the usual returns from atan() when a single value
is
> > passed.)
> > > So, your desired function must look like:
> > >
> > >   result = arctan2( sinval, cosval )
> > >
> > > And both 'sinval' and 'cosval' must be signed
or else it isn't
> > possible to
> > > produce a 'result' that can span from 0 to 1023.
> > >
> > > Some quick observations that may help examine (or write) code.
> > >
> > > 1)  Quadrant 3 and quadrant 1 look alike and quadrant 4 and
> > quadrant 2 look
> > > alike.  This reduces the need for code from 4 quadrants to just 2
--
> >  quadrant 1
> > > and quadrant 4, for example.  You'll still need a way to
examine
> > both input
> > > values to decide whether it's in 2 or 4, or in 1 or 3, of
course.
> > But that's
> > > simple and it just means adding a PI value (512, in your angle
unit
> > terms.)
> > >
> > > 2)  Quadrant 1 and quadrant 4 can be merged by realizing that tan
-
> > x = -tan x.
> > > This folds both of these together, so you only have to deal now
> > with values
> > > representing the tangent from 0 to 90 degrees.  (0 to infinity,
> > yes, but just
> > > positive values, at least.)
> > >
> > > 3)  Quadrant 1 can now be folded in half by also realizing that
tan
> > x > > > cot(PI/2-x), which is just the same as 1/tan(PI/2-x).
 The result
> > is that arctan
> > > x = PI - arctan(1/x).  Again, just a constant away, after you
> > invert the ratio
> > > (which was originally sin/cos and now would become cos/sin for
> > calculating and
> > > afterwards with PI added.)
> > >
> > > This gets you to only having to handle ratios of your two input
> > values that are
> > > (a) positive only, and (b) where the ratio itself is <= 1. 
Only
> > angles from 0
> > > degrees to 45 degrees or just the first octant.
> > >
> > > 4)  You can go even further and realize that tan(a+b) = (tan
a +
> > tan b) / (1 -
> > > tan a * tan b) and use this to either 'rotate' your
argument a bit
> > to aid your
> > > calculating polynomial (or rational polynomial fraction) error
> > bounds or else to
> > > further fold the sections into tinier and tinier segments, with
the
> > extra cost
> > > of keeping the books.
> > >
> > > Anyway, getting back to (3) above [before worrying over (4)],
also
> > note that the
> > > tangent slope is 1/(cos a)^2.  This means the slope varies from
> > about 1:1 (at 0)
> > > to 1:2 (at 45 degrees).  The mean slope remains fairly close to
1,
> > though, at
> > > about 1.27.  Let's just call it "about 1," for
now.  A span of 45
> > degrees
> > > corresponds to about 1/8th of 1024, or 128 counts of angle.  This
> > suggests that
> > > you'd need to compute out 7 bits of your (sin/cos) fraction
with
> > one more for
> > > rounding.  (Also, if you rotate your 45 degree span by 22.5
> > degrees, between the
> > > range of -22.5 degrees to +22.5 degrees, that slope varies
from
> > about 1:1 to
> > > about 1:1.17, with an average of 1:1.05.  Even better for any
> > calculation
> > > formula you may design.)  In a perfect micro programmer world,
> > arctan x = x, but
> > > although it is close, it's not quite that simple.  (If you
choose
> > to make a 22.5
> > > degree prerotation, the ratio of x to arctan x varies from
> > about .95 to 1.00.)
> > > So, you will need to do some shift/adds after the division.  But
it
> > won't be
> > > hard to work out the details, I think.
> > >
> > > Are you able to work through the details of developing your own
> > algorithm?  I'm
> > > looking forward to seeing Michel's addition, if he can find
the
> > source and post
> > > it.
> > >
> > > Jon
> >
> >
> >
> >
> >
> >
> > .
> >
> >
> > Yahoo! Groups Links
> 
> 
> 
> 
> 
> 
> .
> 
> 
> Yahoo! Groups Links

Short answer: CORDIC

Long answer:

Here is some code that I wrote a while back to convert ADXL202 readings into
angles. It worked quite well. Input was also in 4.12 fixed point format but I
think you can feed the routine about anything you want to.

The range is limited to +/- 100 degrees. It has been a long time since I
wrote 
this so I can't remember why but this was sufficient for my application.

/*
	CORDIC arctangent routine

	returns the inverse (arc) tangent of the ratio y/x in radians

	Result is in  4.12 fixed point format.
*/

const int atantable[] 	{ 0xc91, 0x76b, 0x3eb, 0x1fd, 0x100, 0x80, 0x40, 0x20,
0x10,
	  0x8, 0x4, 0x2, 0x1, 0 };
	
int atan( int x, int y )
{
	char 	i;
	int	a, da, dx, dy;

	a = 0;
	for( i = 0; i < 12; i++ )
	{
		da = atantable[i];
		dx = x >> i;
		dy = y >> i;
		if( y > 0 )
		{
			a += da;
			x += dy;
			y -= dx;
		}
		else
		{
			a -= da;
			x -= dy;
			y += dx;
		}
	}
	return (a);
}

-- 
David W. Schultz
http://home.earthlink.net/~david.schultz

Hi Kevin,

I haven't played with the arctan version but the sin() approximation I gave
has less than 1.5% error in the 0 - 90 degrees quadrant within the maths
space I defined.

You will notice I didn't just truncate it but used it as the starting
point.
sin(x) = x -x^3/7 is a slight variation on sin(x) = x - x^3/3! + x^5/5! ...
which provided a small enough error for a low overhead of code space.

Thanks for the site reference you gave.  The specific link bombed out but
http://jove.prohosting.com/~skripty worked fine.  Lots of useful info.

Ray


-----Original Message-----
From: kevinisanonymous [mailto:kevinisanonymous@kevi...]
Sent: Friday, 12 November 2004 10:54 AM
To: msp430@msp4...
Subject: [msp430] Re: Integer arctan calculation




I know that this thread has wandered off the origional question which
was integer approximations but since it has gotten here....

Recall that a Tayor series (or rather a power series) may have VERY
poor convergence qualities for some points.  You are much better off
to use continued fractions or Pade approximants.  There are also
numerious truncated polynomials that can give you sin and cos, etc,
with relatively small error (many of these rational approximations
have degrtee <10) and error < 10-6.  Try
http://jove.prohosting.com/~skripty/page_76.html
for some examples.

DO NOT JUST TRUNCATE A TAYLOR SERIES.  You may need 200 terms to
converge within your needed accuracy.  Also I have seen the following
done and it is very dangerous,

  If abs(current term - next term) < tolerance then stop.

This will not work because although the difference is less than your
error this could add up over succesive terms and become signifigant.
If you are going to try to use a truncated taylor series (assuming it
is not a alternating series with decreasing terms which is a happy
scenearo) you must approximate the remainder.  See Taylor's Remainder
Theorem for info on this.

As far as CORDIC goes there is an abundance of info out there and I
think I have seen a TMS6x assembly port out there somewhere, which
could probably easilty be adapted to an MSP430.

Cheers,

kevin




--- In msp430@msp4..., "Raymond Keefe" <ray@b...> wrote:
> You can also use the taylors series expansion for
trig functions and
> simplify them a bit.  Use symmetry to make life easier so you only
have to
> work out one quadrant.
>
> A very good approximation of sin(x) is x - x^3/7 though x - x^3/6 +
x^5/120
> is even better.
>
> For tan() you have tan(x) = x + x^3/3 + 2x^5/15
>
> And atan(x) = x - x^3/3 + x^5/5
>
> You can truncate the accuracy and therefore the maths to suit the
need.  I
> used the simpler sin() method on a processor with
1K of Flash memory
because
> a lookup table was too large as was including the
float function and
sin(x)
> = x wasn't accurate enough.  I limited the
space to 0-90 degrees = 85 as
> that was all the accuracy I actually needed. I was already using the
> multiply byte*byte=word library function so it worked out well and
was easy
> to implement.
>
> Regards,
>
> Ray
>
>
> -----Original Message-----
> From: michelqv [mailto:michel@q...]
> Sent: Friday, 12 November 2004 7:39 AM
> To: msp430@msp4...
> Subject: [msp430] Re: Integer arctan calculation
>
>
>
>
> The presenter for the Cordic algorithms was Dr. Titi Trandafir of
> Microtrend Systems, Inc.
> www.microtrendsys.com
> I don't know what the copyright of the source code is (it was
> available to all ATC participants), but I'm sure Microtrend would be
> willing to email it to any requester.
> For those who don't know, the cordic routines, in the case of trig
> functions, use trig formulas with angles whose trig functions (tan,
> in general) are successive negative powers of 2 (1/2, 1/4, 1/8,
> etc...) so that by successive approximations, using only shifts and
> adds, you can get a pretty good approximation of any trig functions.
> The devil is in the details, as usaul.
>
> Michel
>
> --- In msp430@msp4..., Jonathan Kirwan <jkirwan@e...> wrote:
> > On Wed, 10 Nov 2004 19:49:42 -0000, Mike wrote:
> >
> > >I need to do an arctan calculation from the readings of a pair of
> A/D
> > >converters.
> >
> > Sine and cosine ADCs, I suppose.
> >
> > >I, of course, can use the built in arctan function with
> > >the compiler but that takes up a lot of code space and is way more
> > >accurate than I need. My sin and cos values are 10 bit numbers (0
-
>
> > >1023) and I need a result that is also a 10 but number. E.g. 0
> > >degrees gives 0, pi/2 gives 256, pi gives 512, you get the
> picture. I
> > >have searched a lot but most routines using least squares
> technique
> > >give much more precision than I need. So, I don't want to do
it in
> > >floating point just with integer math. Any suggestions?
> >
> > Okay, so the output is from 0 to 1023, with 0 being 0 degrees and
> 1023 being
> > (1023/1024)*360 or 359.65 degrees.  I have to assume here that your
> two 10 bit
> > inputs aren't predivided into a single scalar input, because if
> they were there
> > would be no way to produce all four quadrants in the result.
> (Quadrant 1 and
> > quadrant 4 are the usual returns from atan() when a single value is
> passed.)
> > So, your desired function must look like:
> >
> >   result = arctan2( sinval, cosval )
> >
> > And both 'sinval' and 'cosval' must be signed or
else it isn't
> possible to
> > produce a 'result' that can span from 0 to 1023.
> >
> > Some quick observations that may help examine (or write) code.
> >
> > 1)  Quadrant 3 and quadrant 1 look alike and quadrant 4 and
> quadrant 2 look
> > alike.  This reduces the need for code from 4 quadrants to just 2 --
>  quadrant 1
> > and quadrant 4, for example.  You'll still need a way to examine
> both input
> > values to decide whether it's in 2 or 4, or in 1 or 3, of course.
> But that's
> > simple and it just means adding a PI value (512, in your angle unit
> terms.)
> >
> > 2)  Quadrant 1 and quadrant 4 can be merged by realizing that tan -
> x = -tan x.
> > This folds both of these together, so you only have to deal now
> with values
> > representing the tangent from 0 to 90 degrees.  (0 to infinity,
> yes, but just
> > positive values, at least.)
> >
> > 3)  Quadrant 1 can now be folded in half by also realizing that tan
> x > > cot(PI/2-x), which is just the same as 1/tan(PI/2-x).  The
result
> is that arctan
> > x = PI - arctan(1/x).  Again, just a constant away, after you
> invert the ratio
> > (which was originally sin/cos and now would become cos/sin for
> calculating and
> > afterwards with PI added.)
> >
> > This gets you to only having to handle ratios of your two input
> values that are
> > (a) positive only, and (b) where the ratio itself is <= 1.  Only
> angles from 0
> > degrees to 45 degrees or just the first octant.
> >
> > 4)  You can go even further and realize that tan(a+b) = (tan a +
> tan b) / (1 -
> > tan a * tan b) and use this to either 'rotate' your argument
a bit
> to aid your
> > calculating polynomial (or rational polynomial fraction) error
> bounds or else to
> > further fold the sections into tinier and tinier segments, with the
> extra cost
> > of keeping the books.
> >
> > Anyway, getting back to (3) above [before worrying over (4)], also
> note that the
> > tangent slope is 1/(cos a)^2.  This means the slope varies from
> about 1:1 (at 0)
> > to 1:2 (at 45 degrees).  The mean slope remains fairly close to 1,
> though, at
> > about 1.27.  Let's just call it "about 1," for now.  A
span of 45
> degrees
> > corresponds to about 1/8th of 1024, or 128 counts of angle.  This
> suggests that
> > you'd need to compute out 7 bits of your (sin/cos) fraction with
> one more for
> > rounding.  (Also, if you rotate your 45 degree span by 22.5
> degrees, between the
> > range of -22.5 degrees to +22.5 degrees, that slope varies from
> about 1:1 to
> > about 1:1.17, with an average of 1:1.05.  Even better for any
> calculation
> > formula you may design.)  In a perfect micro programmer world,
> arctan x = x, but
> > although it is close, it's not quite that simple.  (If you choose
> to make a 22.5
> > degree prerotation, the ratio of x to arctan x varies from
> about .95 to 1.00.)
> > So, you will need to do some shift/adds after the division.  But it
> won't be
> > hard to work out the details, I think.
> >
> > Are you able to work through the details of developing your own
> algorithm?  I'm
> > looking forward to seeing Michel's addition, if he can find the
> source and post
> > it.
> >
> > Jon
>
>
>
>
>
>
> .
>
>
> Yahoo! Groups Links






.


Yahoo! Groups Links

I know that this thread has wandered off the origional question which
was integer approximations but since it has gotten here....

Recall that a Tayor series (or rather a power series) may have VERY
poor convergence qualities for some points.  You are much better off
to use continued fractions or Pade approximants.  There are also
numerious truncated polynomials that can give you sin and cos, etc,
with relatively small error (many of these rational approximations
have degrtee <10) and error < 10-6.  Try
http://jove.prohosting.com/~skripty/page_76.html 
for some examples.

DO NOT JUST TRUNCATE A TAYLOR SERIES.  You may need 200 terms to
converge within your needed accuracy.  Also I have seen the following
done and it is very dangerous,

  If abs(current term - next term) < tolerance then stop.

This will not work because although the difference is less than your
error this could add up over succesive terms and become signifigant.
If you are going to try to use a truncated taylor series (assuming it
is not a alternating series with decreasing terms which is a happy
scenearo) you must approximate the remainder.  See Taylor's Remainder
Theorem for info on this. 

As far as CORDIC goes there is an abundance of info out there and I
think I have seen a TMS6x assembly port out there somewhere, which
could probably easilty be adapted to an MSP430.

Cheers,

kevin
   



--- In msp430@msp4..., "Raymond Keefe" <ray@b...> wrote:
> You can also use the taylors series expansion for
trig functions and
> simplify them a bit.  Use symmetry to make life easier so you only
have to
> work out one quadrant.
> 
> A very good approximation of sin(x) is x - x^3/7 though x - x^3/6 +
x^5/120
> is even better.
> 
> For tan() you have tan(x) = x + x^3/3 + 2x^5/15
> 
> And atan(x) = x - x^3/3 + x^5/5
> 
> You can truncate the accuracy and therefore the maths to suit the
need.  I
> used the simpler sin() method on a processor with
1K of Flash memory
because
> a lookup table was too large as was including the
float function and
sin(x)
> = x wasn't accurate enough.  I limited the
space to 0-90 degrees = 85 as
> that was all the accuracy I actually needed. I was already using the
> multiply byte*byte=word library function so it worked out well and
was easy
> to implement.
> 
> Regards,
> 
> Ray
> 
> 
> -----Original Message-----
> From: michelqv [mailto:michel@q...]
> Sent: Friday, 12 November 2004 7:39 AM
> To: msp430@msp4...
> Subject: [msp430] Re: Integer arctan calculation
> 
> 
> 
> 
> The presenter for the Cordic algorithms was Dr. Titi Trandafir of
> Microtrend Systems, Inc.
> www.microtrendsys.com
> I don't know what the copyright of the source code is (it was
> available to all ATC participants), but I'm sure Microtrend would be
> willing to email it to any requester.
> For those who don't know, the cordic routines, in the case of trig
> functions, use trig formulas with angles whose trig functions (tan,
> in general) are successive negative powers of 2 (1/2, 1/4, 1/8,
> etc...) so that by successive approximations, using only shifts and
> adds, you can get a pretty good approximation of any trig functions.
> The devil is in the details, as usaul.
> 
> Michel
> 
> --- In msp430@msp4..., Jonathan Kirwan <jkirwan@e...> wrote:
> > On Wed, 10 Nov 2004 19:49:42 -0000, Mike wrote:
> >
> > >I need to do an arctan calculation from the readings of a pair of
> A/D
> > >converters.
> >
> > Sine and cosine ADCs, I suppose.
> >
> > >I, of course, can use the built in arctan function with
> > >the compiler but that takes up a lot of code space and is way more
> > >accurate than I need. My sin and cos values are 10 bit numbers (0
-
> 
> > >1023) and I need a result that is also a 10 but number. E.g. 0
> > >degrees gives 0, pi/2 gives 256, pi gives 512, you get the
> picture. I
> > >have searched a lot but most routines using least squares
> technique
> > >give much more precision than I need. So, I don't want to do
it in
> > >floating point just with integer math. Any suggestions?
> >
> > Okay, so the output is from 0 to 1023, with 0 being 0 degrees and
> 1023 being
> > (1023/1024)*360 or 359.65 degrees.  I have to assume here that your
> two 10 bit
> > inputs aren't predivided into a single scalar input, because if
> they were there
> > would be no way to produce all four quadrants in the result.
> (Quadrant 1 and
> > quadrant 4 are the usual returns from atan() when a single value is
> passed.)
> > So, your desired function must look like:
> >
> >   result = arctan2( sinval, cosval )
> >
> > And both 'sinval' and 'cosval' must be signed or
else it isn't
> possible to
> > produce a 'result' that can span from 0 to 1023.
> >
> > Some quick observations that may help examine (or write) code.
> >
> > 1)  Quadrant 3 and quadrant 1 look alike and quadrant 4 and
> quadrant 2 look
> > alike.  This reduces the need for code from 4 quadrants to just 2 --
>  quadrant 1
> > and quadrant 4, for example.  You'll still need a way to examine
> both input
> > values to decide whether it's in 2 or 4, or in 1 or 3, of course.
> But that's
> > simple and it just means adding a PI value (512, in your angle unit
> terms.)
> >
> > 2)  Quadrant 1 and quadrant 4 can be merged by realizing that tan -
> x = -tan x.
> > This folds both of these together, so you only have to deal now
> with values
> > representing the tangent from 0 to 90 degrees.  (0 to infinity,
> yes, but just
> > positive values, at least.)
> >
> > 3)  Quadrant 1 can now be folded in half by also realizing that tan
> x > > cot(PI/2-x), which is just the same as 1/tan(PI/2-x).  The
result
> is that arctan
> > x = PI - arctan(1/x).  Again, just a constant away, after you
> invert the ratio
> > (which was originally sin/cos and now would become cos/sin for
> calculating and
> > afterwards with PI added.)
> >
> > This gets you to only having to handle ratios of your two input
> values that are
> > (a) positive only, and (b) where the ratio itself is <= 1.  Only
> angles from 0
> > degrees to 45 degrees or just the first octant.
> >
> > 4)  You can go even further and realize that tan(a+b) = (tan a +
> tan b) / (1 -
> > tan a * tan b) and use this to either 'rotate' your argument
a bit
> to aid your
> > calculating polynomial (or rational polynomial fraction) error
> bounds or else to
> > further fold the sections into tinier and tinier segments, with the
> extra cost
> > of keeping the books.
> >
> > Anyway, getting back to (3) above [before worrying over (4)], also
> note that the
> > tangent slope is 1/(cos a)^2.  This means the slope varies from
> about 1:1 (at 0)
> > to 1:2 (at 45 degrees).  The mean slope remains fairly close to 1,
> though, at
> > about 1.27.  Let's just call it "about 1," for now.  A
span of 45
> degrees
> > corresponds to about 1/8th of 1024, or 128 counts of angle.  This
> suggests that
> > you'd need to compute out 7 bits of your (sin/cos) fraction with
> one more for
> > rounding.  (Also, if you rotate your 45 degree span by 22.5
> degrees, between the
> > range of -22.5 degrees to +22.5 degrees, that slope varies from
> about 1:1 to
> > about 1:1.17, with an average of 1:1.05.  Even better for any
> calculation
> > formula you may design.)  In a perfect micro programmer world,
> arctan x = x, but
> > although it is close, it's not quite that simple.  (If you choose
> to make a 22.5
> > degree prerotation, the ratio of x to arctan x varies from
> about .95 to 1.00.)
> > So, you will need to do some shift/adds after the division.  But it
> won't be
> > hard to work out the details, I think.
> >
> > Are you able to work through the details of developing your own
> algorithm?  I'm
> > looking forward to seeing Michel's addition, if he can find the
> source and post
> > it.
> >
> > Jon
> 
> 
> 
> 
> 
> 
> .
> 
> 
> Yahoo! Groups Links

Jonathan Kirwan wrote:

> On Thu, 11 Nov 2004 20:39:18 -0000, you wrote:
> 
> 
>>The presenter for the Cordic algorithms was Dr. Titi Trandafir of 
>>Microtrend Systems, Inc.
>>www.microtrendsys.com
>>I don't know what the copyright of the source code is (it was 
>>available to all ATC participants), but I'm sure Microtrend would
be 
>>willing to email it to any requester.
>>For those who don't know, the cordic routines, in the case of trig 
>>functions, use trig formulas with angles whose trig functions (tan, 
>>in general) are successive negative powers of 2 (1/2, 1/4, 1/8, 
>>etc...) so that by successive approximations, using only shifts and 
>>adds, you can get a pretty good approximation of any trig functions.
> 
> 
> If someone does bother to write them and get source and if they also take
the
> time to ask if it is okay to post it here and they grant that permission,
please
> *do* post what you are allowed to post!  I'd be interested, for one.
> 
> 
>>The devil is in the details, as usaul.
> 
> 
> Wouldn't it be nice if we could just imagine some general approaches
or thrusts
> in direction and the computer would just know what we were addressing and
then
> 'fill in the devilish details' for us?
> 
> Now... *THAT* would be a compiler!

Boring as all hell though!

Al

On Fri, 12 Nov 2004 08:47:34 +1100, you wrote:

>You can also use the taylors series expansion for
trig functions and
>simplify them a bit.  Use symmetry to make life easier so you only have to
>work out one quadrant.
>
>A very good approximation of sin(x) is x - x^3/7 though x - x^3/6 + x^5/120
>is even better.
>
>For tan() you have tan(x) = x + x^3/3 + 2x^5/15
>
>And atan(x) = x - x^3/3 + x^5/5
>
>You can truncate the accuracy and therefore the maths to suit the need.  I
>used the simpler sin() method on a processor with 1K of Flash memory because
>a lookup table was too large as was including the float function and sin(x)
>= x wasn't accurate enough.  I limited the space to 0-90 degrees = 85
as
>that was all the accuracy I actually needed. I was already using the
>multiply byte*byte=word library function so it worked out well and was easy
>to implement.

Actually, Taylor's expansion is notoriously poor at convergence with regard
to
arctan(x).  No one in their right mind uses it for computing arctan(x).  This is
quite in contrast against the series expansion for sin x which is:

  sin(x) = x - x^3/3! + x^5/5! - ...

Note the key difference here which aids convergence for sin(x) (the factorials.)
Also, the Taylor's error term (the next element of the sequence) gives an
idea
of average error but does not bound maximum error, as might chebychev.  An easy
improvement on the Taylor's with alternating signed terms is to add in only
1/2
of the last term.  Since it is oscillating above and below, this in effect
shoots for the middle and often helps.

But try computing the Taylor's series for arctan(1.0).  Print out the sum
for a
varying number of terms and watch how miserably it converges in this particular
case.  It's not pretty.

Jon

You can also use the taylors series expansion for trig functions and
simplify them a bit.  Use symmetry to make life easier so you only have to
work out one quadrant.

A very good approximation of sin(x) is x - x^3/7 though x - x^3/6 + x^5/120
is even better.

For tan() you have tan(x) = x + x^3/3 + 2x^5/15

And atan(x) = x - x^3/3 + x^5/5

You can truncate the accuracy and therefore the maths to suit the need.  I
used the simpler sin() method on a processor with 1K of Flash memory because
a lookup table was too large as was including the float function and sin(x)
= x wasn't accurate enough.  I limited the space to 0-90 degrees = 85 as
that was all the accuracy I actually needed. I was already using the
multiply byte*byte=word library function so it worked out well and was easy
to implement.

Regards,

Ray


-----Original Message-----
From: michelqv [mailto:michel@mich...]
Sent: Friday, 12 November 2004 7:39 AM
To: msp430@msp4...
Subject: [msp430] Re: Integer arctan calculation




The presenter for the Cordic algorithms was Dr. Titi Trandafir of
Microtrend Systems, Inc.
www.microtrendsys.com
I don't know what the copyright of the source code is (it was
available to all ATC participants), but I'm sure Microtrend would be
willing to email it to any requester.
For those who don't know, the cordic routines, in the case of trig
functions, use trig formulas with angles whose trig functions (tan,
in general) are successive negative powers of 2 (1/2, 1/4, 1/8,
etc...) so that by successive approximations, using only shifts and
adds, you can get a pretty good approximation of any trig functions.
The devil is in the details, as usaul.

Michel

--- In msp430@msp4..., Jonathan Kirwan <jkirwan@e...> wrote:
> On Wed, 10 Nov 2004 19:49:42 -0000, Mike wrote:
>
> >I need to do an arctan calculation from the readings of a pair of
A/D
> >converters.
>
> Sine and cosine ADCs, I suppose.
>
> >I, of course, can use the built in arctan function with
> >the compiler but that takes up a lot of code space and is way more
> >accurate than I need. My sin and cos values are 10 bit numbers (0 -

> >1023) and I need a result that is also a 10
but number. E.g. 0
> >degrees gives 0, pi/2 gives 256, pi gives 512, you get the
picture. I
> >have searched a lot but most routines using
least squares
technique
> >give much more precision than I need. So, I
don't want to do it in
> >floating point just with integer math. Any suggestions?
>
> Okay, so the output is from 0 to 1023, with 0 being 0 degrees and
1023 being
> (1023/1024)*360 or 359.65 degrees.  I have to
assume here that your
two 10 bit
> inputs aren't predivided into a single scalar
input, because if
they were there
> would be no way to produce all four quadrants in
the result.
(Quadrant 1 and
> quadrant 4 are the usual returns from atan() when
a single value is
passed.)
> So, your desired function must look like:
>
>   result = arctan2( sinval, cosval )
>
> And both 'sinval' and 'cosval' must be signed or else
it isn't
possible to
> produce a 'result' that can span from 0
to 1023.
>
> Some quick observations that may help examine (or write) code.
>
> 1)  Quadrant 3 and quadrant 1 look alike and quadrant 4 and
quadrant 2 look
> alike.  This reduces the need for code from 4
quadrants to just 2 --
 quadrant 1
> and quadrant 4, for example.  You'll still
need a way to examine
both input
> values to decide whether it's in 2 or 4, or
in 1 or 3, of course.
But that's
> simple and it just means adding a PI value (512,
in your angle unit
terms.)
>
> 2)  Quadrant 1 and quadrant 4 can be merged by realizing that tan -
x = -tan x.
> This folds both of these together, so you only
have to deal now
with values
> representing the tangent from 0 to 90 degrees.  (0
to infinity,
yes, but just
> positive values, at least.)
>
> 3)  Quadrant 1 can now be folded in half by also realizing that tan
x > cot(PI/2-x), which is just the same as 1/tan(PI/2-x).  The result
is that arctan
> x = PI - arctan(1/x).  Again, just a constant
away, after you
invert the ratio
> (which was originally sin/cos and now would become
cos/sin for
calculating and
> afterwards with PI added.)
>
> This gets you to only having to handle ratios of your two input
values that are
> (a) positive only, and (b) where the ratio itself
is <= 1.  Only
angles from 0
> degrees to 45 degrees or just the first octant.
>
> 4)  You can go even further and realize that tan(a+b) = (tan a +
tan b) / (1 -
> tan a * tan b) and use this to either
'rotate' your argument a bit
to aid your
> calculating polynomial (or rational polynomial
fraction) error
bounds or else to
> further fold the sections into tinier and tinier
segments, with the
extra cost
> of keeping the books.
>
> Anyway, getting back to (3) above [before worrying over (4)], also
note that the
> tangent slope is 1/(cos a)^2.  This means the
slope varies from
about 1:1 (at 0)
> to 1:2 (at 45 degrees).  The mean slope remains
fairly close to 1,
though, at
> about 1.27.  Let's just call it "about
1," for now.  A span of 45
degrees
> corresponds to about 1/8th of 1024, or 128 counts
of angle.  This
suggests that
> you'd need to compute out 7 bits of your
(sin/cos) fraction with
one more for
> rounding.  (Also, if you rotate your 45 degree
span by 22.5
degrees, between the
> range of -22.5 degrees to +22.5 degrees, that
slope varies from
about 1:1 to
> about 1:1.17, with an average of 1:1.05.  Even
better for any
calculation
> formula you may design.)  In a perfect micro
programmer world,
arctan x = x, but
> although it is close, it's not quite that
simple.  (If you choose
to make a 22.5
> degree prerotation, the ratio of x to arctan x
varies from
about .95 to 1.00.)
> So, you will need to do some shift/adds after the
division.  But it
won't be
> hard to work out the details, I think.
>
> Are you able to work through the details of developing your own
algorithm?  I'm
> looking forward to seeing Michel's addition,
if he can find the
source and post
> it.
>
> Jon






.


Yahoo! Groups Links

Beginning Microcontrollers with the MSP430