"Magic Constant" 0x5f3759df

In this article we will talk about the "magic" constant 0x5f3759df, which is the basis of an elegant algorithmic trick to quickly calculate the inverse square root .

Here is the full implementation of this algorithm:

float FastInvSqrt(float x) {
  float xhalf = 0.5f * x;
  int i = *(int*)&x;  //   float    
  i = 0x5f3759df - (i >> 1);  //     ?
  x = *(float*)&i;
  x = x*(1.5f-(xhalf*x*x));
  return x;
}

( )



, Quake III Arena 2005 . - , , – Ardent Computer, 80- . , ( ), Quake.
, -1 1.

, , , .

?

, , ? , 3D . 3D . ( ) , , .. . , , . ( ) ? . , , :



. – . – — FastInvSqrt.

?

? . ( float) i integer ( ).

int i = *(int*)&x;         //   float    

,

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

, , , , . , , . , int float.

x = *(float*)&i;

, , .

x = x*(1.5f-(xhalf*x*x));

. ( ) – , . №2: , int. .

?

, . , ( ). : , . 32- :



, 8 23 . , , ( 0).

, . , , ( ). , , 0 1, .. 0, – ( ) 1. , 8- , ( ), -127 128. float- m. , (, ) (, m) – (float).

:





32- L = 2^23, = 127. e m, :



:



, “” . , :



, , , 2 :



, , , :



. , . , , , , .
:



v 0 1. , v 0 1 :



:



σ – . , σ , . , , , , , , :



-! :



( ), , :







. , y, , :



: “y ( ) – ”. :

i = K - (i >> 1);

, ?

K. B L, σ.
, σ – “ ”, 0 1. .. . 0.0450465, . , :



, 1597463007 HEX? , , 0x5f3759df. , , σ , .

, ( , hex-), .

, : “ , , , ”. , , :



1 100. , ? , , , , .

!

0x5f3759df, .

-, L B. , . , 64- 128- – .

-, - σ. ( – ) x + σ . σ , . , σ , .

-, “-1/2” . - , (“ ”). , , -1 1. , “-1/2” :



=0.5 ( ) :




:

i = 0x1fbd1df5 + (i >> 1);

, ? , :



, , , . , ?
“” , :





, :

i = (int) (0x2a517d3c + (0.333f * i));

, - 1/3 0.333f. :

!

, : . , . :



, -1 1:

i = (1 - p) * 0x3f7a3bea + (p * i);

, :

i = 0x3f7a3bea + p * (i - 0x3f7a3bea);

“” , ( -1 1). , , . , , (, ).

“ ” 0x3f7a3bea. (- ) “ ”, . .

, p = 0. , 0 . ? – 0 :

i = 0x3f7a3bea;

, , float-, 0.977477 – .. “ 1”. – . , - . . ( “ ”)
. :

C :



, , . – , . :



. , , , . :



:



, , :



, σ ( 0.0450465) 2 , 0.97747675, , “ 1”. :

float sigma = 0.0450465;
float c_sigma = 1 - (0.5f * sigma);
int C_sigma = *(*int)&c_sigma;

, σ . 0x3f7a3beb, 0x3f7a3bea , 1 ( ). ( ) , 1.5.

, “”, “”, “”, “” , , . , float int – “”, . , , , . , , – .