Полезен ли сегодня быстрый обратный квадратный корень из Quake III?
23 min
Translation
В 2005 году id Software опубликовала под лицензией GPL-2 исходный код своей игры 1999 года Quake III Arena. В файле code/game/q_math.c есть функция для вычисления обратного квадратного корня числа, которая на первый взгляд выглядит очень любопытным алгоритмом:
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // зловещий хакинг чисел с плавающей запятой на уровне битов
i = 0x5f3759df - ( i >> 1 ); // какого чёрта?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // первая итерация
// y = y * ( threehalfs - ( x2 * y * y ) ); // вторая итерация, можно удалить
return y;
}Об этом алгоритме написано множество статей, и ему посвящена хорошая страница Википедии, где он назван fast inverse square root (быстрым обратным квадратным корнем). На самом деле, этот алгоритм упоминался на различных форумах ещё до публикации исходного кода Q3. Ryszard из Beyond3D провёл в 2004-2005 годах исследование и в конечном итоге выяснил, что первоначальным автором алгоритма был Грег Уолш из Ardent Computer, который создал его десятью годами ранее.
