Untitled

mail@pastecode.io avatar
unknown
javascript
2 years ago
2.0 kB
33
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 = [[n, a, b, 1n, a]]
  while (true) {
    // in some ways, stack overflows are the greatest base cases of all
    if (stack.length > 1000) {
      throw RangeError('stack')
    }

    let base_result = undefined;

    let [n, a, b, i, result] = stack[stack.length - 1]
    
    // 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

      // check termination condition of loop
      // which isn't really a base case
    } else if (i === b) {
      base_result = result
    }


    if (base_result !== undefined) {
      stack.pop()

      // if we're in outermost stack frame, return
      if (stack.length == 0) {
        return base_result
      }

      // otherwise save result into previous stack frame
      stack[stack.length - 1][4] = base_result
    } 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])
    }
  }
}