Return to Answer

Efforts were made in the past to optimize sqrt. Although it no longer applies to today's machines, here is an example from the Quake source code, which uses the magic number 0x5f3759df:

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 hell?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration (optional)
  // ...
  return y;
}

A detailed explanation of what's going on here can be found on Wikipedia.

In short, it is a few iterations of Newton's method (a numerical algorithm which iteratively improves an estimate), with the magic number used to provide a reasonable initial estimate.

As Travis points out, this kind of optimization is no longer useful on modern architectures. And even if it was, it could only provide a constant rate speedup to your bottleneck, whilst algorithmic redesign might achieve better results.

Efforts were made in the past to optimize sqrt. Although it no longer applies to today's machines, here is an example from the Quake source code, which uses the magic number 0x5f3759df:

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 hell?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration (optional)
  // ...
  return y;
}

A detailed explanation of what's going on here can be found on Wikipedia.

In short, it is a few iterations of Newton's method (a numerical algorithm which iteratively improves an estimate), with the magic number used to provide a reasonable initial estimate.

As Travis points out, this kind of optimization is no longer useful on modern architectures. And even if it was, it could only provide a constant rate speedup to your bottleneck, whilst algorithmic redesign might achieve better results.

Efforts were made in the past to optimize sqrt. Although it no longer applies to today's machines, here is an example from the Quake source code, which uses the magic number 0x5f3759df:

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 (optional)
  // ...
  return y;
}

A detailed explanation of what's going on here can be found on Wikipedia.

In short, it is a few iterations of Newton's method (a numerical algorithm which iteratively improves an estimate), with the magic number used to provide a reasonable initial estimate.

As Travis points out, this kind of optimization is no longer useful on modern architectures. And even if it was, it could only provide a constant rate speedup to your bottleneck, whilst algorithmic redesign might achieve better results.

Efforts were made in the past to optimize sqrt. Although it no longer applies to today's machines, here is an example from the Quake source code, which uses the magic number 0x5f3759df:

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 hell?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration (optional)
  // ...
  return y;
}

A detailed explanation of what's going on here can be found on Wikipedia.

In short, it is a few iterations of Newton's method (a numerical algorithm which iteratively improves an estimate), with the magic number used to provide a reasonable initial estimate.

As Travis points out, this kind of optimization is no longer useful on modern architectures. And even if it was, it could only provide a constant rate speedup to your bottleneck, whilst algorithmic redesign might achieve better results.

If you really want to optimize sqrt, and you are writing in C, you could try using Quake's magic number 0x5f3759df

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 (optional)
  // ...
  return y;
}

A detailed explanation of what's going on here can be found on Wikipedia.

In short, it is a few iterations of Newton's method (a numerical algorithm which iteratively improves an estimate), with the magic number used to provide a reasonable initial estimate.

Efforts were made in the past to optimize sqrt. Although it no longer applies to today's machines, here is an example from the Quake source code, which uses the magic number 0x5f3759df:

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 (optional)
  // ...
  return y;
}

A detailed explanation of what's going on here can be found on Wikipedia.

In short, it is a few iterations of Newton's method (a numerical algorithm which iteratively improves an estimate), with the magic number used to provide a reasonable initial estimate.

As Travis points out, this kind of optimization is no longer useful on modern architectures. And even if it was, it could only provide a constant rate speedup to your bottleneck, whilst algorithmic redesign might achieve better results.