В коде Quake III Arena (1999) есть легендарная функция с интересными комментариями — это алгоритм быстрого вычисления обратного квадратного корня, который работал примерно в 4 раза быстрее стандартного способа.
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y;
// evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 );
// what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
return y;
}
Фишка в том, что функция трактует биты float-числа как integer, делает побитовый сдвиг вправо (по сути делит экспоненту пополам), вычитает результат из «магического числа» 0x5f3759df, конвертирует обратно во float и делает одну итерацию метода Ньютона для уточнения. Звучит безумно, но математически работает: магическое число подобрано так, чтобы дать очень хорошее начальное приближение для обратного квадратного корня, а метод Ньютона доводит точность до нужного уровня всего за одну итерацию.
Обратный квадратный корень нужен был для нормализации векторов при расчёте освещения в 3D-графике — таких операций выполнялось миллионы в секунду, и каждое ускорение критично. Долгое время никто не знал, кто автор алгоритма, потом выяснилось, что это Greg Walsh из конца 1980-х. Сейчас у процессоров есть специальные инструкции для таких вычислений, но этот хак остаётся одним из самых элегантных примеров низкоуровневой оптимизации в истории.
Подробнее в википедии.
@devs_books
