Jump to content

Use fast trig in C on the X16


rje
 Share

Recommended Posts

I've started looking for easy, portable, fast and imprecise 8-bit trigonometric functions to use in the game I'm writing in C.

I've attached a 320 element binary table, with of course the obligatory initial two null bytes.  Use it like this:

foo = TRIG_TABLE[ x ];  // sin(x).  x is from 0 to 255, representing 0 to 360 degrees.
bar = TRIG_TABLE[ x + 64 ]; // cos(x).  

foo_sign = foo & 128;
foo_val = foo & 127;

bar_sign = bar & 128;
bar_val = bar & 127;

The indexed byte value has two parts: the 8th bit is the sign bit.  The remaining 7 bits represent the value, in hundredths.

Yazwho and Desertfish noted that sin and cos overlap, so only one table is needed, as long as you start COS indexing at an offset of 64 (= 90 degrees). In other words, cos(x) = sin(x+64). Since space isn't THAT critical, the table is 320 bytes long.

* * *

I found this interesting idea over here: https://geometricolor.wordpress.com/2017/01/06/fast-approximations-of-the-sine-and-cosine-functions/

Quote

The length of the table should be a power of 2 plus one for linear approximation. Then we can use bitwise-and (&) to impose periodicity instead of the much slower modulus (%) operation.

 

TRIG

Edited by rje
Link to comment
Share on other sites

7 minutes ago, x16tial said:

How do BASICs trig functions work?  Tables of information might already be in ROM.

Nicely suggested.  You're right, I should look!

 

Link to comment
Share on other sites

22 minutes ago, rje said:

My first assumption is that there could be two tables, one for sine, and one for cosine.

cos is just sin offset by 90 degrees, or 64 if you use a 256 byte table. So you can save yourself some ram at the expense of an add.

Depending on what you're trying to do, if it's possible to match the amplitude to what you need (so no multiplication is required) you'll obviously get better performance.

  • Like 2
Link to comment
Share on other sites

Posted (edited)

Commodore BASIC's SIN routine, after dividing the problem by quadrant, uses floating point math thus:

Quote

...It finally computes SIN(X) using the following polynomial, which approximates SIN(F2*2*π) over [-0.25, +0.25]:

-14.381390672 * F211 + 42.007797122 * F29 - 76.704170257 * F27 + 81.605223686 * F25 - 41.341702104 * F23 + 6.2831853069 * F2

...

SIN calls POLY1, which calls MLTPLY ($BA59), and consequently the multiply bug affects its results.

https://www.c64-wiki.com/wiki/SIN

Edited by rje
Link to comment
Share on other sites

Posted (edited)
1 hour ago, x16tial said:

How do BASICs trig functions work?  Tables of information might already be in ROM.

Now you've got me wondering what a BETTER but still not perfect sin/cos table would look like.  I mean, it could have 64K entries.

But at that point it's ridiculous, and so not only would it be divided into quadrants (thus shrinking to a 16K table) but I suspect speed would be sacrificed and an assembly routine would be introduced, and the result would land somewhere in between.

There's always https://en.wikipedia.org/wiki/Bhaskara_I's_sine_approximation_formula

image.png.69c2625dc12a438435da9c4720a5fb85.png

Edited by rje
Link to comment
Share on other sites

58 minutes ago, rje said:

It also didn't occur to me to find out what kind of trigonometric functions cc65 has, if any (I couldn't find them in cc65's library discussion).

Unfortunately, none.  Anything that requires floats and/or math.h hasn't been implemented yet.  It seems to be due to how the 6502 does floating point vs the 'traditional' C implementation using IEEE 754.  There were discussions on the cc65 dev list a few years ago about it, and one guy seemed to be making progress, but nothing seems to have been committed to the master branch as of yet.

Link to comment
Share on other sites

1 hour ago, Michael Parson said:

  It seems to be due to how the 6502 does floating point vs the 'traditional' C implementation using IEEE 754.  

In short, the 6502 doesn't do floating point at all. You need to implement it with 8-bit integer math. That's what BASIC does. You could absolutely implement IEEE 754 as a cc65 library, it's just going to be very slow same as any FP implementation.

 

 

  • Like 2
Link to comment
Share on other sites

On 3/26/2021 at 5:22 PM, x16tial said:

How do BASICs trig functions work?  Tables of information might already be in ROM.

Basic Trigs, Logs, Exponents and most of those similar functions, and powers, are Taylor Series (not sure about Square Root) which approximate to those values. The BASIC has very little other than a table of the appropriate constants.

You'd be far better off using fixed point arithmetic (say x 256) and a table. You only need degrees 0-45, everything else you can derive easily enough.

 

  • Like 1
Link to comment
Share on other sites

  • 5 months later...

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
×
  • Create New...

Important Information

Please review our Terms of Use