I need to do an arctan calculation from the readings of a pair of A/D 
converters. 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? Thanks.
Mike 

----- Original Message ----- 
From: "Mike Unger" <munger@mung...>
To: <msp430@msp4...>
Sent: Wednesday, November 10, 2004 7:49 PM
Subject: [msp430] Integer arctan calculation


>
>
> I need to do an arctan calculation from the readings of a pair of A/D
> converters. 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? Thanks.

Look-up table? Faster than using the built-in function and might take up 
less space.

Leon 

Mike Unger wrote:
> 
> I need to do an arctan calculation from the readings of a pair of A/D 
> converters. 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? Thanks.
> Mike 
> 

Mike,

Don't know if this will help but Scott Dattalo has a web page describing 
an implementation of an arctan function using a lookup table and linear 
interpolation. It's in PIC assembly but he has some pseudo-code that 
should be easy to translate. Here's the link:

http://www.dattalo.com/technical/software/pic/arctan.asm

Hope this helps,

Greg

If you're using one of the larger memory devices a look up table will
be 
fastest, and most accurate. You only need to cover 90 degrees, which is 
8 bits of your 10 bit value, the two MSB's simply define which quadrant 
the result is in, thus 256 entries at 1 word each uses a single segment 
of memory. Not bad, since any high level language routine will probably 
consume more memory than this. failing that, if you can't afford the 
memory for a full look up table you can compromise. it's crude, but you 
don't need accuracy you say. So divide the 90 degrees into 16 segments, 
to give a coarse resolution of 5.675 degrees, then calculate the mean 
slope between each segment and store this separately. In this way you 
need only 32 values stored, 16 coarse values and 16 slope values, this 
will require a single MAC but should fit in under 80 bytes of code.

Al

Mike Unger wrote:
> 
> I need to do an arctan calculation from the readings of a pair of A/D 
> converters. 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? Thanks.
> Mike 
> 
> 
> 
> 
> 
> 
> 
> .
> 
>  
> Yahoo! Groups Links
> 
> 
> 
>  
> 
> 
> 
> 

There was an interesting presentation of cordic algorithms at the TI 
ATC here in Dallas this morning. No multiplication required, just 
shifts and a lookup table. The presenter gives a free source for one 
cordic algorithm in the ATC book. I forget the name of the company 
now, but I'll post it tomorrow, if anybody's interested.

Michel

--- In msp430@msp4..., onestone <onestone@b...> wrote:
> If you're using one of the larger memory
devices a look up table 
will be 
> fastest, and most accurate. You only need to cover
90 degrees, 
which is 
> 8 bits of your 10 bit value, the two MSB's
simply define which 
quadrant 
> the result is in, thus 256 entries at 1 word each
uses a single 
segment 
> of memory. Not bad, since any high level language
routine will 
probably 
> consume more memory than this. failing that, if
you can't afford 
the 
> memory for a full look up table you can
compromise. it's crude, but 
you 
> don't need accuracy you say. So divide the 90
degrees into 16 
segments, 
> to give a coarse resolution of 5.675 degrees, then
calculate the 
mean 
> slope between each segment and store this
separately. In this way 
you 
> need only 32 values stored, 16 coarse values and
16 slope values, 
this 
> will require a single MAC but should fit in under
80 bytes of code.
> 
> Al
> 
> Mike Unger wrote:
> > 
> > I need to do an arctan calculation from the readings of a pair of 
A/D 
> > converters. 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? Thanks.
> > Mike 
> > 
> > 
> > 
> > 
> > 
> > 
> > 
> > .
> > 
> >  
> > Yahoo! Groups Links
> > 
> > 
> > 
> >  
> > 
> > 
> > 
> >

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

On Thu, 11 Nov 2004 09:13:56 -0800, I wrote:

>inputs aren't predivided into a single scalar
input, because if they were there

I meant to write:

>inputs aren't predivided into a single scalar
input, because if they
>__weren't__ there

Jon

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

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!

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