En Hexa, il s'agit des nombres 0x5f3759df et 0x5f375a86.

Le premier nombre, 0x5f3759df, est appelé constante magique et permet de calculer la fonction inverse de la racine carrée en utilisant une seule itération de la méthode d'approximation de Newton.
Le deuxième nombre, 0x5f375a86, est une amélioration de cette approximation, trouvée par un dénommé Chris Lomont.

Les explications que je suis incapable de donner, se trouvent là : http://fr.wikipedia.org/wiki/John_Carmack

Klim.

Ils sont tous les 2 congrus a 125 modulo 167 ?

Ces deux nombres ont me même nombre de chiffres ?! ou le même nombre de syllabes

Ces 2 nombres sont utilisés dans des algorithmes de calculs approchés de racines carrées et surtout d'inverses de racines carrées.
Voici un article très intéressant sur le sujet:
http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
En français, je n'ai rien trouvé de mieux que:
http://fr.wikipedia.org/wiki/John_Carmack
Mais John Carmack n'y est pour rien (si ce n'est qu'il l'a utilisé).

Il y a sans doute là de quoi faire un bon devoir de math ou d'info (quel niveau? TS? Sup?).

PS: C'était un peu "vache" de les donner en décimal plutot qu'en hexa

1597463007 et 1597463174
Ces deux nombres sont utilises dans les calculs de lumiere et reflexion des jeux 3D. Necessitant rapidite d'execution, un algorithme a ete mis en place afin de calculer approximativement mais tres rapidement l'angle du vecteur normal à une surface. L'algorithme de Quake III (1999) utilisait le premier nb (ou 5f3759df en base 16) mais il semblerait que le second soit plus precis encore.

Pour ceux qui sont ferus de solides mathematiques, tout est sur Wiki (je recommande plutot the english one)

Google me parle de magic number pour calculer une inverse square root...

Allez, un petit indice pour la route:
Spoiler : [Afficher le message] Ne pas chercher ce que ces nombres ont en commun, mais à quoi ils peuvent bien servir

Et dire que je me paumais tranquillement dans des bidouillages numériques...

Grâce à du Google sur le premier des deux nombres, je tombe sur la page Wikipedia dédiée à John Carmack, fondateur d'id software, à l'origine de jeux comme Wolfenstein 3D ou Quake. Et voici ce que j'y trouve :

L'Id Tech 3 (moteur de rendu 3D du jeu Quake III Arena) étant sous licence GNU GPL, il est possible de consulter l'intégralité du code source de ce jeu. Parmi celui-ci, on retrouve deux fonctions longtemps attribuées à John Carmack et qui auront fait beaucoup parler d'elles : l'une pour calculer une racine carrée, l'autre pour calculer l'inverse d'une racine carrée.

(...)

(La fonction qui calcule une racine carrée) est pour le moins particulière puisqu'elle ne contient aucune boucle, elle ne fait intervenir qu'une suite de calculs élémentaires! Pour autant, celle-ci fournit des approximations tout à fait acceptables (de l'ordre de 10-3). Elle est même jusqu'à 4 fois plus rapide que la fonction sqrt(float x) et se révèle ainsi parfaite pour un jeu vidéo.

En réalité, cette fonction repose sur une méthode tirée de l'analyse numérique : la méthode de Newton. La clef de son efficacité réside dans l'utilisation d'une constante particulière 0x5f3759df. Cette constante hexadécimale est utilisée comme première approximation et réduit de façon remarquable le nombre d'itérations nécessaires pour obtenir une approximation satisfaisante. Cette constante – dite magique – est si remarquable qu'une seule itération de Newton donne des résultats suffisants dans le cadre du rendu graphique.

Chris Lomont de l'université de Purdue a depuis étudié la question. Il existe une constante fournissant de meilleures approximations : 0x5f375a86.

Alors, comment que ça marche ? En fait, l'idée est de s'approcher itérativement de la racine carrée d'un nombre grâce à des itérations n'utilisant que les quatre calculs de base. Pour cela, connaissant une estimation [latex]x_i[/latex] de la racine carrée d'un nombre [latex]X[/latex] donné, je sais que [latex]X/x_i[/latex] sera une autre estimation de la racine carrée de X (logique : [latex]\left( X/x_i \right) \times x_i = X[/latex]) et que, si l'une est légèrement supérieure à la valeur recherchée, l'autre sera légèrement inférieure, et vice-versa. La moyenne de ces deux valeurs me donnera donc forcément une meilleure approximation de la valeur cherchée. (On peut le développer d'une façon plus rigoureuse comme un cas particulier de la méthode de Newton.) On a donc pour un calcul de racines carrées une boucle du type :

[latex]x_0[/latex] donné (une estimation de [latex]\sqrt{X}[/latex], ou carrément une valeur au pif)
Faire
[TeX]x_{i+1} = \frac{1}{2} \left( x_i + \frac{X}{x_i} \right)[/TeX]
Jusqu'à avoir une estimation assez précise

Et là où John Carmack (revenons à lui) a un coup de génie, c'est qu'il trouve un moyen de calculer [latex]x_0[/latex] de telle façon que [latex]x_1[/latex] est déjà une approximation au millième près de [latex]\sqrt{X}[/latex], donc une approximation d'assez bonne qualité pour l'utiliser directement. La boucle "faire/jusqu'à" ci-dessus est carrément supprimée grâce à un nombre miracle. Je copie la ligne du programme qui définit [latex]x_0[/latex] :

i  = 0x5f3759df - ( i >> 1 ); // what the fuck?

(Le commentaire "WTF ?" n'est pas de moi, je précise ) Cette ligne écrite en langage humain donne en gros [latex]x_0 = 1597463007 - X/2[/latex]. Et pourquoi ça marche aussi bien ? Aucune idée. D'où vient ce nombre ? Aucune idée non plus. Sorti du chapeau. Une sorte de magie noire mathématique totalement incroyable.

Chris Lomont a ensuite fait des recherches, et déterminé que le nombre 1597463174 donnerait de meilleurs résultats... sauf qu'en pratique, apparemment, pas tant que ça. John Carmack est un p**ain de magicien.



Sources :

http://fr.wikipedia.org/wiki/John_Carmack
http://www.codemaestro.com/reviews/9
http://www.beyond3d.com/content/articles/8/



Merci pour cette découverte, mon cher

Je me suis un peu amusé à chercher à la fois comme ca marche et si on pouvais faire mieux....

J'ai donc commencé par évaluer la fonction en question.
D'abord, on s'apercoit d'abord qu'il n'y a pas 1 nombre magique, mais 3, que j'appelle M (nombre magique), C (constante) et K (coefficient):

float InvSqrt(float x)
{
union {
 float f;
 long int i;
} tmp;
 tmp.f = x;
 tmp.i = M - (tmp.i >> 1);
 y = tmp.f;
 return y * (C - K * x * y * y);
}

Sachant que pour John Carmack on a:
M = 0x5f3759df, C=1.5 et K=.5
Et pour Chris Lomont
M = 0x5F375A86, C=1.5 et K=.5

J'ai donc testé quelques miliers de nombres pour évaluer la precision de cette fonction, et je trouve:
Pour 1597463007, 1.5 et 0.5:
...Erreur maximale=0.175124317%, erreur moyenne = 0.093610765%
Pour 1597463174, 1.5 et 0.5:
...Erreur maximale=0.175126597%, erreur moyenne = 0.093672335%

En reduisant M, on deminue l'erreur moyenne, mais l'erreur maximale augmente.
Ainsi, avec M=1597284351: 
...Erreur maximale=0.305380672%, erreur moyenne = 0.060541421%

Ensuite, apres quelques essais en manipulant M, C et K :
Je trouve:
Pour M=1597735700, C=1.47000 et K=0.46957:
...Erreur maximale=0.109190293%, erreur moyenne = 0.058649267%

Puis je me rend compte qu'il vaut mieux garder K=0.5 puisqu'une division par 2 d'un float est en fait tres rapide.
Donc, en forcant K a rester 0.5, je trouve:
Pour M=1597466846, C=1.5008788 et K=0.5:
...Erreur maximale=0.087901346%, erreur moyenne = 0.052220062%
Je double pratiquement la precision du resultat en ne changeant que 2 constantes.
Etonnant! non?
Est-ce qu'il y aurait des volontaires pour verifier mes resultats?
Merci d'avance.

Je n'est pas essayer du tout a regarder la precision des resultats apres une iteration avec Newton, mais comme dans l'ensemble, x0 est 2 fois plus precis, je suppose que x1 le sera aussi...