Рассчитывает ли Sqrt (x) как x * InvSqrt (x) какой-либо смысл в коде Doom 3 BFG?

Я просмотрел недавно выпущенный исходный код Doom 3 BFG, когда я столкнулся с чем-то, что, похоже, не имеет никакого смысла. Doom 3 завершает математические функции в классе idMath. Некоторые из функций просто соответствуют соответствующим функциям из math.h, но некоторые из них являются переопределениями (например, idMath:: exp16()), которые, как я предполагаю, имеют более высокую производительность, чем их math.h аналогов (возможно, за счет точности).

Что меня озадачивает, так это то, как они реализовали функцию float idMath::Sqrt(float x):

ID_INLINE float idMath::InvSqrt( float x ) {
     return ( x > FLT_SMALLEST_NON_DENORMAL ) ? sqrtf( 1.0f / x ) : INFINITY;
}

ID_INLINE float idMath::Sqrt( float x ) {
     return ( x >= 0.0f ) ? x * InvSqrt( x ) : 0.0f;
}

Это, как представляется, выполняет две ненужные операции с плавающей запятой: сначала деление, а затем умножение.

Интересно отметить, что оригинальный исходный код Doom 3 также реализовал функцию квадратного корня таким образом, но обратный квадратный корень использует алгоритм быстрого обратного квадратного корня.

ID_INLINE float idMath::InvSqrt( float x ) {

    dword a = ((union _flint*)(&x))->i;
    union _flint seed;

    assert( initialized );

    double y = x * 0.5f;
    seed.i = (( ( (3*EXP_BIAS-1) - ( (a >> EXP_POS) & 0xFF) ) >> 1)<<EXP_POS) | iSqrt[(a >> (EXP_POS-LOOKUP_BITS)) & LOOKUP_MASK];
    double r = seed.f;
    r = r * ( 1.5f - r * r * y );
    r = r * ( 1.5f - r * r * y );
    return (float) r;
}


ID_INLINE float idMath::Sqrt( float x ) {
    return x * InvSqrt( x );
}

Вы видите какое-либо преимущество при вычислении Sqrt(x) как x * InvSqrt(x), если InvSqrt(x) внутренне просто вызывает math.h fsqrt(1.f/x)? Возможно, мне не хватает чего-то важного для денормализованных чисел с плавающей запятой или это просто небрежность в части программного обеспечения id?

Ответы

Ответ 1

Я вижу две причины для этого: во-первых, метод "быстрый invSqrt" (действительно, Newton Raphson) теперь является методом, используемым во многих аппаратных средствах, поэтому этот подход открывает возможность воспользоваться такими (и, возможно, четыре или более таких операций одновременно). В этой статье это немного обсуждается:

Как медленно (сколько циклов) вычисляется квадратный корень?

Вторая причина заключается в совместимости. Если вы измените путь кода для вычисления квадратных корней, вы можете получить разные результаты (особенно для нулей, NaN и т.д.) И потерять совместимость с кодом, зависящим от старой системы.

Ответ 2

Насколько я знаю, InvSqrt используется для вычисления цветов в том смысле, что цвет зависит от угла, от которого свет отскакивает от поверхности, что дает вам некоторую функцию, используя обратный квадратный корень.

В их случае им не нужна огромная точность при вычислении этих чисел, поэтому инженеры, стоящие за кодом Doom 3 (первоначально Quake III), разработали очень быстрый метод вычисления приближения для InvSqrt, используя только несколько итераций Ньютона-Рафсона.

Вот почему они используют InvSqrt во всем своем коде вместо использования встроенных (более медленных) функций. Я полагаю, что использование x * InvSqrt(x) заключается в том, чтобы избежать умножения работы на два (с помощью двух очень эффективных функций, один для InvSqrt и другого для Sqrt).

Вы должны прочитать эту статью, это может пролить свет на эту проблему.

Ответ 3

Когда код был изменен несколькими людьми, становится трудно ответить на вопросы о том, почему он имеет свою текущую форму, особенно без истории изменений.

Однако, учитывая треть века опыта программирования, этот код соответствует шаблону, о котором говорили другие: в свое время InvSqrt был быстрым, и имеет смысл использовать его для вычисления квадратного корня. Затем InvSqrt изменился, и никто не обновил Sqrt.

Ответ 4

Возможно также, что они натолкнулись на относительно наивный вариант sqrtf, который был заметно медленнее для больших чисел.