Sqrt

From ZDoom Wiki
(Redirected from FixedSqrt)
Jump to navigation Jump to search

int Sqrt (int number)

fixed FixedSqrt (fixed number)

Usage

Returns the square root of an integer or fixed point number.

Parameters

  • number: Value to take the square root of.

Return value

Either the rounded integer or fixed point square root of the number.

Manual calculation

In older versions of ZDoom, the function is not built into ACS so here are several that work fine. Do note that for the distance between to objects the distance function can be faster.

This version uses Newton's method, where the solution converges quadratically from the initial guess. This function has been compared with the following two, and is at least 5 to 10 times faster in normal use.

function int sqrt(int number)
{
	if(number <= 3) { return number > 0; }

	int oldAns = number >> 1,                     // initial guess
	    newAns = (oldAns + number / oldAns) >> 1; // first iteration

	// main iterative method
	while(newAns < oldAns)
	{
		oldAns = newAns;
		newAns = (oldAns + number / oldAns) >> 1;
	}

	return oldAns;
}

This is a simpler, but slower, version of a square root function. It rounds the root up or down.

function int sqrt (int x)
{
	int r;
	x = x + 1 >> 1;
	while (x > r)
		x -= r++;
	return r;
}

If you need a function that rounds down, this one will work. Based off of this algorithm.

function int isqrt (int n)
{
	int a;
	for (a=0;n>=(2*a)+1;n-=(2*a++)+1);
	return a;
}


This sample-based formulae processes fixed values and returns a fixed result which accuracy is defined by the samples integer, and results zero if the input number is negative.

function int sqrt(int number) 
{ 
  int samples=15; //Samples for accuracy

  if (number == 1.0) return 1.0; 
  if (number <= 0) return 0;
  int val = samples<<17 + samples<<19; //x*10 = x<<1 + x<<3
  for (int i=0; i<samples; i++) 
    val = (val + FixedDiv(number, val)) >> 1;

  return val; 
}

This is the same as above but is optimised for 15 samples

function int sqrt(int number) 
{
  if (number == 1.0) return 1.0; 
  if (number <= 0) return 0;
  int val = 150.0;
  for (int i=0; i<15; i++) 
    val = (val + FixedDiv(number, val)) >> 1;

  return val; 
}