I recently rewrote some code that calculates the distance between 2 latitude/longitude coordinates. I was using a method that used Pythagoras, which assumes Earth is flat. Apparently this works well for distances under 20 km, but my app needs to deal with all of Ontario, which is larger that 20 km. I came across the haversine formula, which assumes a spherical Earth. Still not 100% accurate (the Earth is an ellipsoid, and has mountains and valleys) but much closer.

Some of the example implementations I found in JavaScript (about 1 screen down) and C# were oddly similar. Same variable names, no code comments that indicate an understanding of the algorithm.

I sat with the Wikipedia article open in one window and the JavaScript version on the other until I understood what was going on. (Basically, haversin(x) = (sin(x/2))^2 so you can use a language’s sin function to calculate it.) Though, I still don’t understand why atan2 is used to calculate the inverse of haversin and not arcsin (or even what atan2 does). My inverse implementation uses arcsin, but I wrote a parallel one that uses atan2 and gives the same result for the few unit tests I wrote. Given that these are trig functions I ‘m pretty confident this isn’t a coincidence.

I was happy with my implementation, but a few things still bothered me. What’s the relationship between atan2 and arcsin? What’s the derivation of the haversine formula? It should be high school or first year trig, but I don’t get it. I could probably keep Googling and refresh my knowledge at Khan Academy, but I’ve spent enough time for now. I have a house and family to tend to too. (This was a personal project so no employer time was harmed in the writing of this article.)

But it got me wondering about the thinking behind the C# example I found vs. what I did. I think you could tell the difference between 4 types of programmers with this interview question:

You’re writing an app that needs a mathematical algorithm. Nothing too fancy, but the math is just a little beyond you because it’s been 10 to 15 years since you really understood trig/calculus/algebra/stats. You Google for it and find the following:

- Info on the theory behind the algorithm on, say, Wikipedia
- Some code example in your programming language on various websites

How do you proceed?

This shouldn't be presented as multiple choice. You’re looking for answers of the following types:

A. Copy the code examples into your code and move on.

B. Use the code examples as inspiration for you own version, perhaps with a little refactoring and variable renaming and move on.

C. Use the Wikipedia article to write your own implementation from scratch, adding comments to document what each complex bit does, and move on.

D. Do C and spend some time trying to understand how the algorithm was derived and why it works.

If you answered A you now have 2 problems. You now have code that you can’t support because you don’t understand it, and it’s probably a copyright violation. SCO will find you. Next applicant please.

If you answered B you’ve avoided the copyright problem but you still don’t understand the algorithm. Junior programmer material.

If you answered C, nice work. You have code that you understand and that others can understand. It’s a well known algorithm so it’s not vital that you can explain why it works. Just keep the URLs to your research handy, or add them to your comments for justification. Welcome, new senior developer.

If you answered D there is a follow up question – how much time did you spend? An hour or two, or did you get lost down a rabbit hole and spend a whole afternoon (as I did)? If you spent just a couple of hours you get the team lead job, whether you stopped because you figured things out or you knew enough to not spend any more time. If you spent a whole afternoon, you still get the senior developer position, but you need to learn some hardcore time management skills before advancing.

Diving deep into a problem is pretty typical of good coders but the very best keep this tendency in check. This is where a personal system of organization can save you from rabbit holes. Or at least let you get your code out the door and look into the lingering details at an appropriate time.

PS:

I now understand the relationship between arcsin and atan2, and why the JavaScript examples are written the way they are.

First, the inverse of haversin(x) is

haversin^{-1}(x) = 2sin^{-1}(√x)

Second, the relationship between arcsin and arctan is

sin^{-1}(x) = tan^{-1}(x/√(1-x^{2}))

So,

haversin^{-1}(x)= 2tan^{-1}(√x/√(1-x))

When x > 0 the atan2(y,x) function in most languages gives you

tan^{-1}(y/x)

So,

haversin^{-1}(x) = 2*atan2(Math.Sqrt(x)/Math.Sqrt(1-x))

I suppose this is a handy definition for those languages that don’t have an inverse sine function but do have inverse tan.

I still don’t understand why the haversine function works, but that’s fine. I’m now confident my implementation that uses inverse sine is equivalent and I’m moving on.

## No comments:

## Post a Comment