« previous next »
Pages: [1]   Go Down

Author Topic: Estimating Functions  (Read 7543 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
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*x
a=(y<<1)+9
b=(y<<2)+y+9
return a*x/b


multiply : 2
Divide   : 1
add      : 3
sub      : 0
shift    : 3
« Last Edit: November 10, 2013, 08:01:14 am by Xeda112358 »
Logged
+2/-0 karm for this message

Offline Streetwalrus

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

Offline Adriweb

  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1708
  • Rating: +229/-17
    • View Profile
    • TI-Planet.org
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 ... :D)
Logged
My calculator programs
TI-Planet.org co-admin.
TI-Nspire Lua programming : Tutorials  |  API Documentation

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
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.

Logged

Offline Adriweb

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

Offline Sorunome

  • Fox Fox Fox Fox Fox Fox Fox!
  • Support Staff
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 7920
  • Rating: +374/-13
  • Derpy Hooves
    • View Profile
    • My website! (You might lose the game)
Re: Estimating ArcTangent
« Reply #5 on: October 28, 2013, 10:34:40 am »
xeda, you and your dark magic....
* Sorunome hides
Logged

THE GAME
Also, check out my website
If OmnomIRC is screwed up, blame me!
Click here to give me an internet!

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
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.
Logged

Offline harold

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 226
  • Rating: +41/-3
    • View Profile
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.
Logged
Blog about bitmath: bitmath.blogspot.nl
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
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).
Logged

Offline ElementCoder

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 611
  • Rating: +42/-2
    • View Profile
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) ?
Logged

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

Offline Xeda112358

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

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
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).
Logged
+2/-0 karm for this message

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
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 »
Logged
Pages: [1]   Go Up
« previous next »