Fix exponentiation and timeout issues
Bug:33433764
Bug:33105915
Use the recursive algorithm for exponentiation with an integer
exponent and a base that cannot be determined to be positive.
Use of the log-based algorithm caused expressions like (-pi)^3
to fail. (Note that the recursive exponentiation algorithm
is essentially a clone of rawPow in BoundedRational, not a new
invention.)
Catch stack overflows during expression evaluation and treat them
as timeouts. This is a bit challenging for the underlying VM, but
it's supposed to work, and it seems to. We only rely on it in
cases that previously failed without anyone noticing, like
2^2^2^2^2^2.
Don't just write out the long timeout information. Also read it
back in. Duh.
Some drive-by comment improvements.
Change-Id: I13f84850de5d1b9323b63ae2b769a22d97d0ae66
diff --git a/src/com/android/calculator2/UnifiedReal.java b/src/com/android/calculator2/UnifiedReal.java
index d3bc947..cb8a512 100644
--- a/src/com/android/calculator2/UnifiedReal.java
+++ b/src/com/android/calculator2/UnifiedReal.java
@@ -512,6 +512,7 @@
/**
* Returns true if values are definitely known not to be equal, false in all other cases.
+ * Performs no approximate evaluation.
*/
public boolean definitelyNotEquals(UnifiedReal u) {
boolean isNamed = isNamed(mCrFactor);
@@ -539,6 +540,10 @@
return mRatFactor.signum() == 0;
}
+ /**
+ * Can this number be determined to be definitely nonzero without performing approximate
+ * evaluation?
+ */
public boolean definitelyNonZero() {
return isNamed(mCrFactor) && mRatFactor.signum() != 0;
}
@@ -861,7 +866,27 @@
private static final BigInteger BIG_TWO = BigInteger.valueOf(2);
/**
+ * Compute an integral power of a constrive real, using the standard recursive algorithm.
+ * exp is known to be positive.
+ */
+ private static CR recursivePow(CR base, BigInteger exp) {
+ if (exp.equals(BigInteger.ONE)) {
+ return base;
+ }
+ if (exp.and(BigInteger.ONE).intValue() == 1) {
+ return base.multiply(recursivePow(base, exp.subtract(BigInteger.ONE)));
+ }
+ CR tmp = recursivePow(base, exp.shiftRight(1));
+ if (Thread.interrupted()) {
+ throw new CR.AbortedException();
+ }
+ return tmp.multiply(tmp);
+ }
+
+ /**
* Compute an integral power of this.
+ * This recurses roughly as deeply as the number of bits in the exponent, and can, in
+ * ridiculous cases, result in a stack overflow.
*/
private UnifiedReal pow(BigInteger exp) {
if (exp.signum() < 0) {
@@ -894,7 +919,17 @@
}
}
}
- return new UnifiedReal(crValue().ln().multiply(CR.valueOf(exp)).exp());
+ if (signum(DEFAULT_COMPARE_TOLERANCE) > 0) {
+ // Safe to take the log. This avoids deep recursion for huge exponents, which
+ // may actually make sense here.
+ return new UnifiedReal(crValue().ln().multiply(CR.valueOf(exp)).exp());
+ } else {
+ // Possibly negative base with integer exponent. Use a recursive computation.
+ // (Another possible option would be to use the absolute value of the base, and then
+ // adjust the sign at the end. But that would have to be done in the CR
+ // implementation.)
+ return new UnifiedReal(recursivePow(crValue(), exp));
+ }
}
public UnifiedReal pow(UnifiedReal expon) {