### Author Topic: Estimating Functions  (Read 4951 times)

0 Members and 1 Guest are viewing this topic.

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4687
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Estimating Functions
« on: October 28, 2013, 09:38:46 am »
EDIT: To understand the method, see this document.
For simple formulas:

arctan(x) : (9x+2x3)/(9+5x2) (at least 10 bits on [-1,1] use atan(x)=pi/2-atan(1/x) to extend to the whole real line)
ln(x+1)   : x(8+x)/(8+5x)   (at least 9 bits on [0,1])

A while ago, I mentioned a nice formula that I derived for estimating arctangent to within 10 bits of accuracy on [-1,1] (so within 1/1024 of the actual arctan function). I really like it because it is so simple and short, and requires few math operations for such accuracy:
(9x+2x3)/(9+5x2)

You can get away with using the following operations:
Code: [Select]
y=x*xa=(y<<1)+9b=(y<<2)+y+9return a*x/bmultiply : 2Divide   : 1add      : 3sub      : 0shift    : 3
« Last Edit: November 10, 2013, 08:01:14 am by Xeda112358 »

#### Streetwalrus

• LV12 Extreme Poster (Next: 5000)
• Posts: 3821
• Rating: +80/-8
##### Re: Estimating ArcTangent
« Reply #1 on: October 28, 2013, 09:49:26 am »
Wow that's some nice optimization you pulled off here Xeda.

• Editor
• LV10 31337 u53r (Next: 2000)
• Posts: 1708
• Rating: +229/-17
##### Re: Estimating ArcTangent
« Reply #2 on: October 28, 2013, 09:57:53 am »
Indeed, pretty cool

Came from series expansion ?
(I'm too lazy to reverse-engineer the formula ... )
My calculator programs
TI-Nspire Lua programming : Tutorials  |  API Documentation

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4687
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Estimating ArcTangent
« Reply #3 on: October 28, 2013, 10:09:23 am »
Actually, series expansions like Taylor series are really not good for arctangent (and ln()). Instead, I used a few terms for the continued fraction of arctangent and then I adjusted values to account for the error in the rest of the terms not included. So basically:
x/(1+x2/(3+4x2))
(next term in the continued fraction divides by 5+?, so I use x2 instead of 4x2)
x/(1+x2/(3+x2))
=x/((3+2x2)/(3+x2))
=x(3+x2)/(3+2x2)
=(9x+3x3)/(9+6x2)=f(x)

From there, I leave the constants the same (9 and 9) because those should be the same in the numerator and denominator (as x→0, this makes f(x)→x which is best for series expansion of arctangent around 0). Then I just adjusted the other two coefficients. It is possible that there are even better approximations using different numbers, too.

• Editor
• LV10 31337 u53r (Next: 2000)
• Posts: 1708
• Rating: +229/-17
##### Re: Estimating ArcTangent
« Reply #4 on: October 28, 2013, 10:12:48 am »
Ah, I see, nice
My calculator programs
TI-Nspire Lua programming : Tutorials  |  API Documentation

#### Sorunome

• Fox Fox Fox Fox Fox Fox Fox!
• Support Staff
• LV13 Extreme Addict (Next: 9001)
• Posts: 7920
• Rating: +374/-13
• Derpy Hooves
##### Re: Estimating ArcTangent
« Reply #5 on: October 28, 2013, 10:34:40 am »
xeda, you and your dark magic....
* Sorunome hides
 THE GAMEAlso, check out my websiteIf OmnomIRC is screwed up, blame me!Click here to give me an internet!

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4687
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Estimating ArcTangent
« Reply #6 on: October 28, 2013, 10:36:46 am »
That's okay, I plan to *try* to extend the precision much further than on [-1,1] and as well I want to try to make closer approximations. Currently, this is better than my CORDIC implementations for 24-bit floats.

#### harold

• Posts: 226
• Rating: +41/-3
##### Re: Estimating ArcTangent
« Reply #7 on: October 28, 2013, 11:36:14 am »
Using atan(x)=pi/2-atan(1/x), it extends very nicely.
For example,
Code: [Select]
/ (9x+3x^3)/(9+6x^2)                        [if x <= 1]\ pi/2 - (9x+3a^3)/(9+6a^2) (where a = 1/x) [otherwise]The biggest error is about 0.014, at x=1. See here
I don't have any clever ideas to fix that, though.
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4687
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Estimating ArcTangent
« Reply #8 on: October 28, 2013, 01:05:47 pm »
Well, remember that (9x+3x^3)/(9+6x^2) is not the end of the modification (see the first post for the best fit dealing with 9 as the first coefficients).

To arrive to the estimation of (9x+2x3)/(9+52), you can observe that atan(1)=pi/4. Since 22/7 is a good approximation of pi, 11/14 is a good approximation of atan(1).

From here, you can guess the coefficients so that at x=1, (9+a)/(9+b)=11/24 and you get a=2, b=5

Using this, the biggest error is around .00065.

I am trying to get a formula of the form (ax+bx3)/(a+cx2+dx4) using the ratio of 353/452 to approximate atan(1).

#### ElementCoder

• LV7 Elite (Next: 700)
• Posts: 611
• Rating: +42/-2
##### Re: Estimating ArcTangent
« Reply #9 on: October 28, 2013, 01:39:45 pm »
So this has been brought up in IRC but no-one said it here yet: shouldn't a=(y<<1)+x+(x<<3) be a=(y<<1)*x+x+(x<<3) ?

Some people need a high five in the face... with a chair.
~EC

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4687
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Estimating ArcTangent
« Reply #10 on: October 28, 2013, 03:37:07 pm »
Ah, yes, good catch I modified it a little more and it is actually in a better situation

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4687
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Estimating ArcTangent
« Reply #11 on: October 31, 2013, 01:10:42 pm »
Between yesterday and this morning, I have formulated a more sound process for coming up with these formulas. For more information, I made a document here. (I am still modifying it and checking it for accuracy, otherwise, I would upload it, too).

As a result of yesterday's ventures, I managed to avoid the guess 'n check method and derive a formula for 13-bits of accuracy. It only requires one more multiplication, too:

(240x+115x3)/(240+195x2+17x4)

However, this is less suitable when using 8.8 fixed point math than the previous (then again, if you are using 8.8 fixed point, you probably won't need 13-bits of accuracy).

#### Xeda112358

• they/them
• Moderator
• LV12 Extreme Poster (Next: 5000)
• Posts: 4687
• Rating: +718/-6
• Calc-u-lator, do doo doo do do do.
##### Re: Estimating Functions
« Reply #12 on: November 10, 2013, 08:03:47 am »
Applying the same method to ln(1+x), there is a similar formula to that of atan that is also simple and requires one less multiplication and one less shift for 9 bits of accuracy on [1,2]

EDIT: See the first post for the function.
« Last Edit: November 10, 2013, 08:04:10 am by Xeda112358 »