What is the best way to find a distance between two points in 2D without using Pythagorean theorem?

To some extent it depends on how much inaccuracy you are willing to live with and what resources you have available.  Lookup tables can approximate square roots (or trigonometric functions), and a sufficiently large lookup table might work for your application.  What range of values do you expect to see, and what degree of precision is necessary? Another approach is to use parallelism to increase the number of distances computed at once.  If you can vectorize the operation, then the latency of a single multiplication or square-root extraction will not be as critical.  For example, the Intel SSE extension contains a SQRTPS instruction which can calculate four single-precision square roots at once.  You might also be able to achieve greater instruction-level parallelism by interleaving multiple distance computations.

Using trigonometric function is an alternative for Pythagorean method. Here are the two steps: 1. find the angle between horizontal line and hypotenuse.     θ=tan−1|y2−y1||x2−x1|\theta= \tan ^{ - 1}\frac{|y2-y1|}{|x2-x1|}  2. Hypotenuse length or the distance = |x2−x1|cos(θ)\frac{|x2-x1|}{cos(\theta)} Now if you have table lookups for cos and arctan functions (only in the range [0 , \pi/2] is required), execution can be faster. Comments on the Edited part of the question: The earth co-ordinates are not given in cartesian co-ordinate systems. Latitude and longitudes are angles and not distances. So, you can not simply apply Pythagoras theorem for distance calculation on earth. For more advanced algorithms, check out Harvesine formula (based on spherical model of earth) and Vincenty's formula (based on oblate spheroid model of earth).

There are algorithms for finding "pythagorean sums" -- the distances you refer to -- without computing square roots, or even without any multiplications or divisions.  The Moler-Morrison algorithm is fastest for high-precision calculations (http://www.scribd.com/doc/29568822/Moler-Morrison-Pythagorean-Sums), and for fast calculation without hardware multiply or divide (or square root), the CORDIC arc-tangent calculation (http://www.convict.lu/Jeunes/Math/arctan.htm) uses only addition and subtraction, and produces the pythagorean sum as a byproduct. If you are interested only in rank-ordering the distances, note that you don't need to take square roots; rank ordering by the square of the distance (that is, x^2 + y^2) is sufficient. If your X,Y coordinates are latitude and longtude, the distances cannot be calculated as simple pythagorean sums.

IF, as you say, the coordinates are latitudinal and longitudinal analogues, then you wouldn't use the Pythagorean theorem at all, as you're dealing with spherical coordinates ornithologically projected.  The best way, therefore to deal with this problem would be to use a modified CORDIC or BKM algorithm.  This algorithm, using nothing more than the standard four mathematical operators and bit shifts,can determine hyperbolic, trigonometric, exponential, and logarithmic expressions in under 50 iterations (for 12+ place accuracy).