Продолжая обратную разработку математического сопроцессора Intel 8087, исследователь Ken Shirriff с коллегами разобрал одну из тригонометрических функций — FPTAN. Пожалуй, самое интересное в таком реверс-инжиниринге — понять, какой именно алгоритм лёг в основу реализации, и восстановить логику, стоящую за окончательной схемотехникой.
Если работать с простым микроконтроллером или процессором вроде 6502 или Z80 без аппаратных функций, для тригонометрии обычно применяют алгоритм наподобие CORDIC: ему нужны лишь базовые операции — сложение, вычитание, битовый сдвиг и таблицы поиска. Можно использовать и полиномиальную аппроксимацию, если есть аппаратная поддержка для ускорения, либо, как в 8087, объединить оба подхода ради скорости и точности.
Автор подробно разбирает реализацию, обеспечивающую точность в 64 бита: первые 16 бит вычисляются через CORDIC, после чего происходит переход к аппроксимации Паде — методу, основанному на отношении двух многочленов. Поскольку после расчёта основной части значения через CORDIC остаток оказывается довольно малой величиной, такая полиномиальная аппроксимация не только очень точна, но и быстра.
Этот подход позволяет FPTAN и другим тригонометрическим функциям сопроцессора достигать очень высокой точности, не требуя ни больших таблиц поиска, ни дополнительного времени, которое ушло бы на дорасчёт оставшихся битов средствами CORDIC. Для тех, кто хочет увидеть весь алгоритм инженеров Intel, в статье приводится полный листинг микрокода с комментариями.
По расчётам для одного из значений, FPTAN тратит около 33% времени на псевдоделение в CORDIC, 47% — на псевдоумножение и лишь 15% — на полиномиальную аппроксимацию, плюс примерно 5% накладных расходов.
Начиная с процессоров Pentium, Intel полностью отказалась от CORDIC: при всей его точности алгоритм плохо масштабируется до большого числа битов без существенных потерь во времени. С появлением SIMD-инструкций набор x87 растерял ещё часть функциональности, но этот анализ лишний раз показывает, почему 8087 в своё время произвёл такое впечатление.
