The Impossible Calculator

Google Android’s calculator is (probably) the most widely used calculator in the world. It’s also the most advanced.

By Andre Popovitch

Consider this straightforward calculation: (10¹⁰⁰) + 1 - (10¹⁰⁰)

The answer, of course, is 1. But if you were to input it right now on your iPhone calculator, the answer you would get is 0.

Android, however, gets it right.

Why is there a difference? The answer to that question begins with the story of how one of the world’s top computer scientists ended up working on a humble calculator app.

Basic number representation

The conventional way to represent the number two is with an Arabic numeral: 2. But usage depends on context. It may be more appropriate to use, for example, Roman numerals (e.g. World War II) or a fraction (e.g. 6/3).

Different representations have different advantages. Say you’re counting the number of people who enter a building and you don’t have a clicker. You may want to use tally marks because a number written in the form of tally marks is easy to increment. But if you want to multiply two numbers, using Arabic numerals is much more convenient.

A computer must also choose how to represent numbers in order to work with them. There are various ways that computers can represent numbers, each, again, with benefits and drawbacks. The most common method is what’s called “floating-point” representation, which breaks every number into three separate parts: the sign (negative or positive), the exponent, and the mantissa, which is the fractional part of the number that contains the significant digits. For our equation, that’s where the trouble starts.

Floating-point numbers take up a fixed amount of space in a computer’s memory, most often 64 bits. This is convenient for managing memory and achieving consistent performance. It means that there are 2⁶⁴ numbers that can be expressed — one for each possible combination of bits — which works out to about 18 quintillion different numbers. This is more than sufficient for everyday applications.

But it also means that if a computer using floating-point numbers needs to express a number that is not one of these 18 quintillion possibilities, it has no choice but to round it to the nearest number it can express.

18 quintillion numbers is a lot, but it doesn’t go as far as you’d think. 10¹⁰⁰— otherwise known as a googol — is, in fact, much larger than 18 quintillion. What happens when floating-point numbers get that large is that the space between representable numbers becomes enormous. The only solution is to round. Near a googol, the "gap" between representable numbers might be billions or trillions. Adding 1 falls within this gap and gets rounded to the nearest representable value — which would just be back to the googol itself. So to a floating-point calculator, 1 + a googol gets rounded back to a googol. Which is why your iPhone calculator thinks (10¹⁰⁰) + 1 - (10¹⁰⁰ = 0.

Numbers like 10¹⁰⁰ generally show up only in math problems. But numbers large enough to pose a problem for floating-point numbers do come up sometimes. For example, some estimate that humanity has produced over 13,000,000,000,000,000,000,000 transistors. It happens that 13,000,000,000,000,000,000,000 can be represented exactly by a 64-bit floating-point number, but 13,000,000,000,000,000,000,000 + 1 cannot. The same happens when you add 2, 2,000, or 20,000. You need to add 2,000,000 before you get to the next number that floating-point can represent. A company trying to keep precise track of transistor production would be wise not to use 64-bit floating-point numbers.

And the issue is not limited to very large numbers. Small whole numbers are fine, but once you get into fractions, you run into issues. The only fractions that can be represented precisely by floating-point numbers are those whose denominator is a power of 2, called “dyadic fractions.”

Non-dyadic fractions also have to be rounded to the nearest available floating-point number. This is why when you evaluate 0.1 + 0.2 — both non-dyadic fractions — with Python or JavaScript, the answer returned is 0.30000000000000004.

Most calculators try to solve this issue by rounding the answer to a smaller number of decimal digits, and will display the answer as “0.3.” But the number in the calculator memory is actually 0.30000000000000004. And if you try to calculate 0.1 + 0.2 - 0.3 — which is 0 — a calculator built on floating-point numbers ends up with a number a tiny bit larger. This explains that reason that when you evaluate 1/(0.1 + 0.2 - 0.3) in Python, the answer you get is 18,014,398,509,481,984 (which it most certainly is not).

These limitations are no accident. Floating-point numbers were designed with speed and performance in mind. Imagine a video game rendering a scene with millions of triangles. You want to be able to store the positions of those triangles as compactly as possible and work with them as quickly as possible, even if that comes with some loss in precision. Floating-point numbers are perfect for this, and they’re generally useful enough that most programmers never need to reach for anything else. But when absolute precision is necessary, floating-point numbers are not an option.

If we’re being honest, these failures are visible only in contrived situations. No one asked their calculator to have absolute precision for the 10-100 percent of edge cases. Floating-point inaccuracies are not going to make a difference when you’re doing your taxes or calculating a tip. But there’s something unsatisfying about a calculator that doesn’t always give the exact right answer for any calculation.

So Google turned to Dr. Hans Boehm, who in turn had to draw from much deeper in pure mathematics than most would have suspected. Boehm is a computer science heavyweight. Before joining Google, he led research efforts that underpin much of today's parallel computing infrastructure.¹ For Boehm to pivot to working on a calculator app is a bit like a NASA engineer pivoting to paper airplanes. I asked him why.

It turns out that for some years, Boehm had been working on problems within a subfield of mathematics known as “constructive mathematics” and, within that, the even more obscure application of something called recursive real arithmetic (RRA). And in doing so, he’d had a dramatic realization: The way that many calculators were doing mathematical operations was completely wrong.

Dilbert B. Vilarino

Types of numbers

The essential concepts behind RRA are simple, but before I can explain them, I’ll need to explain the basic types of numbers.

Integers include 0, positive counting numbers (1, 2, 3...), and their negative counterparts (-1, -2, -3...). Any number without a fractional or decimal component is an integer.

As you can imagine, integers are used very often in programming. But there’s a problem when it comes to representing them. All computers have limited memory. Since there is an infinite number of integers, computers can’t have a separate representation for each one.

The way that programmers usually handle this is to ignore it entirely. Most often, they decide to dedicate 32 or 64 bits of memory to storing the integer and hope that more memory is not needed. If the number grows outside of that range, then their program will usually do something wrong. For example, the original Pac-Man used only 8 bits to store the game level. The largest integer expressible in 8 bits is 255. Once you beat Pac-Man’s level 255, the code breaks, and the right half of the screen becomes a mess of numbers and letters.

We’ve come a long way since Pac-Man. Actually encountering a bug caused by exceeding the maximum bounds of an integer is now rare. However, if a programmer wants to be extra cautious, they tell the computer, “Store this integer using as much memory as needed” — which, with modern computers, is almost always enough.

That deals with integers. But a calculator that can work only with integers is not able to perform many interesting calculations. That’s why another insight is needed.

Rational numbers can be expressed as a fraction or ratio of two integers (as long as the denominator is not 0). All integers can be expressed as a fraction (3 is the same as 3/1). Since rational numbers are just one integer divided by another, we can straightforwardly represent them as two integers: a numerator and denominator.

This allows our calculator to give exact answers for operations like 21 ÷ 6, which would be stored precisely as 7/2.

This is the point at which most programmers implementing a calculator would have patted themselves on the back for a job well done. A calculator built on this representation, rather than on normal floating-point numbers, can handle (10¹⁰⁰) + 1 - (10¹⁰⁰) and 0.1 + 0.2 exactly and without any problem. The average calculator user would never notice an issue.

But Boehm wanted to build a calculator that could be more precise. Numbers such as π and √2 are not fractions and cannot be expressed as fractions. You could approximate π using a fraction, as many do with 22/7, but that is not exactly π. So if the calculator were built on fractions, operations that involve these numbers would be inexact, possibly leading to subtly incorrect answers.

So √2 is not a fraction. It is, however, easy to describe: It’s the only positive number that, when squared, equals 2. A programmer could just define it that way: “I’m talking about x, where x² = 2 and x is positive.” x² = 2 is a special type of equation known as a polynomial — an equation that uses only addition, subtraction, and multiplication, and where the variables are raised only to whole number powers (0, 1, 2, 3, etc.).

It is possible to represent numbers like √2 as the polynomial equation they satisfy. Each number that makes up the equation can be expressed as a rational number, but the solutions don’t have to be. This larger class of numbers is called “algebraic numbers.”

Though this approach has the benefit of precision, it also has a couple of drawbacks. First, operations like addition and multiplication become more complex, as they require the computation of new polynomials. This makes them much more computationally expensive than floating-point or rational numbers.

Second, π is not an algebraic number, nor are many other numbers that you might want to express on a calculator. This puts π in an even higher class of numbers, known as the “transcendental numbers.” And since transcendental numbers are not algebraic, algebraic arithmetic is of no use with them.

Computable reals

This is where Boehm’s expertise in RRA came in. In RRA, numbers are represented as increasingly precise approximations. If you ask for π with a precision of 0.01, it returns 3.14. More precision, more digits.

RRA stems from a concept from constructive mathematics called “computable reals.” Computers can’t tell you the exact decimal value of π, since it has an infinite number of digits that never repeat — the computational version of eternal return. But they can easily tell you as many digits as you need. A number that can be computed to whatever precision you need is called a “computable real” number.

The brilliance of this approach is that it recursively determines how much precision is needed for each intermediate calculation, which ensures that the final result returns a number no more and no less precise than required.

Take π × 2 as an example. You first tell RRA what precision you want. It would be reasonable to choose a precision equal to the number of digits displayed on the calculator screen — let’s say 10 digits.

RRA then figures out that π must be computed to 11 decimal places to give an answer accurate to 10 decimal places. (It does this because multiplying an approximation of a number by 2 will double the error of that approximation. Computing one extra decimal place will make the approximation 10 times more accurate, so when it’s multiplied by 2, the answer will be within the desired precision of 10 decimal places.)

Finally, it actually does the work: It computes π to 11 digits and multiplies it by 2 to get the final answer.

By this means, Boehm and his team were able to guarantee that all the digits displayed on the screen were correct. This elegantly sidesteps all the problems with floating-point arithmetic, rational arithmetic, and algebraic arithmetic. They gained the ability to do any computation you would want to do on a calculator and to make sure all the numbers displayed on the screen are accurate.

But such power does not come without cost. RRA introduces yet another problem, and this one required even more sophistication to solve.

The truncation dilemma

1-1 is 0. It’s also, technically, 0.0000000000000, but this isn’t what calculator users expect, or want, to see displayed in any calculation. The problem is that a calculator using RRA makes this impossible. With pure RRA, it’s impossible to determine if a number is exactly 0 or just very close to 0. RRA is great if you want to compute an answer to any particular precision, but it’s fundamentally unsuited to give you an answer and tell you that it’s the exact answer.

And this isn’t just some arbitrary limit of RRA. It’s because of a much deeper mathematical truth: In general, there is no way to tell whether two computable reals are equal, or even whether a computable real is equal to 0. If you compute a number only to 10 digits of precision, you cannot tell if the actual value is exactly 0 or something like 0.000000000001. This is where Boehm and his team needed to get creative.

One approach would have been to implement something called a “computer algebra system.” These can perform calculations entirely symbolically, the same way you would perform them using a pencil and paper. But this would not have been a feasible approach for Boehm and his team. Elyot Grant, an engineer who has worked on computer algebra systems, described this approach as “incredibly difficult” and “insane overkill for a calculator.”

Take the (10¹⁰⁰) + 1 - (10¹⁰⁰ example. Anyone can see that you don’t actually have to calculate 10¹⁰⁰ to find the answer, because whatever it is, it will be cancelled out by the subtraction at the end. To program this specific logic into a calculator would be easy enough, but the number of other cases that would need to be handled as well is far too large. Computer algebra systems typically work by having a very large number of manually written rules, which are then thrown at the problem until some combination of them finally works — not an elegant solution, and hopefully not required just for the basic operation of a calculator.

“Not all the math was clear to me when we started,” Boehm told me. It wasn’t until he came across other work, in a different area of mathematics, that Boehm and his colleagues realized they could combine the strengths of different number systems.

Their insight was to represent numbers as a rational multiplied by a real, where the real part could be either an RRA real or a symbolic representation (like π). This allowed them to:

1. Use exact rational arithmetic whenever possible.

2. Use symbolic representations for common irrational numbers, like π.

3. Fall back on RRA only when absolutely necessary.

For example, with this system, the calculator could recognize that sin(π) is exactly 0. RRA on its own would be able to establish only that it was approximately 0. Boehm’s team did this by adding a rule that “applying sin to π is always 0,” but they fortunately needed only a small number of such rules to have great results.

There are some edge cases where this system fails to realize that the answer is exactly 0, requiring the calculator to display “0.0000000…” unnecessarily. But their approach easily handles all the common situations in which a phone calculator is likely to be used, such as when a student is doing their math homework.

In the end, what Boehm came up with struck a remarkable balance: the answers shown are always correct and are almost always shown the same way you would write it on paper — without being too complicated to implement.

Calculating googols the world over

Android is the world’s most popular mobile operating system, with around three times as many Android users as iOS users. Not every phone ships with Boehm’s calculator installed, but it’s probable the Android app is the most widely used calculator in the world. ² At nearly 4 billion Android users, this is a level of distribution unimaginable for companies that make physical calculators, like Texas Instruments or Casio. It makes sense that Google would pursue a very high standard of quality for their calculator.³

What was remarkable to me was that pursuing their standards of quality led them to constructive real mathematics. These areas of math were once confined exclusively to academic papers. They’re now running the calculator app in millions of pockets around the world. As Boehm told me, many mathematicians “were surprised at the fact that some of these old theorems actually have practical applications.”

Nearly everything around us is a culmination of centuries of hard-won knowledge and experience. The result is that everyday items do exactly what we need them to, and do it so well we barely think about them. It’s not likely that the average calculator user would ever notice what Boehm’s team built. The amount of people to whom the edge cases genuinely matter is — ironically — difficult to calculate. But with more than a billion downloads, the answer, whatever it might be exactly, is undoubtedly a real number.

1. Specifically, he led the effort to define C++ atomic variable semantics and made fundamental contributions to garbage collection and concurrency in programming languages.

2. But Android phone manufacturers are able to customize what apps come with their phones to some extent, so there are many Android phones that do not ship with the calculator app Boehm worked on.

3. Which is not to say that Texas Instruments, Casio, and HP haven’t also thought about these problems. They also seem to implement something more sophisticated than standard floating-point arithmetic on some calculators. This varies by model — my Casio still returns 0 for (10¹⁰⁰) + 1 - (10¹⁰⁰).