Winquake-friendly sqrt function.

[Orion]

I've seen a method of finding square roots 'without' a calculator by hand these days, with very little margin of error.
I decided to transform this method to a QC function, and I've got pretty close ingame results.

Here's the function:

Code: Select all

float(float n) sqrt =
{
   local float divisor, result, i;

   if (n < 0)
   {
      dprint ("impossible!\n");
      return -1;
   }

   if (n == 0 || n == 1)
      return n;   // that's pretty obvious

   divisor = 2;   // start at 2
   result = n / divisor;
   while (divisor != result || i < 100)   // for safety issues, don't do more than 100 tries
   {
      divisor = (divisor + result) / 2;
      result = n / divisor;
      i = i + 1;
   }

   return result;
};


Now to explain how this works.
No matter if you give an even or odd number, it will start dividing it by 2, and checks if the result is equal to the divisor, if it is not then it will try several times making averages between divisors and results until both are the same, or if it tries it 100 times it will return the closest number possible.
Let's say a number we know the square root, 9 (which is 3) and simulate how it finds the square root.

It begins like this: 9/2 = 4.5 (divisor != result)
So it begins doing averages in the while() loop.
divisor = (2 + 4.5) / 2 = 3.25 (this is the new divisor)

Now 9 will be divided by 3.25, an then the process repeats.
9/3.25 = 2.769231 (divisor still != result)
divisor = (3.25 + 2.769231) / 2 = 3.009616 (we're getting close)

9/3.009616 = 2.990415
divisor = (3.009616 + 2.990415) / 2 = 3.000016 (almost there)

9/3.000016 = 2.999984
divisor = (3.000016 + 2.999984) / 2 = 3.

9/3 = 3 (divisor == result, so return this value)


I've tested it ingame with sprints, and for example the square root of 10 gave me 3.162278, and Windows calculator gave me 3.162277660168379. Which is pretty close.
So, for those who want to make a non-dp mod of some sorts, here's an useful function if you need. But of course, DP's builtin sqrt() is still much better.

[qbism]

Very cool. For Winquake, even fewer iterations might be accurate enough. I'm going to look up DP sqrt to see why it's better...

n<1 returns n. Should that be if (n=1 || n=0)? Could it calculate the sqrt of 0.4 for example? Maybe there is no case in Quake where it matters.

[mh]

DP's is better because it's using an engine builtin. sqrt is a native hardware op these days so emulating it in QC is never going to be as fast.

[Cobalt]

Nice job!

[qbism]

"Most" engines updated any time during the last 10 years will have a few built-in math functions. From QIP engine:

Code: Select all

// 2001-09-16 Quake 2 builtin functions: sin, cos, sqrt, etos by id/Maddes  start
    {  60, "sin", PF_sin },
    {  61, "cos", PF_cos },
    {  62, "sqrt", PF_sqrt },
    {  63, "changepitch", PF_changepitch },   // 2001-09-16 Quake 2 builtin functions by id/Maddes
    {  64, "TraceToss", PF_TraceToss },      // 2001-09-16 Quake 2 builtin functions by id/Maddes
    {  65, "etos", PF_etos },
// 2001-09-16 Quake 2 builtin functions: sin, cos, sqrt, etos by id/Maddes  end