Fixed Point ASIN ?

epmoyer

Is there a fixed point Arc Sin (ASIN) routine out there for the Propeller?

I'm looking to use it in a Hydra game (SpaceWar). My concern is that the best way to do it is probably some kind of a newton's method search of the sin table, which is bound to be both non-deterministic (i.e. take different amounts of time depending on the query value), and be dog slow.

For what I'm doing it may be sufficient for me to create my own reverse lookup table with limited angular resolution (its just a game, after all [noparse]:)[/noparse], but if there was something usable out there already I'd rather make use of it.

Thanks

Mike Green

I'm not aware of any arcsine routines other than in the floating point package. Consider using a binary search of the sine table in ROM. With 2048 (actually 2049) entries, the worst case is 11 probes (comparisons). The search time is value dependent, but there are strong bounds on time.

Beau Schwabe

empoyer,

Here is a reverse sine lookup method using 11 iterations that is exactly what Mike describes.
The main core of it (Function Engine) written in assembly is really all that is needed.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

JasonE

Hello,

· Is there a way to use or modify the code that Beau posted in a manner that does not·require an extra cog?

·I am cog limited at the moment and am (unfortunately) not very strong in assembly.

Any thoughts or guidance would be appreciated!!!

-Jason

Beau Schwabe

JasonE,

If you already have an object written in Assembly, you can cut-n-paste the required portions of my code into your Assembly object....

Alternatively you could use spin from your main cog... I'll look and see, but I don't think I have it any more. Originally before I converted
the function to Assembly it was in Spin.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

stevenmess2004

You can make binary searches take a constant amount of time if you want. Have a look here en.wikipedia.org/wiki/Binary_search

JasonE

·· I don't have assembly code I feel I can modify to accomodate the asin code.· What I've done in the meantime is implemented a Taylor series approximation: asin(x) = x + 1/6x^3 + 3/40x^5, which quickly starts to diverge for large angles (x > 0.7, angles·> 45 ) even with higher order terms added (5/112 x^7...).

· Beau, if you happen to come across the spin implementation I would appreciate it.

Thank you all for your input!

-Jason

Beau Schwabe

JasonE,

About the only thing I could fine was a Program that I wrote in QuickBasic4.5 to prove the concept.··It's simply a software version of the classic game ... "guess what number" in as few steps as possible.· The only feed back you get is if the 'actual' number is higher or lower than the guessed number.
·
If you don't need as much·accuracy, then you can shorten the number of steps.· 11-steps were used to correlate with the 13-bit resolution of the sine table built in the Propeller ROM.· The "missing" two bits are because the ROM table only holds 1/4 of the Sine table (... or 11 bits) the other two bits are derived by translation. (Flipping/Mirroring)
·

ARCSIN = 1                              'Range from -1 to 1

Pi# = ATN(1) * 4                        'Build 1/4 Sine Table
DIM SineTable(2048)
Index = 0
FOR Deg = 0 TO 90 STEP 90 / 2048
    Rad = (Deg / 180) * Pi#
    SineTable(Index) = SIN(Rad)
    Index = Index + 1
NEXT Deg

                                        'Find ArcSin Value
'---------------------------------------------------------------------
RefHigh = 2048                          'Set Ref HIGH
 RefLow = 0                             'Set Ref LOW
  Pivot = (RefHigh + RefLow) \ 2        'Set Pivot point
   Sign = SGN(ARCSIN)                   'Preserve sign of ARCSIN value
 ARCSIN = ABS(ARCSIN)                   'Convert ARCSIN to absolute value
 
FOR Iterations = 1 TO 11                'Solve ARCSIN in 11 iterations
   
    IF SineTable(Pivot) > ARCSIN THEN   'Get 'Pivot' SineTable value and
                                        'compare
      
       RefHigh = Pivot                  'If 'Pivot' SineTable value is
                                        'greater than the ARCSINE value
                                        'then adjust RefHigh to equal Pivot
    ELSE
       RefLow = Pivot                   'If 'Pivot' SineTable value is
                                        'less than or equal to the ARCSINE
                                        'value then adjust RefLow to equal
                                        'Pivot
    END IF
    Pivot = (RefHigh + RefLow) \ 2      'Re-define Pivot point based on
                                        'RefHigh and RefLow values.
NEXT Iterations
 
ARCSINDeg = Sign * ((Pivot * 90) / 2048)        'Calculate answer in Degrees
ARCSINRad = Sign * ((Pivot * (Pi# / 2)) / 2048) 'Calculate answer in Radians

CLS                                     'Clear Screen
PRINT ARCSINDeg                         'Display answer in Degrees
PRINT ARCSINRad                         'Display answer in Radians

·Note: In QuickBasic4.5 code, the ''/" division bar indicates standard floating point division.· When the "\" division bar is used·it indicates integer division.
·········


·

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Beau Schwabe

IC Layout Engineer
Parallax, Inc.

Post Edited (Beau Schwabe (Parallax)) : 4/4/2008 4:40:40 AM GMT

JasonE

Beau,

· Thank you very much!· This is something I can work with!· I appreciate you taking the time to find this.

-Jason