Hans Boehm | 50f1bac | 2015-08-11 19:23:02 -0700 | [diff] [blame] | 1 | <!doctype html> |
| 2 | <html> |
| 3 | <head> |
| 4 | <title>Calculator Arithmetic Overview</title> |
| 5 | <meta charset="UTF-8"> |
| 6 | <style> |
| 7 | #toc { |
| 8 | width:300px; |
| 9 | border:1px solid #ccc; |
| 10 | background-color:#efefef; |
| 11 | float:right; |
| 12 | } |
| 13 | .display { |
| 14 | color:#666666; |
| 15 | background-color:#f3f3f3; |
| 16 | } |
| 17 | </style> |
| 18 | </head> |
| 19 | <body onload="init();"> |
| 20 | <div id="toc"></div> |
| 21 | <h1>Arithmetic in the Android M Calculator</h1> |
| 22 | <p>Most conventional calculators, both the specialized hardware and software varieties, represent |
| 23 | numbers using fairly conventional machine floating point arithmetic. Each number is stored as an |
| 24 | exponent, identifying the position of the decimal point, together with the first 10 to 20 |
| 25 | significant digits of the number. For example, 1/300 might be stored as |
| 26 | 0.333333333333x10<sup>-2</sup>, i.e. as an exponent of -2, together with the 12 most significant |
| 27 | digits. This is similar, and sometimes identical to, computer arithmetic used to solve large |
| 28 | scale scientific problems.</p> <p>This kind of arithmetic works well most of the time, but can |
| 29 | sometimes produce completely incorrect results. For example, the trigonometric tangent (tan) and |
| 30 | arctangent (tan<sup>-1</sup>) functions are defined so that tan(tan<sup>-1</sup>(<i>x</i>)) should |
| 31 | always be <i>x</i>. But on most calculators we have tried, tan(tan<sup>-1</sup>(10<sup>20</sup>)) |
| 32 | is off by at least a factor of 1000. A value around 10<sup>16</sup> or 10<sup>17</sup> is quite |
| 33 | popular, which unfortunately doesn't make it correct. The underlying problem is that |
| 34 | tan<sup>-1</sup>(10<sup>17</sup>) and tan<sup>-1</sup>(10<sup>20</sup>) are so close that |
| 35 | conventional representations don't distinguish them. (They're both 89.9999… degrees with at least |
| 36 | fifteen 9s beyond the decimal point.) But the tiny difference between them results in a huge |
| 37 | difference when the tangent function is applied to the result.</p> |
| 38 | |
| 39 | <p>Similarly, it may be puzzling to a high school student that while the textbook claims that for |
| 40 | any <i>x</i>, sin(<i>x</i>) + sin(<i>x</i>+π) = 0, their calculator says that sin(10<sup>15</sup>) |
| 41 | + sin(10<sup>15</sup>+π) = <span class="display">-0.00839670971</span>. (Thanks to floating point |
| 42 | standardization, multiple on-line calculators agree on that entirely bogus value!)</p> |
| 43 | |
| 44 | <p>We know that the instantaneous rate of change of a function f, its derivative, can be |
| 45 | approximated at a point <i>x</i> by computing (<i>f</i>(<i>x</i> + <i>h</i>) - <i>f</i>(<i>x</i>)) |
| 46 | / <i>h</i>, for very small <i>h</i>. Yet, if you try this in a conventional calculator with |
| 47 | <i>h</i> = 10<sup>-20</sup> or smaller, you are unlikely to get a useful answer.</p> |
| 48 | |
| 49 | <p>In general these problems occur when computations amplify tiny errors, a problem referred to as |
| 50 | numerical instability. This doesn't happen very often, but as in the above examples, it may |
| 51 | require some insight to understand when it can and can't happen.</p> |
| 52 | |
| 53 | <p>In large scale scientific computations, hardware floating point computations are essential |
| 54 | since they are the only reasonable way modern computer hardware can produce answers with |
| 55 | sufficient speed. Experts must be careful to structure computations to avoid such problems. But |
| 56 | for "computing in the small" problems, like those solved on desk calculators, we can do much |
| 57 | better!</p> |
| 58 | |
| 59 | <h2>Producing accurate answers</h2> |
| 60 | <p>The Android M Calculator uses a different kind of computer arithmetic. Rather than computing a |
| 61 | fixed number of digits for each intermediate result, the computation is much more goal directed. |
| 62 | The user would like to see only correct digits on the display, which we take to mean that the |
| 63 | displayed answer should always be off by less than one in the last displayed digit. The |
| 64 | computation is thus performed to whatever precision is required to achieve that.</p> |
| 65 | |
| 66 | <p>Let's say we want to compute π+⅓, and the calculator display has 10 digits. We'd compute both π |
| 67 | and ⅓ to 11 digits each, add them, and round the result to 10 digits. Since π and ⅓ were accurate |
| 68 | to within 1 in the 11<sup>th</sup> digit, and rounding adds an error of at most 5 in the |
| 69 | 11<sup>th</sup> digit, the result is guaranteed accurate to less than 1 in the 10<sup>th</sup> |
| 70 | digit, which was our goal.</p> |
| 71 | |
| 72 | <p>This is of course an oversimplification of the real implementation. Operations other than |
| 73 | addition do get appreciably more complicated. Multiplication, for example, requires that we |
| 74 | approximate one argument in order to determine how much precision we need for the other argument. |
| 75 | The tangent function requires very high precision for arguments near 90 degrees to produce |
| 76 | meaningful answers. And so on. And we really use binary rather than decimal arithmetic. |
| 77 | Nonetheless the above addition method is a good illustration of the approach.</p> |
| 78 | |
| 79 | <p>Since we have to be able to produce answers to arbitrary precision, we can also let the user |
| 80 | specify how much precision she wants, and use that as our goal. In the Android M Calculator, the |
| 81 | user specifies the requested precision by scrolling the result. As the result is being scrolled, |
| 82 | the calculator reevaluates it to the newly requested precision. In some cases, the algorithm for |
| 83 | computing the new higher precision result takes advantage of the old, less accurate result. In |
| 84 | other cases, it basically starts from scratch. Fortunately modern devices and the Android runtime |
| 85 | are fast enough that the recomputation delay rarely becomes visible.</p> |
| 86 | |
| 87 | <h2>Design Decisions and challenges</h2> |
| 88 | <p>This form of evaluate-on-demand arithmetic has occasionally been used before, and we use a |
| 89 | refinement of a previously developed open source package in our implementation. However, the |
| 90 | scrolling interface, together with the practicailities of a usable general purpose calculator, |
| 91 | presented some new challenges. These drove a number of not-always-obvious design decisions which |
| 92 | briefly describe here.</p> |
| 93 | |
| 94 | <h3>Indicating position</h3> |
| 95 | <p>We would like the user to be able to see at a glance which part of the result is currently |
| 96 | being displayed.</p> |
| 97 | |
| 98 | <p>Conventional calculators solve the vaguely similar problem of displaying very large or very |
| 99 | small numbers by using scientific notation: They display an exponent in addition to the most |
| 100 | significant digits, analogously to the internal representation they use. We solve that problem in |
| 101 | exactly the same way, in spite of our different internal representation. If the user enters |
| 102 | "1÷3⨉10^20", computing ⅓ times 10 to the 20th power, the result may be displayed as <span |
| 103 | class="display">3.3333333333E19</span>, indicating that the result is approximately 3.3333333333 |
| 104 | times 10<sup>19</sup>. In this version of scientific notation, the decimal point is always |
| 105 | displayed immediately to the right of the most significant digit, and the exponent indicates where |
| 106 | it really belongs.</p> |
| 107 | |
| 108 | <p>Once the decimal point is scrolled off the display, this style of scientific notation is not |
| 109 | helpful; it essentially tells us where the decimal point is relative to the most significant |
| 110 | digit, but the most significant digit is no longer visible. We address this by switching to a |
| 111 | different variant of scientific notation, in which we interpret the displayed digits as a whole |
| 112 | number, with an implied decimal point on the right. Instead of displaying <span |
| 113 | class="display">3.3333333333E19</span>, we hypothetically could display <span |
| 114 | class="display">33333333333E9</span> or 33333333333 times 10<sup>9</sup>. In fact, we use this |
| 115 | format only when the normal scientific notation decimal point would not be visible. If we had |
| 116 | scrolled the above result 2 digits to the left, we would in fact be seeing <span |
| 117 | ass="display">...33333333333E7</span>. This tells us that the displayed result is very close to a |
| 118 | whole number ending in 33333333333 times 10<sup>7</sup>. Effectively the <span |
| 119 | class="display">E7</span> is telling us that the last displayed digit corresponds to the ten |
| 120 | millions position. In this form, the exponent does tell us the current position in the result. |
| 121 | The two forms are easily distinguishable by the presence or absence of a decimal point, and the |
| 122 | ellipsis character at the beginning.</p> |
| 123 | |
| 124 | <h3>Rounding vs. scrolling</h3> |
| 125 | <p>Normally we expect calculators to try to round to the nearest displayable result. If the |
| 126 | actual computed result were 0.66666666666667, and we could only display 10 digits, we would expect |
| 127 | a result display of, for example <span class="display">0.666666667</span>, rather than <span |
| 128 | class="display">0.666666666</span>. For us, this would have the disadvantage that when we |
| 129 | scrolled the result left to see more digits, the "7" on the right would change to a "6". That |
| 130 | would be mildly unfortunate. It would be somewhat worse that if the actual result were exactly |
| 131 | 0.99999999999, and we could only display 10 characters at a time, we would see an initial display |
| 132 | of <span class="display">1.00000000</span>. As we scroll to see more digits, we would |
| 133 | successively see <span class="display">...000000E-6</span>, then <span |
| 134 | class="display">...000000E-7</span>, and so on until we get to <span |
| 135 | class="display">...00000E-10</span>, but then suddenly <span class="display">...99999E-11</span>. |
| 136 | If we scroll back, the screen would again show zeroes. We decided this would be excessively |
| 137 | confusing, and thus do not round.</p> |
| 138 | |
| 139 | <p>It is still possible for previously displayed digits to change as we're scrolling. But we |
| 140 | always compute a number of digits more than we actually need, so this is exceedingly unlikely.</p> |
| 141 | |
| 142 | <p>Since our goal is an error of strictly less than one in the last displayed digit, we will |
| 143 | never, for example, display an answer of exactly 2 as <span class="display">1.9999999999</span>. |
| 144 | That would involve an error of exactly one in the last place, which is too much for us.</p> <p>It |
| 145 | turns out that there is exactly one case in which the display switches between 9s and 0s: A long |
| 146 | but finite sequence of 9s (more than 20) in the true result can initially be displayed as a larger |
| 147 | number ending in 0s. As we scroll, the 0s turn into 9s. When we immediately scroll back, the |
| 148 | number remains displayed as 9s, since the calculator caches the best known result (though not |
| 149 | currently across restarts or screen rotations).</p> |
| 150 | |
| 151 | <p>We prevent 9s from turning into 0s during scrolling. If we generate a result ending in 9s, our |
| 152 | error bound implies that the true result is strictly less (in absolute value) than the value |
| 153 | (ending in 0s) we would get by incrementing the last displayed digit. Thus we can never be forced |
| 154 | back to generating zeros and will always continue to generate 9s.</p> |
| 155 | |
| 156 | <h3>Coping with mathematical limits</h3> |
| 157 | <p>Internally the calculator essentially represents a number as a program for computing however |
| 158 | many digits we happen to need. This representation has many nice properties, like never resulting |
| 159 | in the display of incorrect results. It has one inherent weakness: We provably cannot compute |
| 160 | precisely whether two numbers are equal. We can compute more and more digits of both numbers, and |
| 161 | if they ever differ by more than one in the last computed digit, we know they are <i>not</i> |
| 162 | equal. But if the two numbers were in fact the same, this process will go on forever.</p> |
| 163 | |
| 164 | <p>This is still better than machine floating point arithmetic, though machine floating point |
| 165 | better obscures the problem. With machine floating point arithmetic, two computations that should |
| 166 | mathematically have given the same answer, may give us substantially different answers, and two |
| 167 | computations that should have given us different answers may easily produce the same one. We |
| 168 | can indeed determine whether the floating representations are equal, but this tells us little |
| 169 | about equality of the true mathematical answers.</p> |
| 170 | |
| 171 | <p>The undecidability of equality creates some interesting issues. If we divide a number by |
| 172 | <i>x</i>, the calculator will compute more and more digits of <i>x</i> until it finds some nonzero |
| 173 | ones. If <i>x</i> was in fact exactly zero, this process will continue forever.</p> <p>We deal |
| 174 | with this problem using two complementary techniques:</p> |
| 175 | |
| 176 | <ol> |
| 177 | <li>We always run numeric computations in the background, where they won't interfere with user |
| 178 | interactions, just in case they take a long time. If they do take a really long time, we time |
| 179 | them out and inform the user that the computation has been aborted. This is unlikely to happen by |
| 180 | accident, unless the user entered an ill-defined mathematical expression, like a division by |
| 181 | zero.</li> |
| 182 | <li>As we will see below, in many cases we use an additional number representation that does allow |
| 183 | us to determine that a number is exactly zero. Although this easily handles most cases, it is not |
| 184 | foolproof. If the user enters "1÷0" we immediately detect the division by zero. If the user |
| 185 | enters "1÷(π−π)" we time out. (We might choose to explicitly recognize such simple cases in the |
| 186 | future. But this would always remain a heuristic.)</li> |
| 187 | </ol> |
| 188 | |
| 189 | <h3>Zeros further than the eye can see</h3> |
| 190 | <p>Prototypes of the M calculator, like mathematicians, treated all real numbers as infinite |
| 191 | objects, with infinitely many digits to scroll through. If the actual computation happened to be |
| 192 | 2−1, the result was initially displayed as <span class="display">1.00000000</span>, and the user |
| 193 | could keep scrolling through as many thousands of zeroes to the right of that as he desired. |
| 194 | Although mathematically sound, this proved unpopular for several good reasons, the first one |
| 195 | probably more serious than the others:</p> |
| 196 | |
| 197 | <ol> |
| 198 | <li>If we computed $1.23 + $7.89, the result would show up as <span |
| 199 | class="display">9.1200000000</span> or the like, which is unexpected and harder to read quickly |
| 200 | than <span class="display">9.12</span>.</li> |
| 201 | <li>Many users consider the result of 2-1 to be a finite number, and find it confusing to be able |
| 202 | to scroll through lots of zeros on the right.</li> |
| 203 | <li>Since the calculator couldn't ever tell that a number wasn't going to be scrolled, it couldn't |
| 204 | treat any result as short enough to allow the use of a larger font.</li> |
| 205 | </ol> |
| 206 | |
| 207 | <p>As a result, the calculator now also tries to compute the result as an exact fraction whenever |
| 208 | that is easily possible. It is then easy to tell from the fraction whether a number has a finite |
| 209 | decimal expansion. If it does, we prevent scrolling past that point, and may use the fact that |
| 210 | the result has a short representation to increase the font size. Results displayed in a larger |
| 211 | font are not scrollable. We no longer display any zeros for non-zero results unless there is |
| 212 | either a nonzero or a displayed decimal point to the right. The fact that a result is not |
| 213 | scrollable tells the user that the result, as displayed, is exact. This is fallible in the other |
| 214 | direction. For example, we do not compute a rational representation for π−π, and hence it is |
| 215 | still possible to scroll through as many zeros of that result as you like.</p> |
| 216 | |
| 217 | <p>This underlying fractional representation of the result is also used to detect, for example, |
| 218 | division by zero without a timeout.</p> |
| 219 | |
| 220 | <p>Since we calculate the fractional result when we can in any case, it is also now available to |
| 221 | the user through the overflow menu.</p> |
| 222 | |
| 223 | <h2>More details</h2> |
| 224 | <p>The underlying evaluate-on-demand arithmetic package is described in H. Boehm, "The |
| 225 | Constructive Reals as a Java Library'', Special issue on practical development of exact real |
| 226 | number computation, <i>Journal of Logic and Algebraic Programming 64</i>, 1, July 2005, pp. 3-11. |
| 227 | (Also at <a href="http://www.hpl.hp.com/techreports/2004/HPL-2004-70.html">http://www.hpl.hp.com/techreports/2004/HPL-2004-70.html</a>)</p> |
| 228 | |
| 229 | <p>Our version has been slightly refined. Notably it calculates inverse trigonometric functions |
| 230 | directly instead of using a generic "inverse" function. This is less elegant, but significantly |
| 231 | improves performance.</p> |
| 232 | |
| 233 | </body> |
| 234 | </html> |
| 235 | <script type="text/javascript"> |
| 236 | function generateTOC (rootNode, startLevel) { |
| 237 | var lastLevel = 0; |
| 238 | startLevel = startLevel || 2; |
| 239 | var html = "<ul>"; |
| 240 | |
| 241 | for (var i = 0; i < rootNode.childNodes.length; ++i) { |
| 242 | var node = rootNode.childNodes[i]; |
| 243 | if (!node.tagName || !/H[1-6]/.test(node.tagName)) { |
| 244 | continue; |
| 245 | } |
| 246 | var level = +node.tagName.substr(1); |
| 247 | if (level < startLevel) { continue; } |
| 248 | var name = node.innerText; |
| 249 | if (node.children.length) { name = node.childNodes[0].innerText; } |
| 250 | if (!name) { continue; } |
| 251 | var hashable = name.replace(/[.\s\']/g, "-"); |
| 252 | node.id = hashable; |
| 253 | if (level > lastLevel) { |
| 254 | html += ""; |
| 255 | } else if (level < lastLevel) { |
| 256 | html += (new Array(lastLevel - level + 2)).join("</ul></li>"); |
| 257 | } else { |
| 258 | html += "</ul></li>"; |
| 259 | } |
| 260 | html += "<li><a class='lvl"+level+"' href='#" + hashable + "'>" + name + "</a><ul>"; |
| 261 | lastLevel = level; |
| 262 | } |
| 263 | |
| 264 | html += "</ul>"; |
| 265 | return html; |
| 266 | } |
| 267 | |
| 268 | function init() { |
| 269 | document.getElementById("toc").innerHTML = generateTOC(document.body); |
| 270 | } |
| 271 | </script> |