25 лет тому назад мир впервые увидел Quake III Arena!
и при чем тут Быстрый обратный квадратный корень

19 сентября 1999 года мир впервые увидел Quake III Arena — игру, где виртуальные воины сражались в трёхмерных аренах. Но мало кто знал, что под капотом этой легенды скрывался алгоритм, навсегда изменивший представление о скорости вычислений.

В тот день в исходном коде id Software появилась функция с комментарием «зловещий хакинг чисел с плавающей запятой». Её авторы даже не подозревали, что их трюк станет легендой программирования:

i = 0x5f3759df - (i >> 1); // какого чёрта?

Этот код — сердце Fast Inverse Square Root, алгоритма для быстрого вычисления обратного квадратного корня. В эпоху, когда процессоры едва справлялись с 3D-графикой, он позволял рассчитывать освещение и траектории в десятки раз быстрее стандартных методов. Но как он работал? И почему до сих пор о нём говорят?

Тайна «магического числа»
В 2005 году исходный код Quake III стал открытым. Сообщество ахнуло: функция Q_rsqrt использовала битовые операции и загадочную константу 0x5f3759df. Программисты ломали голову: как преобразование целого числа в float может дать приближение обратного квадратного корня?

Объяснение звучало как магия:
1️⃣ Число с плавающей запятой разбирали на биты.
2️⃣ Сдвигали их вправо (делили на 2) и вычитали из «магического» числа.
3️⃣ Собирали обратно в float.

«Это как взять логарифм, умножить его на -0.5 и снова получить число», — шутили математики. Но за кулисами скрывался гениальный трюк: битовое представление float интерпретировали как целое число, что позволяло аппроксимировать результат через экспоненту и мантиссу.

Грег Уолш, создатель алгоритма, позже признался:

«Мы искали способ убрать деление. Оказалось, всё решила пара битовых операций и метод Ньютона».

«Касательная, которая спасла Quake»
Первое приближение было грубым. Чтобы уточнить его, разработчики использовали метод Ньютона-Рафсона — итерационную формулу:

y = y * (1.5 - (x * 0.5 * y * y));

Всего один шаг — и погрешность сокращалась с 2% до 0.001%. Этого хватало, чтобы рендерить 60 кадров в секунду на Pentium III.

«Пол, посмотри! Мы заменили сотни операций тремя строчками кода»
— возможно, так воскликнул программист id Software, запуская тесты.

В 1999 году алгоритм казался чудом. Но к 2020-м годам всё изменилось. Современные процессоры обзавелись инструкциями вроде rsqrtss, которые вычисляют обратный квадратный корень за такт. Тесты показали: на Intel Core i9 Fast Inverse Square Root в 4 раза медленнее аппаратной реализации.

Зачем тогда о нём помнить?
1️⃣ Гениальная простота. Алгоритм учит думать «вне рамок» — использовать биты как данные и как инструкции.
2️⃣ Исторический код. Без него игры вроде Quake III не смогли бы работать на слабых PC 90-х.
3️⃣ Вдохновение. Даже сегодня разработчики встраивают этот метод в микроконтроллеры без FPU.

Его алгоритм стал мостом между эпохами. В 1999-м он позволил железу выжать максимум, а сегодня напоминает: иногда гениальность кроется в одной строчке кода. Пусть даже с комментарием «какого чёрта?».

#АйтишныеБайки #IT #история #Quake