expt(7, expt(10, 36789)) evaluates to 1

[schanzer]

expt(7, expt(10, 36789)) run in the starter2024 context produces this erroneous result, with no errors.

[shriram]

If it helps:

I ran expt(10, 36789) and it printed a very large number.

To see how big this is, I ran num-log(expt(10, 36789)). This produced

TypeError: Cannot read properties of undefined (reading 'throwDomainError')

Note that the error isn't coming from printing, because this also produces the same error:

t = num-log(expt(10, 36789))
# expt(7, t)

even without running the commented-out line.

The threshold is between 10^308 and 10^309, so for instance

t = expt(10, 308)
num-log(t) / 2.303

produces ~307.9445109171368, whereas

t = expt(10, 309)
num-log(t) / 2.303

produces the same error @schanzer reported.

@blerner will of course immediately point out that this range corresponds to the limit of an IEEE 754 64-bit double.

[blerner]

That's a weird one -- at the JS level, Math.pow(10, 309) yields Infinity, which I don't think we're handling correctly. Further, num-log(num-expt(10, 36789)) fails because (once again, darnit) errbacks is undefined. This is yet another bug somewhere in the js-nums library :(

[jpolitz]

Infinity is handled correctly – a good isOverflow check is in place for the fixnum case of expt. The problem is much harder for me to understand or even narrow past a certain point; I just see obvious nonsense but I'm not sure of the cause.

Something seems quite wrong with exponents in js-numbers going back to its inception. In WeScheme any exponent that would overflow into an integer bignum (the max fixnum boundary in js-numbers for integers is 9e15) triggers an error:

Pyret's version of js-numbers seems to do the right thing here:

But then does strange things with bignum exponents. I can't for the life of me understand why returning BigInteger.ONE makes sense here, but it's pretty directly reached from the BigInteger case of expt:

https://github.com/brownplt/pyret-lang/blob/horizon/src/js/base/js-numbers.js#L2893

The line in general is complete nonsense, because e can be (and is, in the expression expt(7, expt(10, 36789))) a BigInteger, so using < makes absolutely no sense here.

This code is unchanged from the js-numbers ported from WeScheme going back to original commits (WeScheme link is current HEAD, Pyret link is when we ported over the file):

https://github.com/bootstrapworld/wescheme/blob/master/war-src/js/js-runtime/js-numbers.js#L3173

https://github.com/brownplt/pyret-lang/commit/a0896e0aedd0612b80169bb39f50fde2b26daa03#diff-b9452083e0f01003c9f8c2005efdb6d3097e1637401dfc1697f7b89eecfe8845R2965

It's possible that we added new ways to reach bnpExp in erroneous ways in Pyret, which expects only fixnum exponents. However, given that any result that triggers the 9e15 overflow check within expt has issues in WeScheme, this whole domain seems dicey.

[jpolitz]

Also a remark on the related log example at the 64-bit float boundary – this is very likely to be a separate issue. It may be related, but representationally num-expt(10, 308) and num-expt(10, 309) both have BigInteger results, because the representable range of fixnums is exact integers within a 64-bit float, which is Number.MAX_SAFE_INTEGER = 9007199254740991.

So it's possible there's a separate issue where log is doing a float conversion that is impossible. Since I believe js-numbers does not have a log implementation that works outside of the JS-native one on floating point, logs on numbers like this should just be (good) errors.

[jpolitz]

Useful other context:

[jpolitz]

I tried this:

> git diff
diff --git a/src/js/base/js-numbers.js b/src/js/base/js-numbers.js
index bd0fe9523..eefd608f5 100644
--- a/src/js/base/js-numbers.js
+++ b/src/js/base/js-numbers.js
@@ -3815,7 +3817,13 @@ define("pyret-base/js/js-numbers", function() {
   // expt: pyretnum -> pyretnum
   // Produce the power to the input.
   BigInteger.prototype.expt = function(n, errbacks) {
-    return bnPow.call(this, n);
+    const fix = n.toFixnum();
+    if(isOverflow(fix)) {
+      const base = Rational.makeInstance(this, BigInteger.ONE, errbacks);
+      const expt = Rational.makeInstance(n, BigInteger.ONE, errbacks);
+      return base.expt(expt, errbacks);
+    }
+    return bnPow.call(this, fix);
   };

because the Rational implementation of expt is a repeated-multiplication algorithm (https://github.com/brownplt/pyret-lang/blob/horizon/src/js/base/js-numbers.js#L1742). Unfortunately it blows the stack when the exponent is Big.

> cat tests/pyret/regression/expt-log-big-number.arr

expt = num-expt

check:
  expt(expt(10, 16), 7) is-not 1
  expt(7, expt(10, 16)) is-not 1
  expt(7, expt(10, 16)) is 1
end
> node tests/pyret/regression/expt-log-big-number.jarr
file:///Users/joe/src/pyret-lang/tests/pyret/regression/expt-log-big-number.arr:4:0-8:3: check-block-1 (1/3)

  line 5, column 2: ok
  line 6, column 2: failed because:

Got unexpected exception
RangeError: Maximum call stack size exceeded
RangeError: Maximum call stack size exceeded
    at BigInteger.bnpToRadix [as toRadix] (/Users/joe/src/pyret-lang/tests/pyret/regression/expt-log-big-number.jarr:50306:22)
    at BigInteger.bnToString [as toString] (/Users/joe/src/pyret-lang/tests/pyret/regression/expt-log-big-number.jarr:49882:22)
    at splitIntIntoMantissaExpt (/Users/joe/src/pyret-lang/tests/pyret/regression/expt-log-big-number.jarr:48562:17)
    at BigInteger.toFixnum (/Users/joe/src/pyret-lang/tests/pyret/regression/expt-log-big-number.jarr:50993:13)
    at BigInteger.expt (/Users/joe/src/pyret-lang/tests/pyret/regression/expt-log-big-number.jarr:51145:19)
    at BigInteger.expt (/Users/joe/src/pyret-lang/tests/pyret/regression/expt-log-big-number.jarr:51149:19)
    at BigInteger.expt (/Users/joe/src/pyret-lang/tests/pyret/regression/expt-log-big-number.jarr:51149:19)
    at BigInteger.expt (/Users/joe/src/pyret-lang/tests/pyret/regression/expt-log-big-number.jarr:51149:19)
    at BigInteger.expt (/Users/joe/src/pyret-lang/tests/pyret/regression/expt-log-big-number.jarr:51149:19)
   ...

[schanzer]

@ds26gte , you should be aware of this issue. It's not our top priority for Bootstrap, but the content Algebra 2 is absolutely pushing us into more and more of these extreme cases.

[blerner]

@jpolitz I just reread your last patch more carefully. I'm not sure why you're making the base into a Rational. I think that's what's triggering the stack overflow: it's a Rational containing Big Integers, so when Rational tries to run expt, it goes back to the Big Integer case, which creates a new Rational... I'm not at my laptop right now to try it out, but it does seem like it should be possible to stay in the Integer space, until dealing with any fractional part of the exponent and switching over to taking roots...

[ds26gte]

There were two different coding errors contributing to these problem:

• BigInteger.prototype.log() in particular and other similar functions were taking two parameters when they should be taking only one. This causes the errbacks parameter to be bound to an incorrect object. I've corrected all these (even those not relevant to this report)
• I've added the errbacks parameter to the functions bnpExp(), bnModPowInt(), bnPow(). Also bnpExp() erroneously returns 1 for a too-large exponent. I've used the newly incoming errbacks argument to signal an error instead

One could say that having num-log return a roughnum error for num-log(expt(10, 36789)) is wrong when it's clearly a very tractable number. However it's better than the missing throwDomainError error previously thrown. We need to improve the log() functions definitely as the next step.

I've created a PR containing the fix(es).