def Q_rsqrt(number):
threehalfs = 1.5
x2 = number * 0.5
y = np.float32(number)
i = y.view(np.int32) # evil floating point bit level hacking
i = np.int32(0x5f3759df) - np.int32(i >> 1) # what the fuck?
y = i.view(np.float32)
y = y * (threehalfs - (x2 * y * y)) # 1st iteration
# y = y * (threehalfs - (x2 * y * y)) # 2nd iteration, this can be removed
return float(y)1/√ x, mais genre… vraiment vite
Motivation
- Les inverses des racines carrées d’un nombre à virgule flottante sont utilisées pour calculer un vecteur normalisé.
- En synthèse d’image 3D, ces vecteurs normalisés sont utilisés pour déterminer l’éclairage et l’ombrage.
- Des millions de ces calculs sont ainsi nécessaires chaque seconde.
Est-ce que cette approximation est bonne?
Est-ce que cette approximation est bonne?
Est-ce que cette approximation est bonne?
Les entiers non signés
Entiers non signés
La représentation binaire non signée sur \(n\) bits d’un entier \(x\) est le train de bits correspondant à l’écriture de \(x\) en base 2.
Par exemple, en utilisant 8 bits:
Entiers signés
Entiers signés
La représentation binaire signée sur \(n\) bits d’un entier est le train de bit où le premier bit de gauche représente le signe (positif si le bit est 0 et négatif si le bit est 1), et où les \(n-1\) bits restants représentent l’écriture de \(|x|\) en base 2.
Par exemple sur huit bits:
Entiers signés
Entiers signés
La représentation binaire signée sur \(n\) bits d’un entier est le train de bit où le premier bit de gauche représente le signe (positif si le bit est 0 et négatif si le bit est 1), et où les \(n-1\) bits restants représentent l’écriture de \(|x|\) en base 2.
Par exemple sur huit bits:
Les entiers signés
- En pratique, les nombres négatifs sont représentés un peu différemment, à l’aide du complément à deux.
- Nous voulons calculer l’inverse de la racine carrée d’un nombre.
- Nous supposons que le nombre est positif.
- Le bit à gauche est toujours
0.
Le format entier long
- 32 bits au total
- 1 bit pour le signe
- 31 bits pour la mantisse
- Le maximum représentable est \(2^{31}-1=2\ 147\ 483\ 647\)
Un exemple “célèbre”
- On représente l’entier 1 346 269 en utilisant un
entier long.
C’est le 31ème nombre de la suite de Fibonacci.
La norme IEEE 754
Le format simple précision
- 32 bits au total
- 1 bit pour le signe \(S_x\)
- 8 bits pour l’exposant \(E_x\) biaisé (biais de 127)
- 23 bits pour la mantisse \(M_x\) (de \(0\) à \(2^{23}-1\))
Un exemple “célèbre”
- On représente \(\pi\) en utilisant le format
simple précision.
\[ \pi \approx (-1)^0 \cdot 2^{128-127} \cdot \left(1+\frac{4\ 788\ 187}{2^{23}} \right) \]
\[ \pi \approx 1 \cdot 2^1 \cdot 1,570796371 \]
La représentation précédente donne \(\pi \approx 3,141592741\).
Trains de bits
- Un
entier longsur 32 bits.
- Un flottant
simple précisionsur 32 bits.
Trains de bits
- Représente l’entier 1078530011.
- Représenté par
0x40490fdb.
- Représente le nombre décimal 3,1415927.
- Aussi représenté par
0x40490fdb.
Trains de bits
- Posons \(L=2^{23}\).
- Lorsqu’on interprète le nombre en virgule flottante comme un entier, nous avons \(R_x = E_x \cdot L + M_x\).
Trains de bits
- Posons \(L=2^{23}\).
- Lorsqu’on interprète le nombre en virgule flottante comme un entier, nous avons \(R_x = E_x \cdot L + M_x\).
Décalage à gauche (<<)
- En base décimale un décalage à gauche représente une multiplication par 10.
- En base binaire, un décalage à gauche correspond à une multiplication par 2.
Décalage à droite (>>)
- En base décimale un décalage à droite représente une division par 10 (on arrondit à l’entier inférieur).
- En base binaire, un décalage à droite correspond à une division par 2 (on arrondit à l’entier inférieur).
La méthode de Newton
evil floating point bit level hacking
- À quoi vous fait penser ce graphique??
evil floating point bit level hacking
evil floating point bit level hacking
evil floating point bit level hacking
evil floating point bit level hacking
i = np.int32(0x5f3759df) - np.int32(i >> 1) # what the fuck?def Q_rsqrt(number):
threehalfs = 1.5
x2 = number * 0.5
y = np.float32(number)
i = y.view(np.int32) # evil floating point bit level hacking
i = np.int32(0x5f3759df) - np.int32(i >> 1) # what the fuck?
y = i.view(np.float32)
y = y * (threehalfs - (x2 * y * y)) # 1st iteration
# y = y * (threehalfs - (x2 * y * y)) # 2nd iteration, this can be removed
return float(y)On assigne à la variable number, la valeur de \(\pi\).
def Q_rsqrt(number):
threehalfs = 1.5
x2 = number * 0.5
y = np.float32(number)
i = y.view(np.int32) # evil floating point bit level hacking
i = np.int32(0x5f3759df) - np.int32(i >> 1) # what the fuck?
y = i.view(np.float32)
y = y * (threehalfs - (x2 * y * y)) # 1st iteration
# y = y * (threehalfs - (x2 * y * y)) # 2nd iteration, this can be removed
return float(y)La variable y est un nombre à virgule flottante simple précision.
def Q_rsqrt(number):
threehalfs = 1.5
x2 = number * 0.5
y = np.float32(number)
i = y.view(np.int32) # evil floating point bit level hacking
i = np.int32(0x5f3759df) - np.int32(i >> 1) # what the fuck?
y = i.view(np.float32)
y = y * (threehalfs - (x2 * y * y)) # 1st iteration
# y = y * (threehalfs - (x2 * y * y)) # 2nd iteration, this can be removed
return float(y)On interprète la valeur mémorisée y comme un entier long, plutôt que comme un nombre à virgule flottante simple précision,
def Q_rsqrt(number):
threehalfs = 1.5
x2 = number * 0.5
y = np.float32(number)
i = y.view(np.int32) # evil floating point bit level hacking
i = np.int32(0x5f3759df) - np.int32(i >> 1) # what the fuck?
y = i.view(np.float32)
y = y * (threehalfs - (x2 * y * y)) # 1st iteration
# y = y * (threehalfs - (x2 * y * y)) # 2nd iteration, this can be removed
return float(y)On effectue le décalage à droite de la variable i
def Q_rsqrt(number):
threehalfs = 1.5
x2 = number * 0.5
y = np.float32(number)
i = y.view(np.int32) # evil floating point bit level hacking
i = np.int32(0x5f3759df) - np.int32(i >> 1) # what the fuck?
y = i.view(np.float32)
y = y * (threehalfs - (x2 * y * y)) # 1st iteration
# y = y * (threehalfs - (x2 * y * y)) # 2nd iteration, this can be removed
return float(y)La variable i est obtenue en soustrayant le décalage à droite précédent et le magic number \(0x5F3759DF\).
def Q_rsqrt(number):
threehalfs = 1.5
x2 = number * 0.5
y = np.float32(number)
i = y.view(np.int32) # evil floating point bit level hacking
i = np.int32(0x5f3759df) - np.int32(i >> 1) # what the fuck?
y = i.view(np.float32)
y = y * (threehalfs - (x2 * y * y)) # 1st iteration
# y = y * (threehalfs - (x2 * y * y)) # 2nd iteration, this can be removed
return float(y)On réinterprète la variable i comme un nombre à virgule flottante simple précision.
def Q_rsqrt(number):
threehalfs = 1.5
x2 = number * 0.5
y = np.float32(number)
i = y.view(np.int32) # evil floating point bit level hacking
i = np.int32(0x5f3759df) - np.int32(i >> 1) # what the fuck?
y = i.view(np.float32)
y = y * (threehalfs - (x2 * y * y)) # 1st iteration
# y = y * (threehalfs - (x2 * y * y)) # 2nd iteration, this can be removed
return float(y)On effectue une itération de la méthode Newton.
def Q_rsqrt(number):
threehalfs = 1.5
x2 = number * 0.5
y = np.float32(number)
i = y.view(np.int32) # evil floating point bit level hacking
i = np.int32(0x5f3759df) - np.int32(i >> 1) # what the fuck?
y = i.view(np.float32)
y = y * (threehalfs - (x2 * y * y)) # 1st iteration
# y = y * (threehalfs - (x2 * y * y)) # 2nd iteration, this can be removed
return float(y)La seconde itération de la méthode Newton n’est pas nécessaire.
La valeur réelle est \(\frac{1}{\sqrt{\pi}}=0,56418958\ldots\)