Java-Gaming.org Java4K winners: [ by our judges | by the community ]         
Featured games (67)
games approved by the League of Dukes 		Games in Showcase (∞)
games submitted by our members



News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Java-Gaming.org > Game Development > Performance Tuning > sqrt(x) and 1/sqrt(x)
Pages: [1]
  Print  
  sqrt(x) and 1/sqrt(x)  (Read 2007 times)
0 Members and 1 Guest are viewing this topic.
Offline Roquen

JGO Strike Force
***

Posts: 827
Medals: 25
« on: 2009-08-08 10:37:36 »
Popular way to approximate sqrt(x) and 1/sqrt(x):

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
  public static float isqrt(float x)
  {
    float hx = x * 0.5f;
    int   ix;
    float r;

    // make initial guess
    ix = Float.floatToRawIntBits(x);
    ix = 0x5f3759df - (ix>>1);
    r  = Float.intBitsToFloat(ix);

    // do some number of newton-ralphson steps,
    // each doubles the number of accurate
    // binary digits.
    r  = r*(1.5f-hx*r*r);
  //r  = r*(1.5f-hx*r*r);
  //r  = r*(1.5f-hx*r*r);
  //r  = r*(1.5f-hx*r*r);

    return r;    // 1/sqrt(x)
  //return r*x;  // sqrt(x)
  }
Offline woogley

JGO Neuromancer
****

Posts: 1098
Medals: 5
« Reply #1 on: 2009-08-08 13:45:26 »
Here's some background on how this technique works: http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/
Offline DzzD

JGO Kernel
*****

Posts: 2134
Medals: 16
« Reply #2 on: 2009-08-08 13:57:32 »
very nice


EDIT : tested.... and unfortunatly due to the slowness of Float.floatToIntBits(x) it seems to doesn't give any performance gain
Web 3D Engine - Racer3D Web - Viewer3D - Panorama 3D - VOR2
Games published by our own members! Go get 'em!
Offline Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5870
Medals: 255


Hand over your head.
« Reply #3 on: 2009-08-08 14:37:39 »
replace
Float.floatToIntBits()

by
Float.floatToRawIntBits()

maybe it speeds up the 'conversion'
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline Roquen

JGO Strike Force
***

Posts: 827
Medals: 25
« Reply #4 on: 2009-08-08 14:46:54 »
Yeah, I just logged in to note using 'raw' instead comment (bad me).  The 'guess' part can be changed to something else (such as a small table for limited ranges).

Another thing to note is for renormalizing vectors, quaternions, etc. ... the guessed value is '1' and normally a single N-R step will commonly give you the renormalization multiplier.

(edit: many typos)
Offline Roquen

JGO Strike Force
***

Posts: 827
Medals: 25
« Reply #5 on: 2009-08-08 15:07:20 »
Quote from: Roquen on 2009-08-08 14:46:54
Yeah, I just logged in to note using 'raw' instead comment (bad me).  The 'guess' part can be changed to something else (such as a small table for limited ranges).

Another thing to note is for renormalizing vectors, quaternions, etc. ... the guessed value is '1' and normally a single N-R step will commonly give you the renormalization multiplier. (edit: I'm pretty sure I have a better method for refining than N-R, post here if you'd like me to try to dig it up:  Kahan-Ng refinement).

(edit: many typos)
Pages: [1]
  Print  
 
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.16 | SMF © 2011, Simple Machines Valid XHTML 1.0! Valid CSS!
Page created in 0.265 seconds with 20 queries.