Le calcul de Sqrt(x) comme x * InvSqrt(x) a-t-il un sens dans le code BFG de Doom 3 ?

Question

J'ai parcouru la récente publication Code source de Doom 3 BFG quand je suis tombé sur quelque chose qui ne semble pas avoir de sens. Doom 3 emballe les fonctions mathématiques dans la section idMath classe. Certaines des fonctions renvoient simplement aux fonctions correspondantes de math.h mais certaines sont des réimplémentations (par ex. idMath::exp16() ) qui, je suppose, ont des performances supérieures à celles de leur math.h (peut-être au détriment de la précision).

Ce qui me laisse perplexe, cependant, c'est la façon dont ils ont mis en œuvre la float idMath::Sqrt(float x) fonction :

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

Cela semble effectuer deux opérations en virgule flottante inutiles : D'abord une division, puis une multiplication.

Il est intéressant de noter que le code source original de Doom 3 a également implémenté la fonction Racine carrée de cette manière, mais la Racine carrée inverse utilise la fonction algorithme inverse rapide de la racine carrée .

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

Voyez-vous un avantage à calculer Sqrt(x) como x * InvSqrt(x) si InvSqrt(x) en interne, il suffit d'appeler math.h 's fsqrt(1.f/x) ? Est-ce que je rate quelque chose d'important à propos des nombres à virgule flottante dénormalisés ou est-ce que ce n'est qu'une négligence de la part du logiciel ID ?

Answer 1

Je vois deux raisons de procéder de cette façon : premièrement, la méthode "fast invSqrt" (en réalité Newton Raphson) est maintenant la méthode utilisée dans beaucoup de matériel, donc cette approche laisse ouverte la possibilité de profiter de ce matériel (et de faire potentiellement quatre ou plus de ces opérations en une fois). Cet article en parle un peu :

Quelle est la lenteur (combien de cycles) du calcul d'une racine carrée ?

La deuxième raison est la compatibilité. Si vous changez le chemin du code pour le calcul des racines carrées, vous pouvez obtenir des résultats différents (en particulier pour les zéros, les NaN, etc.) et perdre la compatibilité avec le code qui dépendait de l'ancien système.

Answer 2

Pour autant que je sache, le InvSqrt est utilisé pour calculer les couleurs dans le sens où la couleur dépend de l'angle à partir duquel la lumière rebondit sur une surface, ce qui vous donne une fonction utilisant l'inverse de la racine carrée.

Dans leur cas, ils n'ont pas besoin d'une grande précision pour calculer ces chiffres, et les ingénieurs à l'origine du code de Doom 3 (provenant de Quake III) ont donc mis au point une méthode de calcul très très précise. très méthode rapide de calcul d'une approximation pour InvSqrt en utilisant seulement plusieurs itérations de Newton-Raphson.

C'est pourquoi ils utilisent InvSqrt dans tout leur code, au lieu d'utiliser des fonctions intégrées (plus lentes). Je suppose que l'utilisation de x * InvSqrt(x) est là pour éviter de multiplier le travail par deux (en ayant des deux des fonctions très efficaces, l'une pour InvSqrt et un autre pour Sqrt ).

Vous devriez lire ce article, il pourrait apporter un éclairage sur cette question.

Answer 3

Lorsque le code a été modifié par plusieurs personnes, il devient difficile de répondre aux questions sur la raison pour laquelle il a sa forme actuelle, surtout sans historique des révisions.

Cependant, compte tenu d'un tiers de siècle d'expérience en programmation, ce code correspond au modèle que d'autres ont mentionné : A un moment donné, InvSqrt était rapide, et il était logique de l'utiliser pour calculer la racine carrée. Puis InvSqrt a changé, et personne n'a mis à jour Sqrt .

Answer 4

Il est également possible qu'ils soient tombés sur une version relativement naïve de sqrtf qui était nettement plus lent pour les grands nombres.