Magic Numbers et Jeux Vidéo - Historique des versions

Ncuneo le 24 mars 2025 à 20:06

2025-03-24T20:06:33Z

← Version précédente		Version du 24 mars 2025 à 20:06
Ligne 67 :		Ligne 67 :


	La méthode de Newton Raphson est une méthode itérative qui permet de trouver une ~~approximation~~ ~~d'une~~ ~~racine~~.		La méthode de Newton Raphson est une méthode itérative qui permet de trouver une racine par approximation successive.

	Cela signifie que la précision de notre résultat dépend uniquement du nombre d'itération appliqué à notre nombre initial.		Cela signifie que la précision de notre résultat dépend uniquement du nombre d'itération appliqué à notre nombre initial.

Ncuneo le 23 mars 2025 à 19:57

2025-03-23T19:57:55Z

← Version précédente		Version du 23 mars 2025 à 19:57
Ligne 54 :		Ligne 54 :


	<h1 style="font-family:Impact, Haettenschweiler, 'Arial Narrow', sans-serif">Méthode ~~pour~~ ~~calculer~~ ~~des~~ ~~racines carrés~~</h1>		<h1 style="font-family:Impact, Haettenschweiler, 'Arial Narrow', sans-serif">Méthode de normalisation de vecteur</h1>

Ncuneo le 9 mars 2025 à 20:41

2025-03-09T20:41:55Z

← Version précédente		Version du 9 mars 2025 à 20:41
Ligne 206 :		Ligne 206 :


	[[Fichier:Noah_cuneo_newtonvsquake3.png\|none\|400px\|thumb\|~~Perception~~ - ~~jeu~~ ~~réalisé en VISI301~~]]		[[Fichier:Noah_cuneo_newtonvsquake3.png\|none\|400px\|thumb\|Benchmark des deux méthodes]]
			(Python étant un langage haut niveau, la lecture bitwise est moins efficace qu'avec un langage bas niveau.)

			(Un benchmark en C est en préparation quand j'aurais trouvé une librarie graphique pour le C)

	Comme nous l'attendions, la méthode des carré inverse rapide est plus... rapide.		Comme nous l'attendions, la méthode des carré inverse rapide est plus... rapide.

Ncuneo le 9 mars 2025 à 20:39

2025-03-09T20:39:52Z

← Version précédente		Version du 9 mars 2025 à 20:39
Ligne 199 :		Ligne 199 :

	<h2 style="font-family:Impact, Haettenschweiler, 'Arial Narrow Bold', sans-serif">Quel méthode est la meilleure ?</h2>		<h2 style="font-family:Impact, Haettenschweiler, 'Arial Narrow Bold', sans-serif">Quel méthode est la meilleure ?</h2>


			Faisons un test pour savoir quelle méthode est la plus rapide. Même si nous avons déjà une petite idée après ce que nous avons vu.

			En réalisant les deux méthodes sur Python, et en testant le temps d'éxecution des 2 sur plusieurs milliers de valeurs. Nous pouvons obtenir ce graphique.


	[[Fichier:Noah_cuneo_newtonvsquake3.png\|none\|400px\|thumb\|Perception - jeu réalisé en VISI301]]		[[Fichier:Noah_cuneo_newtonvsquake3.png\|none\|400px\|thumb\|Perception - jeu réalisé en VISI301]]


			Comme nous l'attendions, la méthode des carré inverse rapide est plus... rapide.

			Nous serions donc tentés de dire : "Mais dans ce cas, utilisons seulement cette méthode pour calculer des carré inverse !".

			Eh bien non. Cette méthode est extrêmement imprécise. Et dans certains cas, la précision est une question de vie ou de mort.

			Voyons le problème d'une autre manière.

			La méthode des carrés rapide est plus rapide, mais limité. C'est à dire qu'elle s'arrête dès qu'elle a faite son travail.

			La méthode de Newton-Raphson est lente, mais peux subir un nombre illimité d'itération qui nous approche à chaque fois de la bonne valeur. Mais encore une fois, on ne connait pas le nombre minimum d'itération nécessaire à avoir une bonne valeur.

			Pour palier le problème, les personnes travaillant sur le moteur Quake III on tout simplement décidé qu'ils allaient utiliser la méthode des carré inverse rapide, puis une itération de Newton-Raphson par dessus pour de la précision.

			Ainsi, pour une première approximation qui aurait pris plusieurs itération avec Newton-Raphson, et bien nous l'avons en une utilisation des carré inverse rapide.

			Cette dernière étant imprécise, nous rajoutons une itération de Newton-Raphson qui nous rapproche grandement de la valeur finale.

Ncuneo le 9 mars 2025 à 20:22

2025-03-09T20:22:01Z

← Version précédente		Version du 9 mars 2025 à 20:22
Ligne 113 :		Ligne 113 :

	<h2 style="font-family:Impact, Haettenschweiler, 'Arial Narrow Bold', sans-serif">Méthode des carré inverse rapide</h2>		<h2 style="font-family:Impact, Haettenschweiler, 'Arial Narrow Bold', sans-serif">Méthode des carré inverse rapide</h2>


			La méthode des carré inverse rapide a été inventée pour le moteur de jeu quake III, afin d'optimiser les calculs graphique (dont énormément de normalisation de vecteur).

			Cette méthode est très intéressante puisqu'elle se base sur la représentation des flottant en binaire pour se réaliser. C'est le genre d'opération que l'on appelle bitwise.

			Voici la méthode pas à pas :

			- Nous avons notre nombre <math>x</math>, que nous représentons en binaire en tant que flottant (IEEE 754 32bit). C'est à dire avec un signe, un exposant et une mantisse.

			- Nous allons maintenant considérer ce flottant, comme si c'était un nombre entier en binaire. Nous appellerons cette variable <math>xi</math>

			- Nous appliquons maintenant la relation : <math> i = 0x5f3759df - \left( \frac{x_i}{2} \right) </math>

			- Nous considérons maintenant que le résultat i est un flottant.

			- Nous trouvons donc le carré inverse : <math>\frac{1}{\sqrt{x}}</math>


			Mais comment cela peut fonctionner ? Faisons d'abord une application numérique sur 25 pour y voir plus clair :


			- Nous représentons 25 en IEEE 754 32bit : <math>0 10000011 10010000000000000000000</math>

			- Nous appliquons la relation vu ci dessous, en lisant notre flottant comme un entier (0x41C80000) : <math> i = 0x5f3759df - \left( \frac{0x41C80000}{2} \right) </math>

			- Nous lisons notre résultat (0x3F6DDB3F) comme étant un flottant.

			- Nous trouvons 0.2, qui est bien le carré inverse de 25 : <math>\frac{1}{\sqrt{25}}</math>


			Après avoir lu l'expression littérale et l'application numérique de cette méthode, vous devez vous demander d'où sort le nombre 0x5f3759df. Et bien c'est un magic number.

			Pourquoi ce magic number en particulier ? Et pourquoi cette méthode fonctionne en agissant sur un flottant comme il était entier ?

			Pour répondre à ces questions, il faut se pencher sur la représentation binaire d'un flottant.

			Les nombres flottants sont représentés de tel sorte :

			- 1 bit : le signe du nombre (0 pour positif, 1 pour les négatifs)

			- 8 bits : pour l'exposant décalé, on dit qu'il est décalé puisque il faut soustraire 127 à la valeur binaire pour obtenir l'exposant. (qui peut être négatif ducoup)

			- 23 bits : la mantisse, c'est à dire la partie significative du nombre.

			Par exemple, convertissons le nombre 12.75 en flottant binaire :

			- 12.75 se représente en binaire (1100.11). Car 1100 vaut 12. 075 vaut 0.5 + 0.25, donc 1/2 + 1/4. Qui sont les deux premières puissance de 2 négatives/

			- On normalise le nombre pour l'avoir en écriture scientifique : 1.10011 * 2^3

			- Le signe vaut 0 (nombre positif)

			- L'exposant vaut 130, car on a 3 auquel on ajoute le décalage de 127. L'exposant vaut alors 130 en binaire 10000010.

			- La mantisse, c'est les nombres après la virgule : 10011...comblé avec des 0.

			- On a donc 12.75 = 0 10000010 10011000000000000000000


			A l'inverse, on peut obtenir un nombre flottant grâce à cette formule, avec S le signe, M la mantisse, E l'exposant et N le nombre que l'on cherche :

			<math>
			N = (-1)^S \times 1.M \times 2^{(E-127)}
			</math>


			Donc dans notre méthode des carré inverse rapide, lorsque nous considérons notre flottant comme un entier et qu'on le divise par deux, nous décalons en fait tous les bits à droite.

			Ce qui revient à diviser l'exposant par deux, et à modifier la mantisse (en fonction du contenu de l'exposant).

			Or, diviser l'exposant par deux en base deux revient à diviser le logarithme de l'exposant par deux. Ce qui est proche de ce que ferait une racine carré.

			Nous avons donc une première approximation, qu'en est il du magic number ?

			Et bien ce magique number sert en réalité d'affinage à notre première approximation. Il à été trouvé de façon empirique et permet d'avoir une approximation assez précise lorsqu'il est soustrait de notre nombre précédent.

			Puis à la fin nous relisons notre nombre en flottant, nous obtenos biens la racine carré inverse.

Ncuneo le 9 mars 2025 à 18:52

2025-03-09T18:52:54Z

@@ Ligne 51 : / Ligne 51 : @@
 Si je vous demande de calculer la racine carré de 2531 de tête vous n'y arriverai certainement pas. Pour notre pc c'est pareil, il ne sort pas ce résultat par magie.
 <h1 style="font-family:Impact, Haettenschweiler, 'Arial Narrow', sans-serif">Méthode pour calculer des racines carrés</h1>
-Dans cette partie, nous allons donc nous intéresser à deux algorithmes :
+Dans cette partie, nous allons nous intéresser à deux algorithmes :
 - Celui de Newton-Raphson
@@ Ligne 68 : / Ligne 65 : @@
 <h2 style="font-family:Impact, Haettenschweiler, 'Arial Narrow Bold', sans-serif">Méthode Newton-Raphson</h2>
 [[Fichier:Noah_cuneo_newtonvsquake3.png|none|400px|thumb|Perception - jeu réalisé en VISI301]]

Ncuneo le 25 février 2025 à 00:29

2025-02-25T00:29:13Z

← Version précédente		Version du 25 février 2025 à 00:29
Ligne 52 :		Ligne 52 :

	Pour sortir ce résultat, il utilise l'algorithme de Newton-Raphson qui permet de calculer la racine carré d'un nombre.		Pour sortir ce résultat, il utilise l'algorithme de Newton-Raphson qui permet de calculer la racine carré d'un nombre.

			(En vrai dans les nouveaux processeurs les calculs de racine sont mieux optimisés aujourd'hui)

	Intéressons nous à cet algorithme.		Intéressons nous à cet algorithme.

Ncuneo le 25 février 2025 à 00:15

2025-02-25T00:15:43Z

← Version précédente		Version du 25 février 2025 à 00:15
Ligne 66 :		Ligne 66 :

	<h2 style="font-family:Impact, Haettenschweiler, 'Arial Narrow Bold', sans-serif">Méthode Newton-Raphson</h2>		<h2 style="font-family:Impact, Haettenschweiler, 'Arial Narrow Bold', sans-serif">Méthode Newton-Raphson</h2>

			[[Fichier:Noah_cuneo_newtonvsquake3.png\|none\|400px\|thumb\|Perception - jeu réalisé en VISI301]]

Ncuneo le 25 février 2025 à 00:11

2025-02-25T00:11:21Z

← Version précédente		Version du 25 février 2025 à 00:11
Ligne 56 :		Ligne 56 :

	<h1 style="font-family:Impact, Haettenschweiler, 'Arial Narrow', sans-serif">Méthode pour calculer des racines carrés</h1>		<h1 style="font-family:Impact, Haettenschweiler, 'Arial Narrow', sans-serif">Méthode pour calculer des racines carrés</h1>


			Dans cette partie, nous allons donc nous intéresser à deux algorithmes :

			- Celui de Newton-Raphson

			- Celui de la racine carré inverse rapide


	<h2 style="font-family:Impact, Haettenschweiler, 'Arial Narrow Bold', sans-serif">Méthode Newton-Raphson</h2>		<h2 style="font-family:Impact, Haettenschweiler, 'Arial Narrow Bold', sans-serif">Méthode Newton-Raphson</h2>

Ncuneo le 24 février 2025 à 21:00

2025-02-24T21:00:31Z

← Version précédente		Version du 24 février 2025 à 21:00
Ligne 4 :		Ligne 4 :

	== Introduction ==		== Introduction ==

	Les Magic Numbers, c'est mal !		Les Magic Numbers, c'est mal !

Ligne 56 :		Ligne 55 :
	Intéressons nous à cet algorithme.		Intéressons nous à cet algorithme.

	<h1 style="font-family:Impact, Haettenschweiler, 'Arial Narrow', sans-serif">~~Normaliser~~ un ~~vecteur~~</h1>		<h1 style="font-family:Impact, Haettenschweiler, 'Arial Narrow', sans-serif">Méthode pour calculer des racines carrés</h1>

			<h2 style="font-family:Impact, Haettenschweiler, 'Arial Narrow Bold', sans-serif">Méthode Newton-Raphson</h2>