I was recently exposed to the oddity of the SquareRoot function in Starcraft 2's Engine.
For example
SquareRoot(10.5) ==> 3.2402
This is quite far, and in a strange manner so, from the correct value (computed from a python console):
10.5**0.5 = 3.24037034920393
However, it seems to do better with integers (though I am still using the fixed/real version), for example it computes the square root of 24 as 4.899, which is accurate at least to that many digits.
Does anyone know what this function is actually doing? Is there a way to find out? This is quite curious.
Are you familiar with the difference between floating point and fixed point number? SC2 doesn't use FPU, and the fixed type is the way around it, which comes at the cost of low precision.
Fixed type consists of 32 bits:
--------------------------------------------------- -- 1 sign | 19 integer part | 12 fractional part -- ---------------------------------------------------
I won't tell you how the internal implementation of this function looks like, as I don't really know myself. But there are certainly couple of methods it could've been done.
SquareRoot(10.5) ==> 3.2402
The result was trimmed to 4 decimal places, but in reality it is exactly equal to .240234375 (result of 984/4096). The next possible value would be .240478515625 (result of 985/4096). What is above the expected result of sqrt, thus it returned the closest possible that was equal - rounded down.
The fractional part of 10.5 is represented as 2048/4096. Now if you iterate over next possible values:
This function sc2_sqrt(x) produces the same results as SC2 now.
The real moral here is just that SC2 uses a fixed-precision data type as described by Talv. If any unusual behavior comes up, it's because of how the values are stored.
I was recently exposed to the oddity of the SquareRoot function in Starcraft 2's Engine.
For example
This is quite far, and in a strange manner so, from the correct value (computed from a python console):
However, it seems to do better with integers (though I am still using the fixed/real version), for example
it computes the square root of 24 as 4.899, which is accurate at least to that many digits.
Does anyone know what this function is actually doing? Is there a way to find out? This is quite curious.
Are you familiar with the difference between floating point and fixed point number?
SC2 doesn't use FPU, and the fixed type is the way around it, which comes at the cost of low precision.
Fixed type consists of 32 bits:
I won't tell you how the internal implementation of this function looks like, as I don't really know myself. But there are certainly couple of methods it could've been done.
The result was trimmed to 4 decimal places, but in reality it is exactly equal to .240234375 (result of 984/4096).
The next possible value would be .240478515625 (result of 985/4096). What is above the expected result of sqrt, thus it returned the closest possible that was equal - rounded down.
The fractional part of 10.5 is represented as 2048/4096. Now if you iterate over next possible values:
So yeah, that's as far as explanation goes.
btw. You can increase the verbosity of FixedToText when it comes to decimal places - it just defaults to 4 at most.
Previously known as: SomeoneTookMyNameTT
Thanks, the specification for their fixed type is very helpful. I will investigate further in my spare time :)
It looks like it's very simple knowing that. Reproducing SC2's results was as simple as (python again):
This function sc2_sqrt(x) produces the same results as SC2 now.
The real moral here is just that SC2 uses a fixed-precision data type as described by Talv. If any unusual behavior comes up, it's because of how the values are stored.
Here is code for C#
public double SquareRoot(double x) { double a = Math.Pow((int)(x * 4096) / (double)(4096), 0.5); return (int)(a * 4096) / (double)(4096); }