Untitled

mail@pastecode.io avatar
unknown
javascript
2 years ago
2.2 kB
23
Indexable
Never
// All arguments must be BigInts. Return value is a BigInt or a thrown RangeError
const bigH = (n, a, b) => {
  if (n < 0n || a < 0n || b < 0n) {
    throw Error('Can only hyperoperate on non-negative integers')
  }

  // [n, a, b, i result]
  let stack = [[0n, 0n, 0n, 0n, 0n], [n, a, b, 1n, a]]
  // 1 = just pushed a stack frame
  // 2 = just returned into the body of the loop
  let state = 1
  while (stack.length > 1) {
    let base_result = undefined
    let [n, a, b, i, result] = stack[stack.length - 1]
    
    switch (state) {
      case 1:
        // in some ways, stack overflows are the greatest base cases of all
        if (stack.length > 1000) {
          throw RangeError('stack')
        }

        // successor operator
        if (n === 0n) {
          // Ignore `a`
          base_result = b + 1n
          
        // addition
        } else if (n === 1n) {
          base_result = a + b

        // multiplication
        } else if (n === 2n) {
          base_result = a * b

        // exponentiation
        } else if (n === 3n) {
          base_result = a ** b

        // n >= 4, time for some handy base cases

        } else if (a === 0n) {
          // Fun fact:
          base_result = b % 2n === 0n ? 1n : 0n

        } else if (a === 1n) {
          // 1^...^b = 1 for all finite b
          base_result = 1n

        // a >= 2

        } else if (b === 0n) {
          // a^0 = 1 for all a >= 2
          base_result = 1n

        } else if (b === 1n) {
          // a^...^1 = a for all a >= 2
          base_result = a

        // b >= 2

        } else if (a === 2n && b === 2n) {
          // Another fun fact
          base_result = 4n
        }
        break;

      case 2:
        if (i === b) {
          base_result = result
        }
        break;
    }
    if (base_result !== undefined) {
      // "return"
      stack.pop()
      // save result into previous stack frame
      stack[stack.length - 1][4] = base_result
      state = 2
    } else {
      // if we didn't hit a base case, increment i and push a stack frame
      stack[stack.length - 1][3] += 1n
      stack.push([n - 1n, a, result, 1n, a])
      state = 1
    }
  }

  return stack[0][4]
}