How to approximate Euclidean distance on the integer plane, without overflow?
<p>I'm working on a platform that has only integer arithmetic.  The application uses geographic information, and I'm representing points by <em>(x, y)</em> coordinates where <em>x</em> and <em>y</em> are distances measured in meters.
As an approximation, I want to compute the Euclidean distance between two points.  But to do this I have to square distances, and with 32-bit integers, the largest distance I can represent is 32 kilometers.  Not good.
My needs are more on the order of 1000 kilometers.  But I'd like to be able to resolve distances on a scale smaller than 30 meters.</p>

<p>Hence my question: <strong>how can I compute Euclidean distance, using only integer arithmetic, without overflow</strong>, on distances whose squares don't fit in a single word?</p>

<p>ETA: I would like to be able to compute distances, but I might settle for being able to compare them.</p>