Going on a Tangent with the Intel 8087’s Hybrid CORDIC Algorithm

Continuing their reverse-engineering of Intel’s 8087 FPU, [Ken Shirriff] and friends took a look at one of the trigonometric functions, specifically FPTAN.  The most exciting part with such reverse-engineering is probably figuring out which algorithm was used in the implementation, while trying to determine the reasoning behind the final hardware design.

If you’re running a simple MCU or MPU like the 6502 or Z80 without hardware functions you’d likely use an algorithm such as CORDIC or similar, as this requires only basic hardware features like addition, subtraction, bitshift, and look-up tables. One can also use polynomial approximation if there’s hardware support for a potential speed-up, or as is the case in the 8087, create a hybrid approach that targets speed and accuracy.

In the article the exact implementation to get to 64 bits of accuracy is detailed, starting with the 16 bits calculated using CORDIC before switching to the Padé approximant technique involving the ratio of two polynomials. Since after calculating the brunt of the final value with CORDIC the remainder is a fairly small value this polynomial approximation not just very accurate but also fast.

This approach allows the FPTAN and similar trigonometric functions in this FPU to hit a very high level of accuracy and not require the look-up table sizes and additional time required to work through the remaining bits with CORDIC. For those who want to see the full algorithm Intel’s engineers used, [Ken] has the full microcode listing with comments in the article as well.

As for the exact speed-up from this approach, [Ken] calculates for one value that FPTAN would spend 33% on CORDIC pseudo-division, 47% on CORDIC pseudo-multiplication and a mere 15% on the polynomial approximation along with about 5% overhead.

With the Pentium series of CPUs Intel moved completely away from CORDIC, as it’s clear that as accurate as it may be, it’s hard to scale to a significant number of bits without incurring significant time penalties. With the introduction of SIMD instructions the x87 ISA has further seen its functionality reduced, but this analysis shows once again why the 8087 made such an impact when it was released.