Euclidian distance - optimization and casting

Question

I'm trying to optimize a simple Euclidian distance function in C. It's for a DLL, and calculates distances from one point to many. I have:

Version 1:

int CalcDistance (int y1, int x1, int *y2, int *x2, int nb , int *distances)
{
    double dx,dy = 0;

    for (int i = 0;i<nb;i++)
    {
        dx = x2[i] - x1;
        dy = y2[i] - y1;

        distances[i]=(int)sqrt((dx*dx)+(dy*dy));
    }

    return nb;
}

Version 2:

int CalcDistance (int y1, int x1, int *y2, int *x2, int nb , int *distance)
{
    int dx,dy =0;

    for (int i = 0;i<nb;i++)
    {
        dx = x2[i] - x1;
        dy = y2[i] - y1;

        distances[i]=(int)sqrt((double)(dx*dx)+(dy*dy));
    }

    return nb;
}

Essentially, I don't need extra high precision, so that's why I'm cutting down to ints, not doubles. For my specific use case, the final distance will not be larger than what an int (Int32) can hold.

I was taken aback by how slow version 2 was. I figured that in Version 1 calculating dx and dy would implicitly cast to double twice, whereas in version 2 I'm just explicitly casting once. What's happening? And ultimately, what could be even faster?

(And I tried _hypot, which was oddly the slowest of all...)

Answer 1

dstances[i]=(int)sqrt((dx*dx)+(dy*dy));

This only converts to double once. it will do all the math integer style and and then convert it to a double just before calling sqrt.

    distances[i]=(int)sqrt((double)(dx*dx)+(dy*dy));

This is actually the same as:

    distances[i]=(int)sqrt(  ((double)(dx*dx))   + (dy*dy));    

not:

    distances[i]=(int)sqrt((double)(  (dx*dx)) + (dy*dy)  );    

As a result it will convert dx*dx to double, then convert dy*dy to double then add them and the pass it off to sqrt.

In modern computers floating point numbers are really fast, in some cases even faster then integers. As a result, you well be much better off to use double throughout rather then converting from ints to doubles and back again. The conversion between int and double is expensive so avoiding it may actually be your best bet.

A common trick used in algorithms which need to work with distances is to rework the algorithm so that you can use the square of the distance. That way you can avoid the expensive sqrt call. This works because x*x < y*y iff x < y. Be careful though, whether or not you can do this depends on what you are doing with that distance.

Answer 2

Even if the result fits in an int, dx*dx might overflow. Better cast before multiplying

sqrt((double)dx*dx+(double)dy*dy); 

Answer 3

Depending on the x,y values, you could consider using floats instead of doubles. This should help a bit.

Answer 4

If you really need the distance, I have no idea, but if you just need it to compare distances, you can omit the sqrt-function, which is oftten pretty costly. Of course you should rename the function for that purpose.