does Math.Sqrt(double) use "asm fsqrt"?

[not_a_commie]

Does Math.Sqrt(double) use the Intel assembly command to run the
square root or does it have its own implementation? I ask because my
hand-coded, two-bits-per-iteration square root function is only 10%
slower than Math.Sqrt. I have the same question about
Math.Atan2(double). I ask this because I have a known target
architecture and I'm attempting to squeeze a bit more speed out of my
geometric search algorithm that relies heavily on Math.Sqrt(double)
and Math.Atan2(double).

 

[Peter Webb]

Does Math.Sqrt(double) use the Intel assembly command to run the
square root or does it have its own implementation? I ask because my
hand-coded, two-bits-per-iteration square root function is only 10%
slower than Math.Sqrt. I have the same question about
Math.Atan2(double). I ask this because I have a known target
architecture and I'm attempting to squeeze a bit more speed out of my
geometric search algorithm that relies heavily on Math.Sqrt(double)
and Math.Atan2(double).

I am almost certainly the least qualified person in this newsgroup to answer
your direct question, but I have implemented something which appears similar
and is (I believe) quite fast. Its pretty simple, so excuse me if this is
too obvious ...

If I want to find out if (x1, y1) is within "dist" of (x2, y2), I use:

if ((abs(x1-x2)<=(dist)) & (abs(y1-y2)<=dist))
if ((Math.Sqrt((x1-x2)^2 + Math.Sqrt(y1-y2)^2) <=dist)
{}

This checks if (y1, y2) lies in the Rectangle (x1-dist, y1-dist, x1+dist,
y1+dist). The Rectangle class even provides a direct method for seeing if a
point is inside a rectangle, and you could use this instead to check if your
point is in the square box.

If the point isn't in this square box, then it cannot be within the
equivalent circle. If most of your points are more than dist away from your
reference point, these will be filtered with just one or two subtractions
and compares. The overhead for points actually within dist is tiny, and if
these are a small minority - as they often are - it becomes even more
negligible.

 

[Norman Diamond]

I am almost certainly the least qualified person in this newsgroup to
answer your direct question,
me2.

but I have implemented something which appears similar and is (I believe)
quite fast.

If I want to find out if (x1, y1) is within "dist" of (x2, y2), I use:

if ((abs(x1-x2)<=(dist)) & (abs(y1-y2)<=dist))
if ((Math.Sqrt((x1-x2)^2 + Math.Sqrt(y1-y2)^2) <=dist)
{}

I think you almost mean
if ((abs(x1-x2)<=(dist)) & (abs(y1-y2)<=dist))
if (Math.Sqrt((x1-x2)^2 + (y1-y2)^2) <=dist)
{}
with one mathematical correction and one syntactic correction, though you
still have to use something other than the exclusive or operator to get
those squares, and some other syntax remains odd but works.

I can beat it.
if ((abs(x1-x2)<=(dist)) & (abs(y1-y2)<=dist))
if (((x1-x2)^2 + (y1-y2)^2) <=dist^2)
{}
though I still have to use something other than the exclusive or operator to
get those squares, and some other syntax remains odd but works.

 

[Arne Vajhøj]

Does Math.Sqrt(double) use the Intel assembly command to run the
square root or does it have its own implementation? I ask because my
hand-coded, two-bits-per-iteration square root function is only 10%
slower than Math.Sqrt.

I believe .NET uses the fsqrt instruction for Math.Sqrt().

It is easy to verify that .NET and C seems to calculate at
the same speed.

I would very much like to see your "only 10% slower" algorithm.

Arne

 

[Peter Webb]

I think you almost mean
if ((abs(x1-x2)<=(dist)) & (abs(y1-y2)<=dist))
if (Math.Sqrt((x1-x2)^2 + (y1-y2)^2) <=dist)
{}
with one mathematical correction and one syntactic correction, though you
still have to use something other than the exclusive or operator to get
those squares, and some other syntax remains odd but works.

I can beat it.
if ((abs(x1-x2)<=(dist)) & (abs(y1-y2)<=dist))
if (((x1-x2)^2 + (y1-y2)^2) <=dist^2)
{}
though I still have to use something other than the exclusive or operator
to get those squares, and some other syntax remains odd but works.

OK, I must of thought I was in sci.math.

Apart from trivial corrections to other people's posts, have you anything to
add yourself?

 

[Willy Denoyette [MVP]]

Does Math.Sqrt(double) use the Intel assembly command to run the
square root or does it have its own implementation? I ask because my
hand-coded, two-bits-per-iteration square root function is only 10%
slower than Math.Sqrt. I have the same question about
Math.Atan2(double). I ask this because I have a known target
architecture and I'm attempting to squeeze a bit more speed out of my
geometric search algorithm that relies heavily on Math.Sqrt(double)
and Math.Atan2(double).

It depends on the platform it is running on.
32-bit code on X86 and on X64-86 uses the X87 FPU, so it uses 'sqrt' for
Math.Sqrt, while 64-bit code on X64-86 , uses the (faster) SSE2 'sqrtds'
instruction.


Willy.

 

[not_a_commie]

I would very much like to see your "only 10% slower" algorithm.

It ends up I had a bug in my test case that was causing an incorrect
early exit. My code (below) is 3 to 4 times slower than Math.Sqrt. It
seems to run slightly faster when returning s directly instead of
using out but that may be just because some functionality for
returning r gets optimized out. Just for fun, is anyone here good
enough to refactor this function to not have any branching in it
(well, maybe leave the for loop in)?

static void Sqrt(uint n, out uint s, out uint r)
{
// source: http://scholar.google.com/url?sa=U&q=http://www.cp.eng.chula.ac.th/~krerk/publication/iscit-sqrt.pdf
const uint hibit = 0x80000000; // 1<<(bitlen - 1)
s = 0; // result: actually ushort
r = 0; // remainder: actually ushort + 1
for (int i = 15; i >= 0; i--) // (bitlen>>1)-1
{
if ((r & hibit) == 0)
{
r = (r << 2) | (n >> (i << 1) & 3);
r -= ((s << 2) | 1);
}
else
{
r = (r << 2) | (n >> (i << 1) & 3);
r += ((s << 2) | 3);
}
if ((r & hibit) == 0)
s = ((s << 1) | 1);
else
s = (s << 1);
}

if ((r & hibit) != 0)
r += ((s << 1) | 1);
}

 

[Ben Voigt [C++ MVP]]

OK, I must of thought I was in sci.math.

Apart from trivial corrections to other people's posts, have you anything
to add yourself?

Eliminating the square root, although well known, is a huge performance
improvement over your formula.

BTW it is also the wrong and operator, you should use logical and (&&) to
get short circuiting, then you wouldn't need the nested if at all.

 

[Norman Diamond]

Well I thought so at the time, but since then I've been disproven.

Eliminating the square root, although well known, is a huge performance
improvement over your formula.

But clearly, eliminating the square root is not well known. I did it, but
Peter Webb proved that it wasn't a contribution. Peter Webb must of thought
he was in sci.math where eliminating the square root isn't well known and
isn't a contribution.

 

[Peter Webb]

Eliminating the square root, although well known, is a huge performance
improvement over your formula.

Ummm ... the whole point of my change was to eliminate the square root -
unless the test value lies within the "box", we don't check if it is in the
circle (which uses square root).

BTW it is also the wrong and operator, you should use logical and (&&) to
get short circuiting, then you wouldn't need the nested if at all.

I was trying to describe the algorithm. By the way, for all the nitpickers
out there, I believe the appropriate function is not abs(), its Math.Abs().
Of course, as I was explaining an algorithm, I sort of expected people to
know what I was talking about ...

 

[Peter Webb]

Well I thought so at the time, but since then I've been disproven.


But clearly, eliminating the square root is not well known. I did it, but
Peter Webb proved that it wasn't a contribution. Peter Webb must of
thought he was in sci.math where eliminating the square root isn't well
known and isn't a contribution.

So I guess the answer to my question is, "No, you have nothing to contribute
other than trivial corrections to other people's posts".

 

[Peter Webb]

Ummm ... the whole point of my change was to eliminate the square root -
unless the test value lies within the "box", we don't check if it is in
the circle (which uses square root).



I was trying to describe the algorithm. By the way, for all the nitpickers
out there, I believe the appropriate function is not abs(), its
Math.Abs(). Of course, as I was explaining an algorithm, I sort of
expected people to know what I was talking about ...

Whoops, sorry, you presumably meant replace the condition in the inner if
with

if (a^2 + b^2 < c^2) instead of if (sqrt(a^2 + b^2) < c)

This is valid, but is in the inner loop (I was trying to show how to avoid
the inner loop). It also may not help much, if at all. As the OP also wants
Atan(a,b) its pretty likely that he actually wants sqrt(a^2 + b^2) as he is
presumably calculating the x and y separation. So the square root cannot be
avoided; just delayed.

Note that I have used mathematical symbols here, not C# code. Sorry. The ^
character means exponentiation - so for example c^2 is shorthand for c*c. I
am sorry if anybody is unfamiliar with this usage.

 

[not_a_commie]

Well, I did manage to remove the branching. Of course I still could
not out run the hardware asm fsqrt command (go figure ;-).

static void Sqrt(uint n, out uint s, out uint r)
{
// source: http://scholar.google.com/url?sa=U&q=http://www.cp.eng.chula.ac.th/~krerk/publication/iscit-sqrt.pdf
s = 0; // result: actually ushort
r = 0; // remainder: actually ushort + 1
for (int i = 30; i >= 0; i-=2) // bitlen - 2
{
r = ((r << 2) | (n >> i & 3))
- ((s << 2) | 1) * (~r >> 31)
+ ((s << 2) | 3) * (r >> 31);
s = ((s << 1) | (~r >> 31));
}
r += ((s << 1) | 1) * (r >> 31);
}

PS I am using length squared where I can. Unfortunately the ACos
function that I need in various places doesn't play so nice with
length squared as its input.