inv_sqrt.cpp File Reference

Implementation of the inverse square root Root. More...

#include <cassert>
#include <cmath>
#include <iostream>
#include <limits>

Include dependency graph for inv_sqrt.cpp:

Functions
template<typename T = double, char iterations = 2>
T	Fast_InvSqrt (T x)
	for numeric_limits More...
template<typename T = double>
T	Standard_InvSqrt (T number)
	This is the function that calculates the fast inverse square root. The following code is the fast inverse square root with standard lib (cmath) More information can be found at LinkedIn More...
static void	test ()
	Self-test implementations. More...
int	main ()
	Main function. More...

Detailed Description

Implementation of the inverse square root Root.

Two implementation to calculate inverse inverse root, from Quake III Arena (C++ version) and with a standard library (cmath). This algorithm is used to calculate shadows in Quake III Arena.

Function Documentation

Fast_InvSqrt()

template<typename T = double, char iterations = 2>

T Fast_InvSqrt ( T  x )

inline

for numeric_limits

for assert for std::sqrt for IO operations

This is the function that calculates the fast inverse square root. The following code is the fast inverse square root implementation from Quake III Arena (Adapted for C++). More information can be found at Wikipedia

Template Parameters

T	floating type
iterations	inverse square root, the greater the number of iterations, the more exact the result will be (1 or 2).

Parameters

x	value to calculate

Returns

the inverse square root

                           {
    using Tint = typename std::conditional<sizeof(T) == 8, std::int64_t,
                                           std::int32_t>::type;
    T y = x;
    T x2 = y * 0.5;
 
    Tint i =
        *reinterpret_cast<Tint *>(&y);  // Store floating-point bits in integer
 
    i = (sizeof(T) == 8 ? 0x5fe6eb50c7b537a9 : 0x5f3759df) -
        (i >> 1);  // Initial guess for Newton's method
 
    y = *reinterpret_cast<T *>(&i);  // Convert new bits into float
 
    y = y * (1.5 - (x2 * y * y));  // 1st iteration Newton's method
    if (iterations == 2) {
        y = y * (1.5 - (x2 * y * y));  // 2nd iteration, the more exact result
    }
    return y;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();  // run self-test implementations
    std::cout << "The Fast inverse square root of 36 is: "
              << Fast_InvSqrt<float, 1>(36.0f) << std::endl;
    std::cout << "The Fast inverse square root of 36 is: "
              << Fast_InvSqrt<double, 2>(36.0f) << " (2 iterations)"
              << std::endl;
    std::cout << "The Fast inverse square root of 100 is: "
              << Fast_InvSqrt(100.0f)
              << " (With default template type and iterations: double, 2)"
              << std::endl;
    std::cout << "The Standard inverse square root of 36 is: "
              << Standard_InvSqrt<float>(36.0f) << std::endl;
    std::cout << "The Standard inverse square root of 100 is: "
              << Standard_InvSqrt(100.0f)
              << " (With default template type: double)" << std::endl;
}

Here is the call graph for this function:

Standard_InvSqrt()

template<typename T = double>

T Standard_InvSqrt

(

T

number

)

This is the function that calculates the fast inverse square root. The following code is the fast inverse square root with standard lib (cmath) More information can be found at LinkedIn

Template Parameters

T	floating type

Parameters

number

value to calculate

Returns

the inverse square root

                             {
    T squareRoot = sqrt(number);
    return 1.0f / squareRoot;
}

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    const float epsilon = 1e-3f;
 
    /* Tests with multiple values */
    assert(std::fabs(Standard_InvSqrt<float>(100.0f) - 0.0998449f) < epsilon);
    assert(std::fabs(Standard_InvSqrt<double>(36.0f) - 0.166667f) < epsilon);
    assert(std::fabs(Standard_InvSqrt(12.0f) - 0.288423f) < epsilon);
    assert(std::fabs(Standard_InvSqrt<double>(5.0f) - 0.447141f) < epsilon);
 
    assert(std::fabs(Fast_InvSqrt<float, 1>(100.0f) - 0.0998449f) < epsilon);
    assert(std::fabs(Fast_InvSqrt<double, 1>(36.0f) - 0.166667f) < epsilon);
    assert(std::fabs(Fast_InvSqrt(12.0f) - 0.288423) < epsilon);
    assert(std::fabs(Fast_InvSqrt<double>(5.0f) - 0.447141) < epsilon);
}

Here is the call graph for this function: