## "A calculator app? Anyone could make that." (this was originally a [tweet thread](https://x.com/ChadNauseam/status/1890889465322786878 "https://x.com/ChadNauseam/status/1890889465322786878")) Not true. A calculator should show you the result of the mathematical expression you entered. That's much, much harder than it sounds. What I'm about to tell you is the greatest calculator app development story ever told. ![[Pasted image 20250215162526.png]] --- That picture above is from iOS calculator. Notice anything? It's wrong. (10^100) + 1 − (10^100) is 1, not 0. Android gets it right. And the story for how is absolutely insane. ![[Pasted image 20250215162551.png]] --- Google hired Hans-J. Boehm, of the "Boehm garbage collector" fame. They needed an elite coder to fix garbage collection and concurrent programming. He led the effort to define C++ shared variable semantics. But then they gave him an impossible task: write a calculator app. ![[Pasted image 20250215162605.png]] ![[Pasted image 20250215162612.png]] --- Even for him, this must have been a challenge. The purpose of a calculator app is to give you correct answers. Floating point numbers are imprecise - they cannot represent 0.3 or 10^100. This means a calculator built on floating point numbers is like a house built on sand. ![[Pasted image 20250215162627.png]] --- It bears repeating. To give correct answers to mathematical expressions, a calculator must represent numbers. And almost all numbers cannot be expressed in IEEE floating points. Even simple operations with floating point numbers requires careful thought for an accurate answer ![[Pasted image 20250215162639.png]] --- Some problems can be avoided if you use bignums. Most numeric types are always 2 or 4 bytes. Not so for bignums. These are integers without bounds. They grow in memory as needed. This solves the (10^100) + 1 - (10^100) example. But bignums are integers. How about fractions? ![[Pasted image 20250215162654.png]] --- Fractions can be solved easily. Just use bignums for the numerator and denominator. The implementation of arithmetic ops on such a type are trivial, and will always give exact answers. This is where many would have declared victory. But Boehm wasn't satisfied. Not even close. ![[Pasted image 20250215162716.png]] --- Math goes much deeper than fractions. What about π or √2? A calculator that is based on arbitrary-precision fractions still can't tell you the circumference of a circle, since π is not expressible as a fraction. If your calculator can't handle 9th grade math, what good is it? ![[Pasted image 20250215162736.png]] --- Algebraic arithmetic would get him closer. Forget about representing numbers as numerators and denominators. You can represent them as the polynomial equation they satisfy. For √2, it would be x² - 2 = 0. (Plus you'd store that you want the positive root.) ![[Pasted image 20250215162748.png]] --- Now math ops get a little trickier to implement: - To add, you create a new polynomial that has their sum as a root - To multiply, you use polynomial composition and resultants Guess what? Still not good enough for Boehm. This only works for algebraic numbers. Doesn't get us π --- So Boehm had no choice but to go even deeper. It was time to get serious. We started off with integers (bignum), went to rational numbers, then algebraic numbers. What's next? Constructive real numbers. ![[Pasted image 20250215162814.png]] --- So Boehm began to consider "recursive real arithmetic" (RRA). Given an expression and how precise you want the answer, RRA gives you an answer at least that precise. Check out the cover of this classic textbook. See how the rulers get smaller and smaller? ![[Pasted image 20250215162826.png]] --- Constructive real numbers are those numbers that you can compute more and more accurately. You can't ever tell me all the decimals of π. But if I ask for a rational number within 0.01 of π, you can tell me 3.14. π is within 0.01 of 3.14, so that's a valid answer. ![[Pasted image 20250215162838.png]] --- Now let's say I ask for a number within 0.01 of 2π. You know how to generate digits of π. (3.14159...) You can then take some of them and multiply that by 2. But how many digits do you need to take, to make sure your answer is within 0.01 of 2π? Multiplying a number by 2 doubles the error. I asked for 2π to within 0.01, so you need an approximation of π that's within 0.005. Let's say you come up with 3.141, which is indeed less than 0.005 away from π. Multiply that by 2 and you're done! ![[Pasted image 20250215162901.png]] --- RRA works this way. Every number in RRA is represented as a function that takes a rational and returns a rational. The rational it takes is the requested tolerance. The rational it returns is guaranteed to be within that tolerance of the real number it represents ![[Pasted image 20250215162919.png]] --- This means RRA is simple to use. You say how precise the answer must be, and it recursively figures out how much precision is needed in all the intermediate calculations. It can handle expressions involving π or √2 without a problem. Essential for a calculator. --- You're thinking "Surely Boehm stopped here". Just set the "output precision" to be the number of digits displayed by the calculator, right? Then all the digits displayed by the calculator would be correct. So now the calculator always shows the correct answer! Right? ![[Pasted image 20250215162945.png]] --- But not so fast. When users type "1-1", the answer is 0, so you want to show "0". But RRA will only tell you "1-1 is within a rounding error of 0.0000000000000" Showing 0.0000000000000 on the screen, when the answer is exactly 0, would be a horrible user experience. ![[Pasted image 20250215162959.png]] --- Boehm was back to the drawing board. At this point he must have been concerned. His "space efficient conservative garbage collection" was child's play compared to this. He couldn't do it alone. He recruited colleagues such as Corky Cartwright and Vernon Lee Jr to help ![[Pasted image 20250215163012.png]] --- You can check that two RRA numbers are *not* equal. You can compute them with more and more accuracy until you see where they differ. But if the numbers are equal, you'll just be computing them with more and more accuracy forever. It doesn't terminate. ![[Pasted image 20250215163028.png]] --- Remember - if the calculator showed 0 for e^(-10000), that would be wrong. It's not 0. It should say 0.00000... and let you scroll until you see where it changes But, it SHOULD show 0 when you type sin(π). sin(π) is exactly 0 RRA gives us no way to tell that sin(π) is exactly 0 --- Or you could just not give an answer at all, like the iOS calculator does lol ![[Pasted image 20250215163049.png]] --- So showing an exact answer is impossible to solve with constructive real numbers. But Boehm and co had a realization. They don't need to work with all constructive real numbers They only need to work with the numbers you can express with the operations available on a calculator --- These are: 1. The four basic arithmetic operations, and square roots. 2. The sin, cos, and tan trigonometric functions and their inverses. 3. Exponential and (natural) logarithm functions This is a much smaller set of numbers than all constructive reals. --- And in fact, someone had already researched this exact problem. Their names were Dan Richardson and John Fitch, and they solved it in 1994. ![[Pasted image 20250215163123.png]] --- Their solution is absolutely correct. Unless one of the numbers is a counterexample to Shanuel’s conjecture. But realistically, that's not going to happen. Schanuel's conjecture is one of the most important in number theory, and no one has found a counterexample yet ![[Pasted image 20250215163135.png]] --- It sounds perfect. But there's just one problem. It's too slow. 1 is not equal to 1 - e^(-e^1000). But for Richardson and Fitch's algorithm to detect that, it would require more steps than there are atoms in the universe. They needed something faster. --- Their original problem was to see if two constructive real numbers were equal. That was impossible to solve. They simplified it and got closer, by limiting how they could construct the numbers. That made the problem solvable, just slow. Could they simplify it again? --- They realized that it's not the end of the world if they show "0.000000..." in a case where the answer is exactly 0, although it's not the ideal UX. They just can't show "0" in a case where the answer is 0.0000001. Maybe a faster, conservative algorithm was possible? Then they came up with something truly brilliant. --- RRA gives you the full power of the constructive real numbers, with the drawback that getting exact answers becomes impossible. Rational arithmetic gives exact answers, but can't express π. Could their strengths be combined? ![[Pasted image 20250215163207.png]] ![[Pasted image 20250215163213.png]] --- Their realization was that, if the user just enters 6 * 9 or 8 / 3, you don't need the full power of RRA. Rational arithmetic is plenty in those cases You only need RRA when rational numbers aren't enough. Use it when numbers like π or √2 come into play, use rationals otherwise Rationals are exact, but can't represent π. --- RRA numbers can represent numbers like π, but can't be exact. Their solution: represent all numbers as a rational times a RRA number. But that's not enough. As soon as any RRA numbers are involved, the result necessarily is inexact ![[Pasted image 20250215163234.png]] --- But even for irrational numbers, RRA can sometimes be overkill. RRA represents π as a function that can return rational numbers arbitrarily close to π. (Just as all RRA numbers are represented as functions) You say "I want π within 0.001", and RRA tells you "okay, that's 3.141" ![[Pasted image 20250215163246.png]] --- Sometimes you need RRA. But in this case can also just have a special representation for π, that we special-case to use instead of its RRA function. We call this a symbolic representation, since it's like writing the symbol for π rather than an infinite sequence of digits ![[Pasted image 20250215163301.png]] --- Now we're cooking. But let's do it for more than just π Obviously we'll want a symbolic representation for the real number 1 But many irrational numbers we use are the result of applying an operation to a rational argument. We can have symbolic representations for these as well --- They chose to have symbolic representations for √arg, eᵃʳᵍ, ln(arg), log₁₀(arg), sin(πarg), tan(πarg), and more, (where `arg` is some rational number) So their final representation for numbers: A rational times a real, where a real is either an RRA real or a symbolic real ![[Pasted image 20250215163319.png]] --- Remember, the fundamental problem is that RRA numbers are impossible to check for equality. As soon as you use one, your whole calculation becomes inexact. But you do need them sometimes. So now all they had to do was try to avoid RRA reals as much as possible! --- For example, in (1 × π) + (3 × π), we're lucky enough to have symbolic representations of the real parts. π in both cases. Since the real parts are the same, we can perform the summation by adding the rational parts. If it were (1 × π) + (3 × √2), they'd just use RRA for that. --- With this representation, they're in the sweet spot: All the digits shown on the screen are always correct. And they almost never show more digits than necessary. A "computer algebra system" would have accomplished a similar goal, but been much slower and much more complicated --- A computer algebra system is so complicated that maintaining a production-quality one is something very few people are capable of. But what Boehm and co came up with is 100% correct, and gets 99% of the way to the perfect UX at only 1% of the implementation complexity. ![[Pasted image 20250215163354.png]] --- Now THAT is engineering! You should read his paper, [Towards an API for the Real Numbers](https://dl.acm.org/doi/pdf/10.1145/3385412.3386037) I hope you appreciate your android calculator a little more next time you use it! (Also I decided to try writing this thread in the style of a linkedin influencer lol, sorry about that.)