How to approximate the Euclidean distance on an integer plane, without overflow?

Question

I am working on a platform that only has integer arithmetic. The application uses geographical information, and I present the points at the coordinates (x, y), where x and y are the distances measured in meters. As an approximation, I want to calculate the Euclidean distance between two points. But for this, I have square distances, and with 32-bit integers the largest distance I can represent is 32 kilometers. Not good. My needs are more than about 1,000 kilometers. But I would like to be able to allow distances on a scale of less than 30 meters.

Therefore, my question is: how can I calculate the Euclidean distance using only integer arithmetic without overflow , at distances whose squares do not fit in a single word?

ETA: I would like to be able to calculate distances, but I could agree to be able to compare them.

Answer 1

Perhaps comparing the octagonal approximation of the distance ?

This article is a bit more modern about fast approximate distance functions .

Answer 2

I would leave the square offside so that I could approximate the Euclidean distance. However, when comparing distances, this approach gives you 100% accuracy, since the comparison will be the same if you divide the distances by the distance.

I am pretty sure of this, since I used this approach when searching for the nearest neighbors in arrogant spaces. You can check my code and theory in kd-GeRaF .