Using Math. for Fix32

[urben1680]

Hello, I currently write my own version of a 32bit integer fixed-point math.

I only have square root left to do, and all these custom sqrt algorithms seem to be still slower than just performing the regular Math.Sqrt and cast it to int. The Dijkstras Square Root you seem to use is for example ~10 times slower than using+casting Math.Sqrt.

So I wonder if I just should do that. Rounding errors, which you try to avoid by using Fix math, are no matter here as the raw number has no point anyway, after which the machine-dependent rounding errors occurs.

Would like to hear your opinion on this. This is not really an "issue" but I am not sure how else to ask on Github.

[asik]

If you can be confident Math.Sqrt will give you the same results on all runtimes and machines you're targeting, then by all means feel free to use it. I think that on older versions of .NET, the 32-bit runtime will emit FSQRT while newer ones will use equivalent SSE instruction.

[urben1680]

I decided to not use it as I cannot be sure it generates the same result. What I did instead is creating a lookup table. The value of index i is Convert.ToInt32((i+0.5)*(i+0.5)) so using BinarySearch results in finding the value without need to check for rounding. Only thing to do is getting the absolute value. First tests indicate it is just 4 times slower than Math.Sqrt on my machine.

I am not sure if it is useful for you too as your binary tree would be twice as high at Fix64 and probably won't be as fast per step when using long.

[asik]

The tradeoff is going be in accuracy, unless you make the LUT huge. Especially with numbers very close to 0, given the nature of sqrt. But maybe it'd be worth having a FastSqrt if it's good enough.

[urben1680]

In the case of 32bit integers there are just sqrt(2^31-1) possible numbers which can be squared without overflow. So my table only needs that many entries and is as accurate as possible.

64bit integers need a tree with 1024 times the filesize if you want the same accuracy but of course that is going to be too huge.

[asik]

Ah it's a reverse lookup and you find the value by binary search, ok yeah that's a good idea. Thanks for sharing.

[urben1680]

I want to give you an update as I again worked on my Sqrt function. My earlier descibed method does not work as I miscalculated how big the LUT has to be (I forgot it is not just natural numbers). It is not efficient at all anymore. Turned out that the method you use is still the fastest suited for me.

But I accomplished another thing. I came up with a method that calculates Pythagoras' theorem, which calculates the long side of a right-angled triangle. This method is 20% faster than when used Sqrt for the same task.

• I first calculate the ratio of a and b, with a being the smaller number.
• Then I put the value into my LUT with precalculated numbers of sqrt(value*value+1).
• The result is multiplied with b using my fixed-point multiply method.
• Now I have c with the highest possible precision.

The LUT contains 2^precision_bits numbers. In my case 2^18.

The LUT might turn out too big for you and Pythagoras' theorem is not that important for this case, but still you might find this interesting. I skipped how I came up with the LUT but if you really want to know that I can add that as well.