inv_sqrt.cpp File Reference

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

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

Include dependency graph for inv_sqrt.cpp:

Go to the source code of this file.

Functions
template<typename T = double, char iterations = 2>
T	Fast_InvSqrt (T x)
	for std::sqrt
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
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

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.

Definition in file inv_sqrt.cpp.

Function Documentation

Fast_InvSqrt()

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

T Fast_InvSqrt ( T x )

inline

for std::sqrt

for assert for IO operations for numeric_limits

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

Definition at line 28 of file inv_sqrt.cpp.

                           {
    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

Definition at line 87 of file inv_sqrt.cpp.

           {
    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;
}

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

Definition at line 59 of file inv_sqrt.cpp.

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

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 68 of file inv_sqrt.cpp.

                   {
    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);
}