Реверс-інжиніринг алгоритму тангенса Intel 8087: більше, ніж CORDIC
Кен Ширріфф дослідив кристал і мікрокод математичного співпроцесора Intel 8087 та з'ясував, що інструкція FPTAN поєднувала 16-бітний CORDIC із раціональним наближенням Паде, щоб досягти 64-бітної точності.
Математичний співпроцесор Intel 8087, представлений 1980 року, значно прискорив обчислення з плаваючою комою в IBM PC: тангенс обчислювався приблизно за 90 мікросекунд проти близько 13 000 на 8086. Кен Ширріфф відновив алгоритм інструкції FPTAN, дослідивши кристал і мікрокод чипа, і з'ясував, що 8087 не обмежився самим CORDIC.
CORDIC: від B-58 до 8087
Чип використовував CORDIC, який Джек Волдер створив 1956 року для бомбардувальника B-58 Hustler. Алгоритму потрібні лише зсуви, додавання та таблиця наперед обчислених спеціальних кутів, arctan(2^-n), без множення й ділення: обертання вектора (1, 0) на ці кути дає точку (X, Y), а тангенс дорівнює Y/X.
Чому раціональний многочлен
16 кроків CORDIC дають приблизно 16 біт, а для 64 біт знадобилися б 64 кроки. Тому 8087 обчислює малий залишковий кут (близько 2^-16) наближенням Паде: відношенням 3x/(3-x²), похибка якого зростає як x⁴ і залишається меншою за 2^-64. Відношення двох многочленів описує тангенс краще, ніж ряд Тейлора, бо функція розбігається в π/2; а оскільки FPTAN повертає чисельник і знаменник окремо, ділення нічого не коштує.
Три фази в мікрокоді
ROM мікрокоду містить 1648 мікроінструкцій, а FPTAN починається з адреси #1039. Псевдоділення порівнює вхідний кут зі збереженими кутами CORDIC і записує рішення в 16-бітний регістр зсуву; для 0,95 радіана виходить послідовність 10010101 00100111. Далі йде раціональне наближення, а потім псевдомноження: обертання виконуються зсувами й додаваннями у зворотному порядку, від найменшого. Більшість арифметики — 64-бітні цілі числа з неявними експонентами, а найдорожча операція — піднесення кута до квадрата.
Апаратне забезпечення та продуктивність
Числа зберігаються у 80-бітному форматі «temporary real»: знак, 15-бітна зміщена експонента і 64-бітна мантиса, а кожен регістр стека має тег — zero, valid, special або empty. FPTAN зазвичай займає 450 тактів; для 0,95 на псевдоділення припадає 33% часу, на многочлен 15%, на псевдомноження 47%, ще 5% — накладні витрати. Для Pentium Intel перейшла на поліноміальні наближення.
Дослідження проводили разом із «Opcode Collective»: зображення ROM перетворили на дані мікрокоду за допомогою класифікатора машинного навчання.
SiTech — веброзробка з підтримкою AI
Створюємо швидкі та сучасні сайти й інтегруємо AI у бізнес-процеси. Маєте проєкт чи запитання? Із задоволенням допоможемо.