Fix getShortString(), tune evaluation heuristics.

Bug: 21474616

Rewrite getShortString() to also look at the least significant digit
information when available, and try to mimic the display formatting
code wherever appropriate.  As a result, when the user hits "=",
followed by "+" transitions are now more frequently smooth.

Revise the evaluation heuristics so the we are more aggressive
with the initial evaluation precision, and try harder to discover
the leading digit in a near-zero number.  Some of this is necessary
to keep getShortString() happy.  This version should also now
guarantee that we are never worse than double precision floating
pointing in displaying very small nonzero numbers.  If we display
a number as zero, the old calculator would have, too.  (And now
you can scroll to see whether it really is.)

Up the BoundedRational bit limit to improve the chances of identifying
exact results.

In general, the incremental computation cost for operating on
larger BigIntegers appears relatively low, so it makes sense to
trade longer computations for fewer calls.

Change-Id: I33066845b832753c109fcaf27f883b48e7e119d2

4 files changed, 103 insertions, 31 deletions

diff --git a/src/com/android/calculator2/BoundedRational.java b/src/com/android/calculator2/BoundedRational.java
index a6dd6d9..8bf2bf5 100644
--- a/src/com/android/calculator2/BoundedRational.java
+++ b/src/com/android/calculator2/BoundedRational.java
@@ -33,7 +33,7 @@ import com.hp.creals.AbortedError;
 
 public class BoundedRational {
     // TODO: Maybe eventually make this extend Number?
-    private static final int MAX_SIZE = 400; // total, in bits
+    private static final int MAX_SIZE = 800; // total, in bits
 
     private final BigInteger mNum;
     private final BigInteger mDen;
diff --git a/src/com/android/calculator2/CalculatorExpr.java b/src/com/android/calculator2/CalculatorExpr.java
index 6771b52..c5ad301 100644
--- a/src/com/android/calculator2/CalculatorExpr.java
+++ b/src/com/android/calculator2/CalculatorExpr.java
@@ -233,7 +233,7 @@ class CalculatorExpr {
         final BoundedRational mRatValue;
         private final CalculatorExpr mExpr;
         private final EvalContext mContext;
-        private final String mShortRep;
+        private final String mShortRep;  // Not internationalized.
         PreEval(CR val, BoundedRational ratVal, CalculatorExpr expr,
                 EvalContext ec, String shortRep) {
             mValue = val;
@@ -302,7 +302,7 @@ class CalculatorExpr {
         }
         @Override
         String toString(Context context) {
-            return mShortRep;
+            return KeyMaps.translateResult(mShortRep);
         }
         @Override
         TokenKind kind() { return TokenKind.PRE_EVAL; }
diff --git a/src/com/android/calculator2/CalculatorResult.java b/src/com/android/calculator2/CalculatorResult.java
index 7752525..34c8f9a 100644
--- a/src/com/android/calculator2/CalculatorResult.java
+++ b/src/com/android/calculator2/CalculatorResult.java
@@ -80,10 +80,10 @@ public class CalculatorResult extends AlignedTextView {
                             // is not noticeable.
     private static final int MAX_WIDTH = 100;
                             // Maximum number of digits displayed
-    private static final int MAX_LEADING_ZEROES = 6;
+    public static final int MAX_LEADING_ZEROES = 6;
                             // Maximum number of leading zeroes after decimal point before we
                             // switch to scientific notation with negative exponent.
-    private static final int MAX_TRAILING_ZEROES = 6;
+    public static final int MAX_TRAILING_ZEROES = 6;
                             // Maximum number of trailing zeroes before the decimal point before
                             // we switch to scientific notation with positive exponent.
     private static final int SCI_NOTATION_EXTRA = 1;
diff --git a/src/com/android/calculator2/Evaluator.java b/src/com/android/calculator2/Evaluator.java
index b127f05..16121f5 100644
--- a/src/com/android/calculator2/Evaluator.java
+++ b/src/com/android/calculator2/Evaluator.java
@@ -161,11 +161,24 @@ class Evaluator {
                                      // in current cached result, if determined.
                                      // This is just the index in mCache
                                      // holding the msd.
-    private static final int MAX_MSD_PREC = 100;
+    private static final int INIT_PREC = 50;
+                             // Initial evaluation precision.  Enough to guarantee
+                             // that we can compute the short representation, and that
+                             // we rarely have to evaluate nonzero results to
+                             // MAX_MSD_PREC.  It also helps if this is at least
+                             // EXTRA_DIGITS + display width, so that we don't
+                             // immediately need a second evaluation.
+    private static final int MAX_MSD_PREC = 320;
                              // The largest number of digits to the right
                              // of the decimal point to which we will
                              // evaluate to compute proper scientific
                              // notation for values close to zero.
+                             // Chosen to ensure that we always to better than
+                             // IEEE double precision at identifying nonzeros.
+    private static final int EXP_COST = 3;
+                             // If we can replace an exponent by this many leading zeroes,
+                             // we do so.  Also used in estimating exponent size for
+                             // truncating short representation.
 
     private AsyncReevaluator mCurrentReevaluator;
         // The one and only un-cancelled and currently running reevaluator.
@@ -361,7 +374,7 @@ class Evaluator {
         protected InitialResult doInBackground(Void... nothing) {
             try {
                 CalculatorExpr.EvalResult res = mExpr.eval(mDm, mRequired);
-                int prec = 3;  // Enough for short representation
+                int prec = INIT_PREC;
                 String initCache = res.mVal.toString(prec);
                 int msd = getMsdPos(initCache);
                 if (BoundedRational.asBigInteger(res.mRatVal) == null
@@ -504,7 +517,7 @@ class Evaluator {
                 return lastDigit;
             }
         }
-        if (msd > wholeSize && msd <= wholeSize + 4) {
+        if (msd > wholeSize && msd <= wholeSize + EXP_COST + 1) {
             // Display number without scientific notation.  Treat leading zero as msd.
             msd = wholeSize - 1;
         }
@@ -521,31 +534,88 @@ class Evaluator {
         return msd - wholeSize + lineLength - negative - 1;
     }
 
-    // Get a short representation of the value represented by
-    // the string cache (presumed to contain at least 5 characters)
-    // and possibly the exact integer i.
-    private String getShortString(String cache, BigInteger i) {
-        // The result is internationalized; we only display it.
-        String res;
-        boolean need_ellipsis = false;
+    private static final int SHORT_TARGET_LENGTH  = 8;
+    private static final String SHORT_UNCERTAIN_ZERO = "0.00000" + KeyMaps.ELLIPSIS;
 
-        if (i != null && i.abs().compareTo(BIG_MILLION) < 0) {
-            res = i.toString();
-        } else {
-            res = cache.substring(0,5);
-            // Avoid a trailing period; doesn't work with ellipsis
-            if (res.charAt(3) != '.') {
-                res = res.substring(0,4);
+    /**
+     * Get a short representation of the value represented by the string cache.
+     * We try to match the CalculatorResult code when the result is finite
+     * and small enough to suit our needs.
+     * The result is not internationalized.
+     * @param cache String approximation of value.  Assumed to be long enough
+     *              that if it doesn't contain enough significant digits, we can
+     *              reasonably abbreviate as SHORT_UNCERTAIN_ZERO.
+     * @param msdIndex Index of most significant digit in cache, or INVALID_MSD.
+     * @param lsd Position of least significant digit in finite representation,
+     *            relative to decimal point, or MAX_VALUE.
+     */
+    private String getShortString(String cache, int msdIndex, int lsd) {
+        // This somewhat mirrors the display formatting code, but
+        // - The constants are different, since we don't want to use the whole display.
+        // - This is an easier problem, since we don't support scrolling and the length
+        //   is a bit flexible.
+        // TODO: Think about refactoring this to remove partial redundancy with CalculatorResult.
+        final int dotIndex = cache.indexOf('.');
+        final int negative = cache.charAt(0) == '-' ? 1 : 0;
+        final String negativeSign = negative == 1 ? "-" : "";
+
+        // Ensure we don't have to worry about running off the end of cache.
+        if (msdIndex >= cache.length() - SHORT_TARGET_LENGTH) {
+            msdIndex = INVALID_MSD;
+        }
+        if (msdIndex == INVALID_MSD) {
+            if (lsd < INIT_PREC) {
+                return "0";
+            } else {
+                return SHORT_UNCERTAIN_ZERO;
+            }
+        }
+        // Avoid scientific notation for small numbers of zeros.
+        // Instead stretch significant digits to include decimal point.
+        if (lsd < -1 && dotIndex - msdIndex + negative <= SHORT_TARGET_LENGTH
+            && lsd >= -CalculatorResult.MAX_TRAILING_ZEROES - 1) {
+            // Whole number that fits in allotted space.
+            // CalculatorResult would not use scientific notation either.
+            lsd = -1;
+        }
+        if (msdIndex > dotIndex) {
+            if (msdIndex <= dotIndex + EXP_COST + 1) {
+                // Preferred display format inthis cases is with leading zeroes, even if
+                // it doesn't fit entirely.  Replicate that here.
+                msdIndex = dotIndex - 1;
+            } else if (lsd <= SHORT_TARGET_LENGTH - negative - 2
+                    && lsd <= CalculatorResult.MAX_LEADING_ZEROES + 1) {
+                // Fraction that fits entirely in allotted space.
+                // CalculatorResult would not use scientific notation either.
+                msdIndex = dotIndex -1;
             }
-            // TODO: Don't do this in the unlikely case this is the
-            // full representation.
-            need_ellipsis = true;
         }
-        res = KeyMaps.translateResult(res);
-        if (need_ellipsis) {
-            res += KeyMaps.ELLIPSIS;
+        int exponent = dotIndex - msdIndex;
+        if (exponent > 0) {
+            // Adjust for the fact that the decimal point itself takes space.
+            exponent--;
+        }
+        if (lsd != Integer.MAX_VALUE) {
+            int lsdIndex = dotIndex + lsd;
+            int totalDigits = lsdIndex - msdIndex + negative + 1;
+            if (totalDigits <= SHORT_TARGET_LENGTH && dotIndex > msdIndex && lsd >= -1) {
+                // Fits, no exponent needed.
+                return negativeSign + cache.substring(msdIndex, lsdIndex + 1);
+            }
+            if (totalDigits <= SHORT_TARGET_LENGTH - 3) {
+                return negativeSign + cache.charAt(msdIndex) + "."
+                        + cache.substring(msdIndex + 1, lsdIndex + 1) + "e" + exponent;
+            }
         }
-        return res;
+        // We need to abbreviate.
+        if (dotIndex > msdIndex && dotIndex < msdIndex + SHORT_TARGET_LENGTH - negative - 1) {
+            return negativeSign + cache.substring(msdIndex,
+                    msdIndex + SHORT_TARGET_LENGTH - negative - 1) + KeyMaps.ELLIPSIS;
+        }
+        // Need abbreviation + exponent
+        return negativeSign + cache.charAt(msdIndex) + "."
+                + cache.substring(msdIndex + 1, msdIndex + SHORT_TARGET_LENGTH - negative - 4)
+                + KeyMaps.ELLIPSIS + "e" + exponent;
     }
 
     // Return the most significant digit position in the given string
@@ -829,8 +899,10 @@ class Evaluator {
      * @return the {@link CalculatorExpr} representation of the current result
      */
     CalculatorExpr getResultExpr() {
-        final BigInteger intVal = BoundedRational.asBigInteger(mRatVal);
-        return mExpr.abbreviate(mVal, mRatVal, mDegreeMode, getShortString(mCache, intVal));
+        final int dotPos = mCache.indexOf('.');
+        final int leastDigPos = getLsd(mRatVal, mCache, dotPos);
+        return mExpr.abbreviate(mVal, mRatVal, mDegreeMode,
+               getShortString(mCache, getMsdPos(mCache), leastDigPos));
     }
 
     // Abbreviate the current expression to a pre-evaluated