From 41718121ab7e8e50c996fac4fac5ddcf165e05b5 Mon Sep 17 00:00:00 2001 From: Hans Boehm Date: Tue, 11 Aug 2015 19:23:02 -0700 Subject: Add docs directory and contents Bug: 24811759 Add the following documentation files: arithmetic-overview.html describes the approach used to get "exact" arithmetic. implementation-overview.html outlines the major parts of the implementation. Change-Id: I3c8645aabbc5fb8aa894372a1eea0b5aad4a6473 (cherry picked from commit dd895bcaedc095c6dbb4d6df7cbc941e7a2a9d8d) --- docs/arithmetic-overview.html | 271 ++++++++++++++++++++++++++++++++++++++ docs/implementation-overview.html | 51 +++++++ 2 files changed, 322 insertions(+) create mode 100644 docs/arithmetic-overview.html create mode 100644 docs/implementation-overview.html diff --git a/docs/arithmetic-overview.html b/docs/arithmetic-overview.html new file mode 100644 index 0000000..68dd24e --- /dev/null +++ b/docs/arithmetic-overview.html @@ -0,0 +1,271 @@ + + + +Calculator Arithmetic Overview + + + + +

Arithmetic in the Android M Calculator

Most conventional calculators, both the specialized hardware and software varieties, represent +numbers using fairly conventional machine floating point arithmetic. Each number is stored as an +exponent, identifying the position of the decimal point, together with the first 10 to 20 +significant digits of the number. For example, 1/300 might be stored as +0.333333333333x10^-2, i.e. as an exponent of -2, together with the 12 most significant +digits. This is similar, and sometimes identical to, computer arithmetic used to solve large +scale scientific problems.

This kind of arithmetic works well most of the time, but can +sometimes produce completely incorrect results. For example, the trigonometric tangent (tan) and +arctangent (tan^-1) functions are defined so that tan(tan^-1(x)) should +always be x. But on most calculators we have tried, tan(tan^-1(10²⁰)) +is off by at least a factor of 1000. A value around 10¹⁶ or 10¹⁷ is quite +popular, which unfortunately doesn't make it correct. The underlying problem is that +tan^-1(10¹⁷) and tan^-1(10²⁰) are so close that +conventional representations don't distinguish them. (They're both 89.9999… degrees with at least +fifteen 9s beyond the decimal point.) But the tiny difference between them results in a huge +difference when the tangent function is applied to the result.

+ +

Similarly, it may be puzzling to a high school student that while the textbook claims that for +any x, sin(x) + sin(x+π) = 0, their calculator says that sin(10¹⁵) ++ sin(10¹⁵+π) = -0.00839670971. (Thanks to floating point +standardization, multiple on-line calculators agree on that entirely bogus value!)

+ +

We know that the instantaneous rate of change of a function f, its derivative, can be +approximated at a point x by computing (f(x + h) - f(x)) +/ h, for very small h. Yet, if you try this in a conventional calculator with +h = 10^-20 or smaller, you are unlikely to get a useful answer.

+ +

In general these problems occur when computations amplify tiny errors, a problem referred to as +numerical instability. This doesn't happen very often, but as in the above examples, it may +require some insight to understand when it can and can't happen.

+ +

In large scale scientific computations, hardware floating point computations are essential +since they are the only reasonable way modern computer hardware can produce answers with +sufficient speed. Experts must be careful to structure computations to avoid such problems. But +for "computing in the small" problems, like those solved on desk calculators, we can do much +better!

+ +

Producing accurate answers

The Android M Calculator uses a different kind of computer arithmetic. Rather than computing a +fixed number of digits for each intermediate result, the computation is much more goal directed. +The user would like to see only correct digits on the display, which we take to mean that the +displayed answer should always be off by less than one in the last displayed digit. The +computation is thus performed to whatever precision is required to achieve that.

+ +

Let's say we want to compute π+⅓, and the calculator display has 10 digits. We'd compute both π +and ⅓ to 11 digits each, add them, and round the result to 10 digits. Since π and ⅓ were accurate +to within 1 in the 11^th digit, and rounding adds an error of at most 5 in the +11^th digit, the result is guaranteed accurate to less than 1 in the 10^th +digit, which was our goal.

+ +

This is of course an oversimplification of the real implementation. Operations other than +addition do get appreciably more complicated. Multiplication, for example, requires that we +approximate one argument in order to determine how much precision we need for the other argument. +The tangent function requires very high precision for arguments near 90 degrees to produce +meaningful answers. And so on. And we really use binary rather than decimal arithmetic. +Nonetheless the above addition method is a good illustration of the approach.

+ +

Since we have to be able to produce answers to arbitrary precision, we can also let the user +specify how much precision she wants, and use that as our goal. In the Android M Calculator, the +user specifies the requested precision by scrolling the result. As the result is being scrolled, +the calculator reevaluates it to the newly requested precision. In some cases, the algorithm for +computing the new higher precision result takes advantage of the old, less accurate result. In +other cases, it basically starts from scratch. Fortunately modern devices and the Android runtime +are fast enough that the recomputation delay rarely becomes visible.

+ +

Design Decisions and challenges

This form of evaluate-on-demand arithmetic has occasionally been used before, and we use a +refinement of a previously developed open source package in our implementation. However, the +scrolling interface, together with the practicailities of a usable general purpose calculator, +presented some new challenges. These drove a number of not-always-obvious design decisions which +briefly describe here.

+ +

Indicating position

We would like the user to be able to see at a glance which part of the result is currently +being displayed.

+ +

Conventional calculators solve the vaguely similar problem of displaying very large or very +small numbers by using scientific notation: They display an exponent in addition to the most +significant digits, analogously to the internal representation they use. We solve that problem in +exactly the same way, in spite of our different internal representation. If the user enters +"1÷3⨉10^20", computing ⅓ times 10 to the 20th power, the result may be displayed as 3.3333333333E19, indicating that the result is approximately 3.3333333333 +times 10¹⁹. In this version of scientific notation, the decimal point is always +displayed immediately to the right of the most significant digit, and the exponent indicates where +it really belongs.

+ +

Once the decimal point is scrolled off the display, this style of scientific notation is not +helpful; it essentially tells us where the decimal point is relative to the most significant +digit, but the most significant digit is no longer visible. We address this by switching to a +different variant of scientific notation, in which we interpret the displayed digits as a whole +number, with an implied decimal point on the right. Instead of displaying 3.3333333333E19, we hypothetically could display 33333333333E9 or 33333333333 times 10⁹. In fact, we use this +format only when the normal scientific notation decimal point would not be visible. If we had +scrolled the above result 2 digits to the left, we would in fact be seeing ...33333333333E7. This tells us that the displayed result is very close to a +whole number ending in 33333333333 times 10⁷. Effectively the E7 is telling us that the last displayed digit corresponds to the ten +millions position. In this form, the exponent does tell us the current position in the result. +The two forms are easily distinguishable by the presence or absence of a decimal point, and the +ellipsis character at the beginning.

+ +

Rounding vs. scrolling

Normally we expect calculators to try to round to the nearest displayable result. If the +actual computed result were 0.66666666666667, and we could only display 10 digits, we would expect +a result display of, for example 0.666666667, rather than 0.666666666. For us, this would have the disadvantage that when we +scrolled the result left to see more digits, the "7" on the right would change to a "6". That +would be mildly unfortunate. It would be somewhat worse that if the actual result were exactly +0.99999999999, and we could only display 10 characters at a time, we would see an initial display +of 1.00000000. As we scroll to see more digits, we would +successively see ...000000E-6, then ...000000E-7, and so on until we get to ...00000E-10, but then suddenly ...99999E-11. +If we scroll back, the screen would again show zeroes. We decided this would be excessively +confusing, and thus do not round.

+ +

It is still possible for previously displayed digits to change as we're scrolling. But we +always compute a number of digits more than we actually need, so this is exceedingly unlikely.

+ +

Since our goal is an error of strictly less than one in the last displayed digit, we will +never, for example, display an answer of exactly 2 as 1.9999999999. +That would involve an error of exactly one in the last place, which is too much for us.

It +turns out that there is exactly one case in which the display switches between 9s and 0s: A long +but finite sequence of 9s (more than 20) in the true result can initially be displayed as a larger +number ending in 0s. As we scroll, the 0s turn into 9s. When we immediately scroll back, the +number remains displayed as 9s, since the calculator caches the best known result (though not +currently across restarts or screen rotations).

+ +

We prevent 9s from turning into 0s during scrolling. If we generate a result ending in 9s, our +error bound implies that the true result is strictly less (in absolute value) than the value +(ending in 0s) we would get by incrementing the last displayed digit. Thus we can never be forced +back to generating zeros and will always continue to generate 9s.

+ +

Coping with mathematical limits

Internally the calculator essentially represents a number as a program for computing however +many digits we happen to need. This representation has many nice properties, like never resulting +in the display of incorrect results. It has one inherent weakness: We provably cannot compute +precisely whether two numbers are equal. We can compute more and more digits of both numbers, and +if they ever differ by more than one in the last computed digit, we know they are not +equal. But if the two numbers were in fact the same, this process will go on forever.

+ +

This is still better than machine floating point arithmetic, though machine floating point +better obscures the problem. With machine floating point arithmetic, two computations that should +mathematically have given the same answer, may give us substantially different answers, and two +computations that should have given us different answers may easily produce the same one. We +can indeed determine whether the floating representations are equal, but this tells us little +about equality of the true mathematical answers.

+ +

The undecidability of equality creates some interesting issues. If we divide a number by +x, the calculator will compute more and more digits of x until it finds some nonzero +ones. If x was in fact exactly zero, this process will continue forever.

We deal +with this problem using two complementary techniques:

+ +

We always run numeric computations in the background, where they won't interfere with user +interactions, just in case they take a long time. If they do take a really long time, we time +them out and inform the user that the computation has been aborted. This is unlikely to happen by +accident, unless the user entered an ill-defined mathematical expression, like a division by +zero.
As we will see below, in many cases we use an additional number representation that does allow +us to determine that a number is exactly zero. Although this easily handles most cases, it is not +foolproof. If the user enters "1÷0" we immediately detect the division by zero. If the user +enters "1÷(π−π)" we time out. (We might choose to explicitly recognize such simple cases in the +future. But this would always remain a heuristic.)

+ +

Zeros further than the eye can see

Prototypes of the M calculator, like mathematicians, treated all real numbers as infinite +objects, with infinitely many digits to scroll through. If the actual computation happened to be +2−1, the result was initially displayed as 1.00000000, and the user +could keep scrolling through as many thousands of zeroes to the right of that as he desired. +Although mathematically sound, this proved unpopular for several good reasons, the first one +probably more serious than the others:

+ +

If we computed $1.23 + $7.89, the result would show up as 9.1200000000 or the like, which is unexpected and harder to read quickly +than 9.12.
Many users consider the result of 2-1 to be a finite number, and find it confusing to be able +to scroll through lots of zeros on the right.
Since the calculator couldn't ever tell that a number wasn't going to be scrolled, it couldn't +treat any result as short enough to allow the use of a larger font.

+ +

As a result, the calculator now also tries to compute the result as an exact fraction whenever +that is easily possible. It is then easy to tell from the fraction whether a number has a finite +decimal expansion. If it does, we prevent scrolling past that point, and may use the fact that +the result has a short representation to increase the font size. Results displayed in a larger +font are not scrollable. We no longer display any zeros for non-zero results unless there is +either a nonzero or a displayed decimal point to the right. The fact that a result is not +scrollable tells the user that the result, as displayed, is exact. This is fallible in the other +direction. For example, we do not compute a rational representation for π−π, and hence it is +still possible to scroll through as many zeros of that result as you like.

+ +

This underlying fractional representation of the result is also used to detect, for example, +division by zero without a timeout.

+ +

Since we calculate the fractional result when we can in any case, it is also now available to +the user through the overflow menu.

+ +

More details

The underlying evaluate-on-demand arithmetic package is described in H. Boehm, "The +Constructive Reals as a Java Library'', Special issue on practical development of exact real +number computation, Journal of Logic and Algebraic Programming 64, 1, July 2005, pp. 3-11. +(Also at http://www.hpl.hp.com/techreports/2004/HPL-2004-70.html)

+ +

Our version has been slightly refined. Notably it calculates inverse trigonometric functions +directly instead of using a generic "inverse" function. This is less elegant, but significantly +improves performance.

+ + + + diff --git a/docs/implementation-overview.html b/docs/implementation-overview.html new file mode 100644 index 0000000..a06e73b --- /dev/null +++ b/docs/implementation-overview.html @@ -0,0 +1,51 @@ + + + +Calculator Implementation Overview + + +

M Calculator Implementation Overview

Although the appearance of the calculator has changed little from Lollipop, and some of the UI +code is indeed the same, the rest of the code has changed substantially. Unsurprisingly, +Calculator.java implements the main UI. The other major parts of the implementation +are:

+ +

CR.java in external/crcalc provides the underlying demand-driven ("constructive +real") arithmetic implementation. Numbers are represented primarily as objects with a method that +can compute arbitrarily precise approximations. The actual arithmetic performed by these methods +is based on Java's java.util.BigInteger arithmetic, with appropriate implicit +scaling.

+ +

BoundedRational.java is a rational arithmetic package that is used to provide finite +exact answers in "easy" cases. It is used primarily to determine when an approximation provided +by CR.java is actually exact. This is used in turn both to limit the length of displayed results +and scrolling, as well as to identify errors such as division by zero, that would otherwise result +in timeouts during computations. It is in some sense not needed to produce correct results, but +it significantly improves the usability of the calculator. It is also used for the "display as +fraction" option in the overflow menu.

+ +

CalculatorExpr.java implements calculator arithmetic expressions. It supports editing, +saving, restoring, and evaluation of expressions. Evaluation produces a constructive real (CR) +and possibly a BoundedRational result. Unlike the "arity" library used in earlier versions, the +underlying expression is represented as a sequence of "tokens", many of which are represented by +Button ids, not as a character string.

+ +

Evaluator.java implements much of the actual calculator logic, particularly background +expression evaluation. Expression evaluation here includes both using CalculatorExpr.java to +evaluate the expression, and then invoking the resulting CR value to actually produce finite +approximations and convert them to decimal. Two types of expression evaluation are supported: +(1) Initial evaluation of the expression and producing an initial decimal approximation, and (2) +reevaluation to higher precision. (1) is invoked directly from the Calculator UI, while (2) is +invoked from the calculator display, commonly in response to scrolling. When the display requests +a result, a "result" is immediately returned, though it may contains blank placeholders. The +display is then notified when the real result becomes available.

+ +

CalculatorText.java is the TextView subclass used to display the formula.

+ +

CalculatorResult.java is the TextView subclass used to display the result. It handles +result formatting, scrolling, etc. After the user hits "=", the CalculatorResult widget moves +into the top position, replacing the formula display. Currently it remains in that position until +the formula is again modified.

+ + + -- cgit v1.2.3