Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

In fact, when Sinnott published the haversine formula, computational precision was limited. Nowadays, JavaScript (and most modern computers & languages) use IEEE 754 64-bit floating-point numbers, which provide 15 significant figures of precision. With this precision, the simple spherical law of cosines formula (cos c = cos a cos b + sin a sin b cos C) gives well-conditioned results down to distances as small as around 1 metre. In view of this it is probably worth, in most situations, using either the simpler law of cosines or the more accurate ellipsoidal Vincenty formula in preference to haversine! (bearing in mind notes below on the limitations in accuracy of the spherical model).
Source: http://www.movable-type.co.uk/scripts/latlong.html

What is the reason why law of cosines is more preferable?

Note: The quoted text has been updated by its author as mentioned bellow.

share|improve this question
7  
How is law of cosines "preferable"? We can answer this in two ways: for the computer and the programmer. For the computer, the haversine formula uses fewer trig functions but requires two square roots. For computational efficiency, then, it's a toss-up. For the programmer, the haversine formula is a bit longer. However, the law of cosines formula requires having an ACos implementation, which is seen a little less frequently than an ATan implementation. Furthermore, to write bulletproof code you have to check that the ACos won't fail. For this reason alone we should prefer haversine. –  whuber Jan 6 '11 at 17:36
2  
I've just implemented haversine and cosine in Python. On this computer haversine takes 3.3μs and cosine takes 2.2μs which is quite significant if you need to do a lot of them –  gnibbler Feb 1 '11 at 0:56
1  
Thanks to everyone for some good observations and information. I've updated the text quoted in the question to be, I hope, rather more objective and helpful. –  ChrisV May 2 '11 at 17:34
    
@ChrisV, thanks for the update! I've moved this to a comment as it isn't directly an answer to the question, thanks for your great site. –  scw May 3 '11 at 23:15
add comment

3 Answers

up vote 26 down vote accepted

The problem is indicated by the word "well-conditioned." It's an issue of computer arithmetic, not mathematics.

Here are the basic facts to consider:

  1. One radian on the earth spans almost 10^7 meters.

  2. The cosine function for arguments x near 0 is approximately equal to 1 - x^2/2.

  3. Double-precision floating point has about 15 decimal digits of precision.

Points (2) and (3) imply that when x is around one meter, or 10^-7 radians (point 1), almost all precision is lost: 1 - (10^-7)^2 = 1 - 10^-14 is a calculation in which the first 14 of the 15 significant digits all cancel, leaving just one digit to represent the result. Flipping this around (which is what the inverse cosine, "acos", does) means that computing acos for angles that correspond to meter-length distances cannot be done with any meaningful accuracy. (In certain bad cases the loss of precision gives a value where acos is not even defined, so the code will break down and give no answer, a nonsense answer, or crash the machine.) Similar considerations suggest you should avoid using the inverse cosine if distances less than a few hundred meters are involved, depending on how much precision you're willing to lose.

The role played by acos in the naive law-of-cosines formula is to convert an angle to a distance. That role is played by atan2 in the haversine formula. The tangent of a small angle x is approximately equal to x itself. Consequently the inverse tangent of a number, being approximately that number, is computed essentially with no loss in precision. This is why the haversine formula, although mathematically equivalent to the law of cosines formula, is far superior for small distances (on the order of 1 meter or less).

Here is a comparison of the two formulas using 100 random point-pairs on the globe (using Mathematica's double-precision calculations).

alt text

You can see that for distances less than about 0.5 meters, the two formulas diverge. Above 0.5 meters they tend to agree. To show how closely they agree, the next plot shows the ratios of the law of cosines:haversine results for another 100 random point pairs, with their latitudes and longitudes randomly differing by up to 5 meters.

alt text

This shows that the law of cosines formula is good to 3-4 decimal places once the distance exceeds 5-10 meters. The number of decimal places of accuracy increases quadratically; thus at 50-100 meters (one order of magnitude) you get 5-6 dp accuracy (two orders of magnitude); at 500-1000 meters you get 7-8 dp, etc.

share|improve this answer
    
Is there some cheap test - e.g. delta latitude > .1 || delta longitude > .1 to dynamically choose either cosine (for large) or haversine (for small distances)? In order to get the best performance and good precision. –  Anony-Mousse Mar 20 '13 at 15:10
    
@Anony-Mousse Both formulas can be off by a few tenths of one percent for distances one-quarter around the world, so by then we're not going to be fussing about precision! Therefore any test that can distinguish close points (a few hundred meters) from nearly diametrically opposite points (around 20 million meters) from everything in between should be sufficient. –  whuber Mar 20 '13 at 15:16
add comment

The cosine formula can be implemented in one line:

  Distance = acos(SIN(lat1)*SIN(lat2)+COS(lat1)*COS(lat2)*COS(lon2-lon1))*6371

The haversine formula takes multiple lines:

  dLat = (lat2-lat1)
  dLon = (lon2-lon1)
  a = sin(dLat/2) * sin(dLat/2) + cos(lat1) * cos(lat2) * sin(dLon/2) * sin(dLon/2)
  distance = 6371 * 2 * atan2(sqrt(a), sqrt(1-a))

Mathematically, there are identical, so the only difference is one of practicality.

share|improve this answer
    
While the original Haversine does not use the computer-related atan2 formula, there's nothing that keeps one from rewriting the 4 lines above into a single formula. –  Arjan Jan 8 '11 at 14:51
    
@Arjan, True, but it would be inefficient because you would need to compute a twice. It's essential that the formula involve both Sqrt(a) and Sqrt(1-a), because although one of these will be numerically unstable for very small or very large distances, the other will not be: that's what makes this approach work. –  whuber Jan 9 '11 at 17:39
    
True, @whuber, but still I doubt the number of lines would ever make me choose one over the other. (And like you're already explained in your answer, there are much more important reasons to favour one.) –  Arjan Jan 9 '11 at 20:38
3  
@Arjan I agree. One's first priority should be adequacy of the code for the programming task. After that I would place clarity: that is, readability, maintainability, and literate documentation. Absent such a context, counting the number of lines of code is meaningless. –  whuber Jan 9 '11 at 21:16
1  
atan2(sqrt(a), sqrt(1-a)) is the same as asin(sqrt(a)) –  user102008 Dec 7 '11 at 2:11
add comment

A historical footnote:

The haversine was a way of avoiding large round-off errors in computations such as

1 - cos(x)

when x is small. In terms of the haversine we have

1 - cos(x) = 2*sin(x/2)^2
           = 2*haversin(x)

and 2*sin(x/2)^2 can be computed accurately even when x is small.

In the old days, the haversine formula had an additional advantage of avoiding an addition (which entailed an antilog lookup, the addition, and a log lookup). A trigonometic formula which entailed only multiplications was said to be in "logarithmic form".

Nowadays, use of the haversine formulas is slightly anachronistic. It might be that the angle x is expressed in terms sin(x) and cos(x) (and x might not be explicitly known). In that case, computing 1 - cos(x) via the haversine formula entails an arctangent (to get the angle x), halving (to get x/2), a sine (to get sin(x/2)), a square (to get sin(x/2)^2) and a final doubling. You are far better off using evaluating

1 - cos(x) = sin(x)^2/(1 + cos(x))

which entails no evaluations of trigonometric functions. (Obviously use the right hand side only if cos(x) > 0; otherwise, it's OK to use 1 - cos(x) directly.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.