The previous posts on sin() approximations has made me wonder which methods are implemented on 8-bit processors. So I took a look at both the AVR C library for the 8-bit megaAVR (used in the Arduino Uno) and the ZX Spectrum (an early Z80-based 8-bit computer) ROM disassembly.
Sin(x): The AVR C lib version
After downloading the most recent sources from the Subversion repository, I started going through the directory tree to get a sense of what can be found where. The files of interest are located in the avr-libc/libm/fplib/ directory; all of them are written in AVR assembly language.
The first routine to look at is sin which can be found in sin.S (gee, what gave it away?). This routine calls __fp_rempio2, which changes the argument so it is within the right range for calling the actual sin() calculating function, __fp_sinus.
The __fp_sinus function does some more domain manipulation after which it starts setting up pointers to a table holding six coefficients:
After the setup code, __fp_powsodd is called, which evaluates the following polynomial with odd powers only:
The careful observer will have noticed that the coefficients are those of the Taylor series for .
The maximum error of the Taylor approximation is determined by the first truncated term, which is then .
Summarizing, the AVR lib C uses an 11th-order polynomial based on the Taylor series and domain symmetry to calculate sin(x).
Sin(x): Z80 / ZX Spectrum version
According to the Complete Spectrum ROM Disassembly the main part of the sin() function is the series generator routine. This routine evaluates Chebyshev polynomials up to a specified order. The calculation of sin() is based on the first six polynomials:
These polynomials are weighted using the following coefficients:
The approximation polynomial is equal to:
,where and is between -1 and 1.
Finally, the approximation is calculated by .
The interesting thing about the ZX Spectrum code is that the Chebyshev polynomials are not evaluated one at a time, but that the entire calculation of is done in one go. This code is almost as efficient as evaluating one polynomial!
The performance of this approximation is very good, as shown by the following graphs:
The maximum error is approximately , which is better than the AVR version! Not bad for an oldskool machine!
Sometimes older is better!
BOCHS, the IA-32 CPU emulator, uses a 17th-order Taylor polynomial to calculate sin().