How hard can it be to write a simple four-function calculator program? After all, computers are good at math, and making a calculator isn’t exactly blazing a new trail, right? But [Chad Nauseam] will tell you that it is harder than you probably think. His post starts with a screenshot of the iOS calculator app with a mildly complex equation. The app’s answer is wrong. Android’s calculator does better on the same problem.
What follows is a bit of a history lesson and a bit of a math lesson combined. As you might realize, the inherent problem with computers and math isn’t that they aren’t good at it. Floating point numbers have a finite precision and this leads to problems, especially when you do operations that combine large and small numbers together.
Indeed, any floating point representation has a bigger infinity of numbers that it can’t represent than those that it can. But the same is true of a calculator. Think about how many digits you are willing to type in, and how many digits you want out. All you want is for each of them to be correct, and that’s a much smaller set of numbers.
Google’s developer, [Hans-J. Boehm] tackled this problem by turning to recursive real arithmetic (RRA). Here, each math function is told how accurate it needs to be, and a set of rules determines the highest required accuracy.
But every solution brings a problem. With RRA, there is no way to tell very small numbers from zero. So computing “1-1” might give you “0.000000000”, which is correct but upsetting because of all the excess precision. You could try to test if “0.00000000” was equal to “0”, and simplify the output. But testing for equality of two numbers in RRA is not guaranteed to terminate: you can tell if two numbers are unequal by going to more and more precision until you find a difference, but if the numbers happen to be equal, this procedure never ends.
The key realization for [Boehm] and his collaborators was that you could use RRA only for cases where you deal with inexact numbers. Most of the time, the Android calculator deals with rationals. However, when an operation produces a potentially irrational result, it switches to RRA for the approximation, which works because no finite representation ever gets it exactly right. The result is a system that doesn’t show excess precision, but correctly displays all of the digits that it does show.
We really like [Chad’s] step-by-step explanation. If you would rather dive into the math, you can read [Boehm’s] paper on the topic. If you ever wonder how many computer systems handle odd functions like sine and cosine, read about CORDIC. Or, avoid all of this and stick to your slide rule.