Tout savoir sur l’algorithme de l’inverse de racine carrée rapide

Tout savoir sur l’inverse de racine carrée rapide

Algorithme

• L’algorithme de l’inverse de racine carrée rapide est un algorithme rendu célèbre par le code source de Quake 3, utilisé par John Carmack.
• Cet algorithme calcule rapidement l’inverse d’une racine carrée en manipulant les bits d’un nombre à virgule flottante.
• Exemple de code :

  float Q_rsqrt(float number) {
    long i;
    float x2, y;
    const float threehalfs = 1.5F;
  
    x2 = number * 0.5F;
    y = number;
    i = *(long*)&y;              // 부동 소수점 비트 수준 해킹
    i = 0x5f3759df - ( i >> 1 ); // 마법의 상수
    y = *(float*)&i;
    y = y * ( threehalfs - ( x2 * y * y ) );  // 1차 반복
  
    return y;
  }
  

Virgule flottante 32 bits : représentation

• Le format à virgule flottante IEEE-754 32 bits se compose de 3 éléments :
  • Signe : 1 bit, indique si le nombre est positif ou négatif.
  • Exposant : 8 bits, détermine la plage de valeurs du nombre.
  • Mantisse : 23 bits, spécifie la position du nombre dans cette plage.
• La valeur réelle se calcule comme suit :

  N = -1^S * 2^(E-127) * (1 + M/2^23)
  

Virgule flottante 32 bits : interprétation des bits

• La représentation interne d’un nombre à virgule flottante n’est généralement pas importante pour les programmeurs.
• Cependant, une bonne compréhension de cette représentation permet de concevoir des algorithmes efficaces.
• Si l’on interprète le motif de bits d’un flottant comme un entier, on obtient une approximation de la fonction logarithme.

  log2(x) ≈ Ix / L - B
  

Méthode de Newton

• La méthode de Newton (Newton's method) est utilisée pour améliorer la valeur d’approximation initiale.
• La méthode de Newton est un algorithme qui améliore de manière itérative l’approximation d’une fonction donnée.
• Exemple de code :

  y = y * ( threehalfs - ( x2 * y * y ) ); // 1차 반복
  

Conclusion

• Cet algorithme a été conçu à partir d’une compréhension approfondie des détails mathématiques internes du système à virgule flottante, en exploitant des opérations rapides à exécuter sur ordinateur.
• L’origine exacte de l’algorithme n’est pas certaine, mais il constitue un exemple d’ingénierie extrêmement efficace et bien pensée.

L’avis de GN⁺

• Importance historique : cet algorithme est une méthode innovante conçue pour surmonter les contraintes matérielles de l’époque.
• Valeur pédagogique : il aide grandement à comprendre la structure interne des nombres à virgule flottante et les principes mathématiques sous-jacents.
• Application moderne : il est peut-être moins nécessaire sur le matériel moderne, mais les principes de l’algorithme restent utiles.
• Potentiel d’optimisation : la valeur des constantes de l’algorithme peut être optimisée, ce qui laisse place à des recherches supplémentaires.
• Regard critique : sur le matériel moderne, il peut exister de meilleures méthodes ; il est donc important de toujours les comparer aux techniques les plus récentes.

[joyfui]

Un bout de code étonnant qui refait surface de temps en temps... haha

[GN⁺]

Commentaires Hacker News

• Prise en charge des instructions SSE : les ordinateurs fabriqués après 1999 prennent en charge le jeu d’instructions SSE et peuvent calculer rapidement l’inverse de la racine carrée via l’instruction _mm_rsqrt_ps.

• Progrès du matériel moderne : sur le matériel moderne, le calcul de l’inverse de la racine carrée peut être effectué rapidement par le CPU, et l’idée selon laquelle toutes les opérations en virgule flottante seraient déportées vers le GPU est erronée.

• Implémentation MMIX : il existe un exemple de code qui implémente le calcul de l’inverse de la racine carrée en langage MMIX. Ce code suppose à l’origine que le nombre est supérieur à 2^-1021.

• Coquille dans la formule : il y a une coquille dans la formule en virgule flottante. Il faut corriger en (-1)^S.

• Interprétation du logarithme : interpréter le motif de bits brut n’est pas une approximation linéaire par morceaux du logarithme. Les lignes entre les points de données n’existent pas réellement.

• Référence Wikipédia : Wikipédia propose une bonne discussion sur cette fonction et son histoire. Lien Wikipédia

• Recueil de code sur GitHub : quelques codes liés au sujet ont été rassemblés sur GitHub. Lien GitHub

• Référence StackOverflow : une question StackOverflow sur une approximation optimisée à faible précision mérite aussi le détour. Lien StackOverflow

• Expérience d’optimisation de moteur 3D : l’auteur avait acquis de l’expérience en optimisation en construisant des moteurs 3D avant Quake, et l’optimisation algorithmique l’emporte toujours.

• Recommandation de vidéo YouTube : il existe une vidéo intéressante sur ce sujet. Lien YouTube

• Voleur de temps productif : se plonger dans ce sujet a fait perdre beaucoup de temps productif.

• Nombre magique optimal : le nombre magique du célèbre extrait de code n’est pas la constante optimale. Il est possible d’en trouver une meilleure, et un notebook Jupyter permet de déterminer le nombre magique optimal.