Fast SQRT function for integers

[Administrator]

This is simple and fast SQRT algorithm for integers in range (0..500000):

Code: Select all

int sqrt_int(int x)
{
    unsigned int ret = 44; // starting point is relatively unimportant
    for (int i = 0; i < 6; i++)
    {
        ret = (ret + x / ret) / 2;
    }
    // almost exact for x ~ 1 .. 500000
    return ret;
}

[Administrator]

Fast SQRT for numbers with floating point (based on Quake code):

Code: Select all

#include <stdint.h>

float Q_rsqrt( float number )
{	
	const float x2 = number * 0.5F;
	const float threehalfs = 1.5F;
	union {
		float f;
		uint32_t i;
	} conv = {number}; // member 'f' set to value of 'number'.
	conv.i = 0x5f3759df - ( conv.i >> 1 );
	conv.f *= threehalfs - x2 * conv.f * conv.f;
	return conv.f;
}

Note:
3B/2 = 4B/2 - B/2 =>
- (i << 1) + 0x5f400000;

Improved version:

Code: Select all

float inv_sqrt(float x)
{
	union { float f; uint32 u; }
	y = {x};
	y.u = 0x5F1FFFF9ul - (y.u >> 1);
	return 0.703952253f * y.f * (2.38924456f - x * y.f * y.f);
}

https://habr.com/ru/articles/730872/