Q_rsqrt()float Q_rsqrt( float number ){ long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed return y;}12345678910111213141516id Software - GPLv2Gary Tarolli 3dfx InteractiveBrian Hook 3dfx Interactiveid SoftwareJohn Carmack id SoftwareWilliam Kahanunpublished paper 1986"The Father of Floating Point"Cleve MolerArdent ComputerMatLab1999Greg WalshArdent Computerlongfloata historyThe story of void VectorNormalizeFast( vec3_t v ){ float ilength; ilength = Q_rsqrt( DotProduct( v, v ) ); v[0] *= ilength; v[1] *= ilength; v[2] *= ilength;}long00000000 00000000 00000000 00000000000000000 00000000 00000000 00000001100000000 00000000 00000000 00000010200000000 00000000 00000000 000000113...01111111 11111111 11111111 111111112 147 483 647float(IEEE 754 single precision)0 00000000 0000000 00000000 00000000float(sign)0 00000000 0000000 00000000 00000000float(exponent)0 0000000 00000000 00000000± 0.0 x 2float(mantissa) 0.000000 00000000 000000000 1 sign bit 000000100 000000000 00000000 0000000 00000000 00000000Links8 exponent bits[0,255]Scientific notationfloat(IEEE 754 exemples)1 00000000 0000000 00000000 00000000-00-0.00000000 01111111 0000000 00000000 00000000+1270+1.00000000 10000000 1001001 00001111 11011011+1284788187+3.14159270 01101011 0000110 00110111 10111101+1035685141+0.00000010 → +1 → -± 0.0 x 20± 0.0 x 2000000000 00000000 00000000 00000000≠ 0float(mantissa) 0000000 00000000 000000000 00000000 .± 0.0 x 20µµµ± 1.0 x 20yyyyiii0x5f3759df// what the fuck?i = 0x5f3759df - ( i >> 1 ); yyyyyyyiy8 shifted exponent bits[0,255] - 127 ⇒ [-127,128]2-12728 shifted exponent bits[0,255] - 127 ⇒ [-127,128]00000010100000012-1272 = 22-127-1252 = 2129-1272[0,2 -1] ≠ [0,1[2300000000 ....... ........ ........0000000 00000000 000000000000000 00000000 00000000// evil floating point bit level hackingi = * ( long * ) &y;y&yfloat*float00000000 00000000 00000000 00000000(long*)&ylong193549ffi00000000 00000000 00000000 00000000long// 1st iteration - Newton-Raphson's methody = y * ( threehalfs - ( x2 * y * y ) ); approximation errorapproximation error %Newton-Raphson'smethodpow(number, -0.5f)1 / sqrt(number)Q_rsqrt(number)_mm_rsqrt_ss(number)95%50%medianeInkscapeSozisprites© id SoftwareJérôme Labidurie - 2024MerciQuestions ?Lighting, Shading & ReflectioncalculationsSurface normalsfield of unit vectors normal to a surfaceQuake ]|[ Fast Inverse Square RootQ_rsqrt(number) number⇔SourcesHistory - Rys Sommefeldt (Beyond3D )https://www.beyond3d.com/content/articles/8/https://www.beyond3d.com/content/articles/15/The Maths behind the rsqrt function - Charles McEniryhttp://www.daxia.com/bibis/upload/406Fast_Inverse_Square_Root.pdfWikipediahttps://en.wikipedia.org/wiki/Fast_inverse_square_rootFast Inverse Square Root — A Quake III Algorithm - Nemeanhttps://www.youtube.com/watch?v=p8u_k2LIZyoThe Truth about the Fast rsqrt on the N64 - Kaze Emanuarhttps://www.youtube.com/watch?v=tmb6bLbxd08Q_rsqrt()Jérôme LabidurieCC:BY-SAenglish
1
  1. Intro
  2. Why ?
  3. Vectors
  4. History
  5. line 1
  6. line 3
  7. long
  8. line 4
  9. line 5
  10. float sign
  11. float exponent
  12. float mantissa
  13. float exemples
  14. line 9
  15. evil1
  16. line 10
  17. float bits
  18. log 1+x
  19. WTF
  20. line 11
  21. line 12
  22. newton
  23. line 13
  24. approx
  25. line 15
  26. benchmark
  27. This is the end