Author Topic: Approximating inverse trigonometric functions  (Read 4820 times)

0 Members and 1 Guest are viewing this topic.

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Approximating inverse trigonometric functions
« on: November 21, 2013, 07:43:26 am »
Hey guys,

I wanted to use cos-1 for a spherical mapping, but since it doesn't exist in Axe, I had to approximate it :P

So here's the thing : cos-1 =

Okay I'll explain that ;D

So I did it in a non-fonctionnal way, thus with an algorithm. Basically, it takes a parameter in the range [-128,128] and returns the corresponding cos/sin -compatible angle (between 0 and 256 inclusive).
  • First, if |x| is lesser than 89 (I took that value from a graphed cos-1) :
  • Else :
  • If x > 0, we substract the result from 128.
And amazingly, that gives us an approximation with an error range of only 1 ! :D

If someone could graph the thing, Wolfram doesn't seem to be capable of that.

So here's the Axe code as I did it :

:Lbl ArcCos
:~abs(r1)→r2
:If r2>>~89
:~r2//3+64
:Else
:128-sqrt(r2+128*30)
:End
:→r2
:r1ee0??128-r2→r2
:r2
:Return


Exactly 255 bytes in Noshell, isn't that beautiful ;D

I'm working on sin-1 as well, so expect it for in a few hours.
« Last Edit: November 21, 2013, 07:44:08 am by Matrefeytontias »

Offline Adriweb

  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1708
  • Rating: +229/-17
    • View Profile
    • TI-Planet.org
Re: Approximating inverse trigonometric functions
« Reply #1 on: November 21, 2013, 08:32:59 am »
Hmmm what am I missing ?



(yeah acos1 is acos, don't worry :P)
« Last Edit: November 21, 2013, 08:33:34 am by adriweb »
My calculator programs
TI-Planet.org co-admin.
TI-Nspire Lua programming : Tutorials  |  API Documentation

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: Approximating inverse trigonometric functions
« Reply #2 on: November 21, 2013, 08:34:50 am »
Basically, it takes a parameter in the range [-128,128] and returns the corresponding cos/sin -compatible angle (between 0 and 256 inclusive)
This is meant to be used in Axe only, so it works with integers between -128 and 128 and outputs integers between -128 and 128. That's why it's in the Axe subforum.

To have a proper comparison, you should use this as a reference cos-1 :

cos-1(x / 128) * 128 / pi
« Last Edit: November 21, 2013, 08:36:30 am by Matrefeytontias »

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: Approximating inverse trigonometric functions
« Reply #3 on: November 21, 2013, 08:44:49 am »
Wow, nice! How well does it work near the end points? I was just going to compute asin() and acos() from atan().

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: Approximating inverse trigonometric functions
« Reply #4 on: November 21, 2013, 08:46:11 am »
Taking care of the accuracy at the end points is the purpose of segmenting the function, so that the square roots gives the right curve to the function. It has an error margin of 1 everywhere on the curve.
« Last Edit: November 21, 2013, 08:46:34 am by Matrefeytontias »

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: Approximating inverse trigonometric functions
« Reply #5 on: November 21, 2013, 09:30:06 am »
Cool, I got it to work and that is nice! If you check out this:
http://en.wikipedia.org/wiki/Inverse_trigonometric_functions#Relationships_among_the_inverse_trigonometric_functions

You can get a representation of arccos with arctangent, and on [-1,1] it becomes 2tan-1(sqrt((1-x)/(1+x)). You can probably modify it to work with the Axe atan() command.

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: Approximating inverse trigonometric functions
« Reply #6 on: November 21, 2013, 11:58:03 am »
Bad idea, that would only be slower, weighter and not even more accurate due to Axe's precision.

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: Approximating inverse trigonometric functions
« Reply #7 on: November 21, 2013, 08:07:02 pm »
[rambling]
Yeah, after analysing, the method I gave uses one less multiplication than yours, the same number of divisions and square roots. However, mine also uses arctangent, and arctangent is slower than the saved multiplication, so in all, my routine would be slower. In assembly, I could optimise the division in both cases, but your multiplication would be trivial and fast whereas my square root would be faster than yours (only 8 bits of precision would be needed).
[/rambling]

Anyways, after looking at the graph, there are actually a few values that are off by a little more than 1, but that is still very accurate and excellent. If you need speed, though, you probably already know that table methods are great. In fact, you can use the fact that it is basically linear from [-89,89] to make only a table from 90 to 128 and they only need to be 1 byte. Here is a routine that gets exact rounded values (111 bytes):
Code: [Select]
acos:
;Input:
;    L is the signed int from [-128,127] where -128 corresponds to -1
;Output:
;    HL
ld h,0
ld a,l
or a
jp p,acossub0
neg
call acossub0
ld a,128
sub l
ld l,a
ret
acossub0:
    cp 14
jr c,$+7
cp 57
jr nc,$+3
dec a
cp 68
jp nc,acossub1
    inc a
ld bc,0530h
cp c \ jr c,$+3 \ sub c
rla \ djnz $-5
    or $E0
add a,65
ld l,a
ret
acossub1:
;now
sub 68
;between 0 and 21, slope is -2/5
sub 22
jr nc,acossub2
ld c,5 \ ld l,h
inc l \ add a,c \ jr nc,$-2
sub 3 \ ld a,l
    adc a,a
add a,1Fh
ld l,a
ret
acossub2:
;original a>=90
;between 0 and 17, slope is -1/2
sub 18
jr nc,acossub3
rra
    cpl
add a,18h
ld l,a
ret
;original a>=107
acossub3:
ld hl,acosLUT
add a,l
ld l,a
jr nc,$+3
inc h
ld l,(hl)
ld h,0
ret
acosLUT:
.db $17
.db $16
.db $16
.db $15
.db $15
.db $14
.db $13
.db $13
.db $12
.db $11
.db $10
.db $F
.db $E
.db $E
.db $D
.db $B
.db $A
.db $9
.db $7
.db $5

And if you are okay with tiny error of only 1, this is 21 bytes smaller and around 300 t-states worst case:
Code: [Select]
acos:
;Input:
;    L is the signed int from [-128,127] where -128 corresponds to -1
;Output:
;    HL
ld h,0
ld a,l
or a
jp p,acossub0
neg
call acossub0
ld a,128
sub l
ld l,a
ret
acossub0:
cp 90
jp nc,acossub1
    inc a
ld bc,0530h
cp c \ jr c,$+3 \ sub c
rla \ djnz $-5
    or $E0
add a,65
ld l,a
ret
acossub1:
;now
sub 90
ld hl,acosLUT
add a,l
ld l,a
jr nc,$+3
inc h
ld l,(hl)
ld h,0
ret
acosLUT:
.db $20
.db $20
.db $1F
.db $1F
.db $1E
.db $1E
.db $1D
.db $1D
.db $1C
.db $1C
.db $1B
.db $1B
.db $1A
.db $1A
.db $19
.db $19
.db $18
.db $18
.db $17
.db $16
.db $16
.db $15
.db $15
.db $14
.db $13
.db $13
.db $12
.db $11
.db $10
.db $F
.db $E
.db $E
.db $D
.db $B
.db $A
.db $9
.db $7
.db $5

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: Approximating inverse trigonometric functions
« Reply #8 on: November 22, 2013, 12:40:34 am »
Nice :D and yeah, I figured out that I could use a LUT for [89,128], but I was too lazy to copy the values, since I had no computer atm :P

Offline Matrefeytontias

  • Axe roxxor (kinda)
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1982
  • Rating: +310/-12
  • Axe roxxor
    • View Profile
    • RMV Pixel Engineers
Re: Approximating inverse trigonometric functions
« Reply #9 on: November 26, 2013, 12:30:15 pm »
Plop,

Small optimisations of the cos-1 routine (algorithm-related), and I figured a fast way to get sin-1 from cos-1 :) so now you have this :
:Lbl ArcCos
:~abs()→r2
:
:If >>~89
:~r2
:Else
:128-√(r2+128*30)
:End
:→r2
:r1ee0??128-r2,r2
:Return
:
:Lbl ArcSin
:-ArcCos()+64
(:Return)