c++ - edition - doom 3 source code

¿Tiene sentido calcular Sqrt(x) como x*InvSqrt(x) en el código Doom 3 BFG?

Question

Busqué en el código fuente de Doom 3 BFG recientemente publicado, cuando encontré algo que no parece tener sentido. Doom 3 envuelve las funciones matemáticas en la clase idMath . Algunas de las funciones solo avanzan hacia las funciones correspondientes de math.h , pero algunas son reimplementaciones (por ejemplo, idMath::exp16() ) que supongo que tienen un rendimiento más alto que sus contrapartidas de math.h (quizás a expensas de la precisión).

Lo que me desconcierta, sin embargo, es la forma en que han implementado la función 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;
}

Esto parece realizar dos operaciones de coma flotante innecesarias: primero una división y luego una multiplicación.

Es interesante observar que el código fuente original de Doom 3 también implementó la función de raíz cuadrada de esta manera, pero la raíz cuadrada inversa usa el algoritmo de raíz cuadrada inversa rápida .

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 );
}

¿Ve alguna ventaja al calcular Sqrt(x) como x * InvSqrt(x) si InvSqrt(x) internamente llama a math.h ''s fsqrt(1.f/x) ? ¿Me estoy perdiendo algo importante acerca de los números de coma flotante desnormalizados aquí o es esto simplemente descuido en la parte del software de identificación?

Answer 1

Cuando varias personas han modificado el código, resulta difícil responder preguntas sobre por qué tiene su forma actual, especialmente sin historial de revisiones.

Sin embargo, dado un tercio de siglo de experiencia en programación, este código se ajusta al patrón que otros han mencionado: En un momento, InvSqrt era rápido, y tenía sentido usarlo para calcular la raíz cuadrada. Luego InvSqrt cambió y nadie actualizó Sqrt .

Answer 2

Hasta donde yo sé, el InvSqrt se usa para calcular colores en el sentido de que el color depende del ángulo desde el cual la luz rebota en una superficie, lo que le da alguna función usando la inversa de la raíz cuadrada.

En su caso, no necesitan una gran precisión al calcular estos números, por lo que los ingenieros que están detrás del código de Doom 3 (originalmente de Quake III) InvSqrt un método muy muy rápido para calcular una aproximación para InvSqrt utilizando solo varios Newton-Raphson. iteraciones.

Esta es la razón por la que usan InvSqrt en todo su código, en lugar de usar funciones incorporadas (más lentas). Supongo que el uso de x * InvSqrt(x) está ahí para evitar multiplicar el trabajo por dos (teniendo dos funciones muy eficientes, una para InvSqrt y otra para Sqrt ).

Deberías leer this artículo, podría arrojar algo de luz sobre este tema.

Answer 3

Puedo ver dos razones para hacerlo de esta manera: en primer lugar, el método "fast invSqrt" (realmente Newton Raphson) es ahora el método utilizado en un montón de hardware, por lo que este enfoque deja abierta la posibilidad de aprovechar dicho hardware (y haciendo potencialmente cuatro o más de tales operaciones a la vez). Este artículo lo discute un poco:

¿Qué tan lento (cuántos ciclos) está calculando una raíz cuadrada?

El segundo motivo es la compatibilidad. Si cambia la ruta del código para calcular las raíces cuadradas, puede obtener resultados diferentes (especialmente para ceros, NaN, etc.) y perder compatibilidad con el código que dependía del sistema anterior.

Answer 4

También es posible que encontraran una versión relativamente ingenua de sqrtf que era notablemente más lenta para números más grandes.