gfs@abvax.UUCP (Greg F. Shay) (05/13/88)
In writing a graphics rotation routine for a stand alone, ROM demo, I had a
need for a subroutine that I found a bit of an interesting challenge.
------> Write sin(x) using integer math only. No lookup tables!
short sin(x)
short x;
{}
Some further detail, I used a 16 bit fixed point format for input and output:
short x;
S IIIIIIII.FFFFFFF
| Integer Fraction
sign bit
I used 32 bit integer for intermediate computations.
The interesting result is that the accuracy of the result is as good as the
accuracy of the number representation (that is the error is no larger than
the error due to the limited 7 bit fraction representation (1/128)).
Hint #1: Justify the number of terms in the power series you use.
Hint #2: My solution uses 2 intermediate integers and exactly 5 integer
multiplies.
Have fun! I'll post my solution for comparison later.
Greg Shay
mandrill |
decvax |..!abvax!gfs
pyramid |paul@torch.UUCP (Paul Andrews) (05/23/88)
In article <327@abvax.UUCP> gfs@abvax.UUCP (Greg F. Shay) writes: > ------> Write sin(x) using integer math only. No lookup tables! Why no lookup tables? If you relax that constraint you could use the Cordic algorithm (COordinate Rotation by DIgital Computer). The lookup table is small (#entries = bits of precision I think), and there are NO multiplications involved. Even machines that have hardware multiplies are usually fairly slow at them. In addition it performs - as the name implies - a rotation on two arguments giving two results (the X,Y of the rotated point). Only problem is a scale factor left at the end. You can either remove this using 2 divides or account for it in later transformations. Still I'll be interested to see the results of your poser. When I was looking for algorithms in this area I found it very difficult to find papers on the subject. At the time almost all the papers assumed that everyone had hardware floating point. That may have been true in the mainframe world but certainly not on my humble 6502. - Paul.