Skip to content

Instantly share code, notes, and snippets.

@mumbleskates
Created November 28, 2021 04:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mumbleskates/557f2d9cdd09118682748494aa1f9eb9 to your computer and use it in GitHub Desktop.
Save mumbleskates/557f2d9cdd09118682748494aa1f9eb9 to your computer and use it in GitHub Desktop.
Hyperoperator with only tail recursion
// All arguments must be BigInts. Return value is a BigInt or a thrown RangeError
const bigH = (n, a, b) => {
let result = 0n
const stack = [{n, a, b}]
do {
const {n, a, b} = stack.pop()
if (n < 0n || a < 0n || b < 0n) {
throw Error('Can only hyperoperate on non-negative integers')
}
// successor operator
if (n === 0n) {
// Ignore `a`
result = b + 1n
continue
}
// addition
if (n === 1n) {
result = a + b
continue
}
// multiplication
if (n === 2n) {
result = a * b
continue
}
// exponentiation
if (n === 3n) {
result = a ** b
continue
}
// n >= 4, time for some handy base cases
if (a === 0n) {
// Fun fact:
result = b % 2n === 0n ? 1n : 0n
continue
}
if (a === 1n) {
// 1^...^b = 1 for all finite b
result = 1n
continue
}
// a >= 2
if (b === 0n) {
// a^0 = 1 for all a >= 2
result = 1n
continue
}
if (b === 1n) {
// a^...^1 = a for all a >= 2
result = a
continue
}
// b >= 2
if (a === 2n && b === 2n) {
// Another fun fact
result = 4n
continue
}
let result = a
// push the next iteration of this hyperoperator's loop
// like: `for (let i = 1n; i < b; i++) ...`
// When n and/or a and/or b get low enough, the last couple iterations
// of the loop get optimized in the normal way.
stack.push({n, a, b: b - 1n})
// call the function in the downwards recursion
// like: `result = bigH(n - 1n, a)`
stack.push({n: n - 1n, a, b: result})
} while (stack.length > 0);
return result
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment