Reverse-engineering the Intel 8087's tangent algorithm: more than CORDIC

Intel's 8087 math coprocessor, introduced in 1980, made floating-point arithmetic far faster in the IBM PC: a tangent took about 90 microseconds instead of roughly 13,000 on the 8086. Ken Shirriff has reverse-engineered the algorithm behind the FPTAN tangent instruction by examining the chip's die and microcode, and found more than CORDIC.

CORDIC, from the B-58 to the 8087

The chip used CORDIC, an algorithm Jack Volder created in 1956 for the B-58 Hustler bomber. CORDIC needs only shifts, additions and a table of precomputed special angles, arctan(2^-n), with no multiplication or division; rotating the vector (1, 0) through them yields (X, Y), and the tangent is Y/X.

Why a rational polynomial

Sixteen CORDIC steps give about 16 bits of accuracy, while 64 bits would need 64 steps. The 8087 therefore handles the small residual angle, about 2^-16, with a Pade approximant: the ratio 3x/(3-x²), whose error grows as x to the fourth power and stays below 2^-64. A ratio of polynomials fits the tangent better than a Taylor series because the function diverges at π/2, and FPTAN returns numerator and denominator separately, so the division costs nothing.

Three phases in microcode

The microcode ROM holds 1648 micro-instructions, and FPTAN starts at address #1039. Pseudo-division compares the input angle with the stored CORDIC angles and records the decisions as 16 bits in a shift register; 0.95 radians yields 10010101 00100111. The rational approximation supplies the starting vector, and pseudo-multiplication applies the rotations with shifts and adds in reverse order to limit rounding error. The arithmetic is 64-bit integer math with implicit exponents, and squaring the angle is the one costly step.

Hardware and performance

Numbers live in an 80-bit temporary real format: a sign bit, a 15-bit biased exponent and a 64-bit significand, and each stack register is tagged zero, valid, special or empty. FPTAN typically takes 450 clock cycles; for 0.95, 33% of the time goes to pseudo-division, 15% to the rational polynomial, 47% to pseudo-multiplication and 5% to overhead. Intel moved to polynomial approximations for the Pentium.

The analysis was done with the Opcode Collective, whose members converted the ROM images into microcode data with a machine-learning classifier.