7

I'm currently doing distance calculations between coordinates and have been getting slightly different results depending on the language used.

Part of the calculation is taking calculating the cosine of a given radian. I get the following results

// cos(0.8941658257446736)

// 0.6261694290123146 node
// 0.6261694290123146 rust
// 0.6261694290123148 go
// 0.6261694290123148 python
// 0.6261694290123148 swift
// 0.6261694290123146 c++
// 0.6261694290123146 java
// 0.6261694290123147 c

I would like to try and understand why. If you look past 16dp c is the only "correct" answer in terms of rounding. What I am surprised as is python having a different result.

This small difference is being amplified currently and over 000's of positions it is adding a not insignificant distance.

Not really sure how this is a duplicate. Also I am more asking for a holistic answer rather than language specific. I don't have a compute science degree.

UPDATE

I accept that maybe this is too broad a question I suppose I was curious as to why as my background isn't CS. I appreciate the links to the blogs that were posted in the comments.

UPDATE 2

This question arose from porting a service from nodejs to go. Go is even weirder as I am now unable to run tests as the summation of distances varies with multiple values.

Given a list of coordinates and calculating the distance and adding them together I get different results. I'm not asking a question but seems crazy that go will produce different results.

9605.795975874069
9605.795975874067
9605.79597587407

For completeness here is the Distance calculation I am using:

func Distance(pointA Coordinate, pointB Coordinate) float64 {
    const R = 6371000 // Earth radius meters
    phi1 := pointA.Lat * math.Pi / 180
    phi2 := pointB.Lat * math.Pi / 180
    lambda1 := pointA.Lon * math.Pi / 180
    lambda2 := pointB.Lon * math.Pi / 180

    deltaPhi := phi2 - phi1
    deltaLambda := lambda2 - lambda1
    a := math.Sin(deltaPhi/2)*math.Sin(deltaPhi/2) + math.Cos(phi1)*math.Cos(phi2)*math.Sin(deltaLambda/2)*math.Sin(deltaLambda/2)
    c := 2 * math.Atan2(math.Sqrt(a), math.Sqrt(1-a))

    d := R * c
    return d
}
phuclv
  • 37,963
  • 15
  • 156
  • 475
amwill04
  • 1,330
  • 1
  • 11
  • 18
  • 16
    The results you posted are the results _somehow_ displayed to you. That _somehow_ might involve rounding and truncating, varies on languages and the way you print it. For example Go's output is `0.6261694290123148`, but if you use "higher precision" printing like `fmt.Printf("%.25f", v)`, you'll get `0.6261694290123147599302911`. The 16th fraction digit becomes `7` not `8` compared to when printed using the default format. – icza Oct 16 '19 at 11:13
  • 8
    Possible duplicate of [double and accuracy](https://stackoverflow.com/questions/11110130/double-and-accuracy) You are right on the edge and this will depend on how `cos` is implemented and if 80-bit floating point is used for the intermediate results. – Richard Critten Oct 16 '19 at 11:14
  • 6
    Basically you are asking 10 questions in one (like "what does X do in language Y", for 10 different languages). Plus: telling us what you think your code does ... isnt sufficient. See [mcve]. How are supposed to tell you what kind of FP problem you might have, without being able to look at the exact code that created one of those lines?! – GhostCat Oct 16 '19 at 11:15
  • 1
    Its not that difficult to replicate, simply calculating `cosine`, need the exact syntax for every lanuage?? This is using builtins for every language so dont understand what you would like. Im asking a more holistic question as @icza has done – amwill04 Oct 16 '19 at 11:17
  • 4
    Fun fact: In C++ it is very possible that `x = 0.8941658257446736; assert(cos(x) == cos(x + argc/1000));` fires (one might be computed at compile time, the other at run-time, possibly using different methods). See the "Transcendentals" section at https://randomascii.wordpress.com/2013/07/16/floating-point-determinism/. So yes, the exact syntax (and compiler, and flags, and floating point rounding mode, etc.) used may be relevant. – Max Langhof Oct 16 '19 at 11:18
  • If your question is "why does this happen" then I recommend the above blog post (pretty C/C++-specific) as well as [this](https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html). It's just way too broad a question to explain in detail why each language does these things as it does, and I'm not sure if a "because floating point math is not usually an exact science" satisfies you. If you have a more specific question, feel free to express it. – Max Langhof Oct 16 '19 at 11:21
  • Also read about rounding issues: https://randomascii.wordpress.com/2013/07/16/floating-point-determinism/ And Intermediate Precision https://randomascii.wordpress.com/2012/03/21/intermediate-floating-point-precision/ – Richard Critten Oct 16 '19 at 11:22
  • Might also want to look up the "paranoia test" (paranoia.c), which is some old industry standard for determining floating point conformance on different systems. – Lundin Oct 16 '19 at 11:26
  • 1
    Fact remains that you ask 10 questions in 1. That alone renders your question too broad. And yes, sometimes subtle changes MIGHT play out in subtle ways. – GhostCat Oct 16 '19 at 11:38
  • Does “calculations between coordinates” mean you’re calculating the distance between two points on earth? – VGR Oct 16 '19 at 11:41
  • The C result is, in my opinion, the only reasonable one there. – S.S. Anne Oct 16 '19 at 11:43
  • If the problem you are solving is affected by such a small difference in the result of the `cos` calculation, then it also depends just as much on the accuracy of the radian argument to it. It's pretty unlikely you know the argument to the required accuracy. That seems like a more fundamental problem. – pcarter Oct 16 '19 at 11:44
  • @VGR yeah using a simple havisine calculation based upone spherical earth. – amwill04 Oct 16 '19 at 11:50
  • @GhostCat I respectfully disagree. Given the same input the builtin functions provide different results and dont round how I would have expected. Im asking what is at play that accounts for that. Maybe stackoverflow is the right medium to get an answer to that. – amwill04 Oct 16 '19 at 11:52
  • Is it possible your ‘spherical earth’ assumption is the reason for the “not insignificant distance” discrepancies? – VGR Oct 16 '19 at 11:53
  • @VGR the above differences are just from one part of the distance calculation - specifically `cos(radian)`, not the distance its self. – amwill04 Oct 16 '19 at 12:00
  • 1
    Although OP says the C result is the only “correct” answer, it is the only one that is impossible for a correctly rounded display of an IEEE-754 binary64 value. The two nearest representable values are 0.62616942901231464890798861233633942902088165283203125 and 0.6261694290123147599302910748519934713840484619140625, for which correctly rounding to 17 digits produces a numeral ending in 6 or 8, not 7. – Eric Postpischil Aug 20 '20 at 00:01

2 Answers2

2

IEEE-754 only requires basic operations (+-*/) and sqrt to be correctly rounded, i.e. the error must be no more than 0.5ULP. Transcendental functions like sin, cos, exp... are very complex so they're only recommended to be correctly rounded. Different implementations may use different algorithms to calculate the result for those functions depending on the space and time requirements. Therefore variations like you observed is completely normal

There is no standard that requires faithful rounding of transcendental functions. IEEE-754 (2008) recommends, but does not require, that these functions be correctly rounded.

Standard for the sine of very large numbers

See also

phuclv
  • 37,963
  • 15
  • 156
  • 475
  • 1
    “Correctly rounded” and “faithfully rounded” are specific terms in floating-point, and they need to be used carefully. “Properly rounded” is not a specifically defined phrase; it would depend on context as to what “proper” is. “Correct” rounding is the strictest: The floating-point result must be the infinitely precise result rounded to the number uniquely determined by the rounding rules. This is not equivalent to rounding of at most ½ ULP, as the rule for ties must be obeyed. “Faithful” is looser: The result may be one of the two immediately surrounding neighbors. – Eric Postpischil Aug 19 '20 at 23:51
  • The phrase “only recommended to be properly rounded” has “only” near “recommended” although it is more likely intended to modify “properly rounded.” – Eric Postpischil Aug 19 '20 at 23:54
  • 2
    Also worth noting is that humans do not yet know how to evaluate all the “elementary” functions (sine, cosine, logarithm, and so on) with correct rounding in a known-bounded execution time. Nobody would be able to implement a library satisfying IEEE 754’s recommendation with a known bound on execution time without new research. At my suggestion, the committee voted to recommend faithful rounding, but it was changed in balloting after the committee finished its work. – Eric Postpischil Aug 19 '20 at 23:56
1

Generally, the representation of floating point numbers is defined by the standard IEEE 754 and my assumption is that this standard is implemented by all (major) programming languages.

Precision and rounding are known issues and may sometimes lead to unexpected results.

Aspects that may have an influence on the result of a calculation depending on the programming language or used math library:

  • different calculation methods (in your case: the cosine function might be implemented by numerical approximation with different approaches)
  • different rounding strategies during calculation or for the final output
Gerd
  • 2,568
  • 1
  • 7
  • 20