Метод утёнка: “В коде Quake III Arena (1999) есть легендарная функция с интересными к…”

В коде 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