1. Welcome to TechPowerUp Forums, Guest! Please check out our forum guidelines for info related to our community.

Finding cosine inverse without standard functions

Discussion in 'Programming & Webmastering' started by xfire, Oct 1, 2009.

  1. xfire

    xfire New Member

    Joined:
    Nov 22, 2007
    Messages:
    1,395 (0.60/day)
    Thanks Received:
    193
    Location:
    Hyderabad,India
    Anyone has any program or method to find the cosine inverse of a value without using the cos tables or cos-1 function? I'm trying to program an 8051 micro processor so in short a program to find cosine inverse in assembly language.
  2. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    12,994 (6.44/day)
    Thanks Received:
    3,094
    Location:
    IA, USA
    xfire says thanks.
    Crunching for Team TPU
  3. xfire

    xfire New Member

    Joined:
    Nov 22, 2007
    Messages:
    1,395 (0.60/day)
    Thanks Received:
    193
    Location:
    Hyderabad,India
    That should do:) Thanks a lot.
  4. xfire

    xfire New Member

    Joined:
    Nov 22, 2007
    Messages:
    1,395 (0.60/day)
    Thanks Received:
    193
    Location:
    Hyderabad,India
    any idea what (1/2) subscript n-1 stands for? I'm not able to figure out that part. It doesn't fit.
    Edit: got it! that's (2 power n)-1. Thanks :)
  5. W1zzard

    W1zzard Administrator Staff Member

    Joined:
    May 14, 2004
    Messages:
    14,545 (4.00/day)
    Thanks Received:
    11,226
    use a lookup table
  6. xfire

    xfire New Member

    Joined:
    Nov 22, 2007
    Messages:
    1,395 (0.60/day)
    Thanks Received:
    193
    Location:
    Hyderabad,India
    Like i mentioned without tables. I would have to program the entire table into the program. Waste of memory+size+time.
  7. W1zzard

    W1zzard Administrator Staff Member

    Joined:
    May 14, 2004
    Messages:
    14,545 (4.00/day)
    Thanks Received:
    11,226
    check how many bytes your compiled code uses, vs. how many bytes your LUT uses. also look at cpu time
    xfire says thanks.
  8. xfire

    xfire New Member

    Joined:
    Nov 22, 2007
    Messages:
    1,395 (0.60/day)
    Thanks Received:
    193
    Location:
    Hyderabad,India
    I see the point, will let you know the difference in memory and time once code is completed in both. LUT is faster but formula is shorter and accurate.
  9. W1zzard

    W1zzard Administrator Staff Member

    Joined:
    May 14, 2004
    Messages:
    14,545 (4.00/day)
    Thanks Received:
    11,226
    i doubt it is shorter, what kind of values are you working with ? int ?
  10. xfire

    xfire New Member

    Joined:
    Nov 22, 2007
    Messages:
    1,395 (0.60/day)
    Thanks Received:
    193
    Location:
    Hyderabad,India
    It doesn't have to be considered from 1 to infinity. as n tends to infinity the higher order terms can be ignored as they are very small. So you can consider up to say n=4 then the program is(in c cause i can do it faster)
    doing that in assembly could take a while.
  11. W1zzard

    W1zzard Administrator Staff Member

    Joined:
    May 14, 2004
    Messages:
    14,545 (4.00/day)
    Thanks Received:
    11,226
    you use only integer values ? or floating point too? (in the microcontroller)
  12. xfire

    xfire New Member

    Joined:
    Nov 22, 2007
    Messages:
    1,395 (0.60/day)
    Thanks Received:
    193
    Location:
    Hyderabad,India
    It's only integer but can be manipulated into a float by dividing 8 bits into 4 bits for integer part and 4 bits for decimal. Works only with the input post which is bit addressable.
  13. Tatty_One

    Tatty_One Super Moderator Staff Member

    Joined:
    Jan 18, 2006
    Messages:
    16,192 (5.37/day)
    Thanks Received:
    2,178
  14. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    12,994 (6.44/day)
    Thanks Received:
    3,094
    Location:
    IA, USA
    That site uses JavaScript functions (Math.cos, Math.acos, etc.). It doesn't help much when those aren't available. :(
    Crunching for Team TPU
  15. xfire

    xfire New Member

    Joined:
    Nov 22, 2007
    Messages:
    1,395 (0.60/day)
    Thanks Received:
    193
    Location:
    Hyderabad,India
  16. qamulek

    qamulek New Member

    Joined:
    Feb 7, 2008
    Messages:
    186 (0.08/day)
    Thanks Received:
    26
    I found this explanation of how to calculate a sine/cosine function to be interesting. A quick glance shows that they are using multiple rotations of the vector (1,0) till the angle of the final rotation is close enough to the angle of the desired rotation. Inside the description is a method that does this very fast, but I don't really understand that part fully yet(its late , i'm going to sleep, also I really don't care about it at this time).

    The interesting thing though is that a similar method can be used to find the inverse cosine. First for simplicity assume the angle lies between 0 and Pi/2. Take the initial vector at (1,0). The idea is that at each iteration if the x component of the vector is larger then the given cosine(the input) then the vector is rotated counter clockwise, otherwise the vector is rotated clockwise. Each iteration uses a rotation that is half as small as the previous rotation(the first rotation being Pi/4-counter clockwise), and the angle the vector is rotated must be kept track of as its the desired output(+ for counter clockwise rotations, -for clockwise rotations). Do as many iterations as you want accuracy(considering round off errors, and that without using the techniques mentioned in that link that you would have to precalculate the cos(Pi/(2^n)) and sin(Pi/(2^n)) for a max of n-1 iterations), however I think you must also consider the problems of accuracy using integers for each method.

    TBH I think a look up table using both the value for cos-1 as well as the first two derivatives of cos-1 for a second order series would be the easiest way to go. Oh wait..... I just looked and cos-1(x) is -1/sqrt(1-x^2) which goes to to -infinity as it approaches 1 :( Did a quick plot of the second order approximation compared to the cos-1 and found that the approximation itself doesn't last very long as the approximation is brought near 1. At x0=.995 I found the approximation lasts reasonably till x=.9975. At x0=.998 the approximation only lasted till about x=.999. The rotation method is starting to look A LOT faster considering the singularity of the derivative of cos-1(x) at x=1.

    EDIT: In that link figure out wth those techniques are to speed up the rotations. I can see how the method itself is sound, but using those techniques to speed up the rotations are probably very important(unless you don't care about speed).
    EDIT#2: The error(not including round off error) for the rotations method goes something like Pi/(2^(n+1)) where n is the number of iterations(n=1 being the Pi/4 rotation). A method that converges that fast would be hard to pass up.
    Last edited: Oct 2, 2009
    xfire says thanks.
  17. xfire

    xfire New Member

    Joined:
    Nov 22, 2007
    Messages:
    1,395 (0.60/day)
    Thanks Received:
    193
    Location:
    Hyderabad,India
    It's gone way over my head. It'll take me some time to understand but thanks:)
  18. qamulek

    qamulek New Member

    Joined:
    Feb 7, 2008
    Messages:
    186 (0.08/day)
    Thanks Received:
    26
    It goes faster if you ask questions. For instance I started writing a bunch of stuff about how you can calculate a sine/cosine by rotating the vector (1,0), but then I realized that most likely is not what you are having trouble understanding.

    I read that link again this morning and found that for sine/cosine they were able to reduce the rotations to a bit shift and add operation at each iteration, and a final multiplication by essentially a constant. Since a cos-1 function would need the value of the cosine at each iteration you would need the full bit shift, add operation, and multiplication for every iteration.

    Before starting with the cos-1() you should probably start with trying to do cos() using the method in that link. You can hammer out the problems of round off due to using integers while building the cos function, then tweak it a bit to make the cos-1 function.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guest)

Share This Page