Created
November 28, 2021 04:46
-
-
Save mumbleskates/557f2d9cdd09118682748494aa1f9eb9 to your computer and use it in GitHub Desktop.
Hyperoperator with only tail recursion
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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