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
Integer arctan calculation
Started by ●November 10, 2004
Reply by ●November 11, 20042004-11-11
Reply by ●November 11, 20042004-11-11
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
Reply by ●November 11, 20042004-11-11
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
Reply by ●November 11, 20042004-11-11
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
Reply by ●November 11, 20042004-11-11
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
Reply by ●November 11, 20042004-11-11
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
Reply by ●November 11, 20042004-11-11
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
Reply by ●November 11, 20042004-11-11
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
Reply by ●November 12, 20042004-11-12
On Thu, 11 Nov 2004 23:53:44 -0000, Kevin who is anonymous wrote: >I know that this thread has wandered off the origional question which >was integer approximations but since it has gotten here.... Actually, I never imagined for a moment that any good discussion about real number algorithms is necessarily wandering off the topic of integer-in and integer-out functions. A good understanding of the real number valued function very likely will help for an integer-based algorithm. Sometimes, it takes a little more (like generating functions and hypergeometric functions or differential operators and the z-transform.) But I don't imagine it is off-track that much. >Recall that a Tayor series (or rather a power series) may have VERY >poor convergence qualities for some points. Looks like we said about the same thing. If two of us say it, then maybe it is true. ;) >You are much better off to use continued fractions Exactly. In fact, that's what I've used in the past for arctan with good results. That, and minimax to assign 'better' coefficients. >or Pade approximants. This one is new to me. At least, the term 'Pade.' I'll have to look it up. Thanks! >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. ><snip of the rest> That didn't take with my IE browser. (On this machine, I keep a vanilla O/S without adding any absolutely necessary software. So no other browsers are added, just now.) That link bounced me to free.prohosting.com and to several other related links ultimately offering me their services. So I switched to: http://jove.prohosting.com/~skripty/page_76.htm and that worked. So did this, for the entire book: http://jove.prohosting.com/~skripty/frameindex.htm Thanks for the link! I had no idea it was there! Jon