Algorithms for computing Pythagoras Sum

While helping a friend of mine with programming assignments, I stumbled upon a question on two different algorithms of calculating Pythagoras Sum (Pythagoras Addition), through a function called pythag

One algorithm is straight-forward, which is just  c = \sqrt{a^2 + b^2}. \,

The other, however, is very intriguing, it makes use of absolute, min, max and several lines of weird mathematical operations to get the result.

Not knowing what the second method does or why it even existed, I turned to my friend Google.

There are not much resources on the topic of Pythagoras Sum, but I managed to find both implementations in various programming languages:

Python (1st algorithm):

Haskell (1st algorithm):

C (2nd algorithm):

Fortran (2nd algorithm):

After digging a little deeper on Google, I managed to find the origin of the 2nd algorithm, it is in fact invented by Moler, Cleve and Donald Morrison.

The original paper is titled Replacing Square Roots by Pythagorean Sums published on IBM Journal of Research and Development.

In this paper, it is highlighted that this algorithm has several advantages over the simple one (directly quote from paper):

  • No destructive floating point overflows or underflows are possible
  • Can be extended to compute Euclidean norm of a vector
  • Particularly attractive for computers where space and reliability are more important than speed
  • Potentially faster than a square root

This is an interesting discovery because it is an example of the case where the obvious and simple solution may not be the best solution.

Leave a Reply