Tetration: (Very) Hard Mode

Question

This question is inspired by this one

Your task

Make a program or function that calculates the Tetration of 2 numbers. Tetration is what "comes next after addition, multiplication, and exponents".

For example, passing in 3 and 3, this is calculated:

3 ^ (3 ^ 3)

yielding this:

7625597484987

Simple, right?

WRONG.

Rules

The rules are taken from this question's inspiration.

Rules:

• An integer is 64 bits, signed, two's complement. This is the only data type you may work with.
• You may only use the following operations. Each of these counts as one operation.
  • n << k, n >> k: Left/right shift n by k bits. Sign bit is extended in right shift.
  • n >>> k: Right shift but do not extend sign bit. 0's are shifted in.
  • a & b, a | b, a ^ b: Bitwise AND, OR, XOR.
  • [removed], a - b [removed]: [removed], subtract [removed]
  • ~b: Bitwise invert.
  • -b: Two's complement negation.
  • a / b, a % b: Divide (integer quotient, rounds towards 0), and modulo.

• Comparison operators (<=, >=, >, <, etc.) are allowed but count as one operation.

   - Modulo of negative numbers uses the rules [specified in C99](http://stackoverflow.com/a/11720841/616460): `(a/b) * b + a%b`

shall equal a. So 5 % -3 is 2, and -5 % 3 is -2: - 5 / 3 is 1, 5 % 3 is 2, as 1 * 3 + 2 = 5. - -5 / 3 is -1, -5 % 3 is -2, as -1 * 3 + -2 = -5. - 5 / -3 is -1, 5 % -3 is 2, as -1 * -3 + 2 = 5. - -5 / -3 is 1, -5 % -3 is -2, as 1 * -3 + -2 = -5. - Note that Python's // floor division operator does not satisfy the "round towards 0" property of division here. - Assignments do not count as an operation. As in C, assignments evaluate to the value of the left-hand side after the assignment: a = (b = a + 5) sets b to a + 5, then sets a to b, and counts as one operation. - Compound assignments may be used a += b means a = a + b and count as one operation. - You may use integer constants, they do not count as anything. - Parentheses to specify order of operations are acceptable. - You may declare functions. Function declarations can be in any style that is convenient for you but note that 64 bit integers are the only valid data type. Function declarations do not count as operations, but a function call counts as one. Also, to be clear: Functions may contain multiple return statements and returns from any point are allowed. The return itself does not count as an operation. - You may declare variables at no cost. - You may use while loops, but you may not use if or for. Operators used in the while condition count towards your score. while loops execute as long as their condition evaluates to a non-zero value (a "truthy" 0 in languages that have this concept is not a valid outcome). Since early-return is allowed, you are allowed to use break as well - Overflow/underflow is allowed and no value clamping will be done. It is treated as if the operation actually happened correctly and was then truncated to 64 bits.

Scoring / Winning Criteria:

...

This is atomic-code-golf. Your score is the total number of operations present in your code (as defined above), not the total number of operations that are executed at run-time. The following code:

function example (a, b) {
    return a + ~b;
}

function ispowerofnegtwo (input) {
    y = example(input, 9);
    y = example(y, 42);
    y = example(y, 98);
    return y;
}

Contains 5 operations: two in the function, and three function calls.

It doesn't matter how you present your result, use whatever is convenient in your language, be it ultimately storing the result in a variable, returning it from a function, or whatever.

The winner is the post that is demonstrably correct (supply a casual or formal proof if necessary) and has the lowest score as described above.

Note: If you'd like to provide a solution in a language that only supports 32-bit integers, you may do so, provided that you sufficiently justify that it will still be correct for 64-bit integers in an explanation.

Also: Certain language-specific features may be permitted at no-cost if they do not evade the rules but are necessary to coerce your language into behaving according to the rules above. For example (contrived), I will permit a free not equals 0 comparison in while loops, when applied to the condition as a whole, as a workaround for a language that has "truthy" 0's. Clear attempts to take advantage of these types of things are not allowed -- e.g. the concept of "truthy" 0 or "undefined" values does not exist in the above ruleset, and so they may not be relied on.

breaks are allowed, but they count as an operation.

Also, if your language has no concept of 64-bit ints, you may use any other form of number.

Note that you are not allowed to use multiplication, exponentiation, or addition.

Answer 1

Ruby, 13 operations

def tetr(a, b)
  def exp(a, b)
    def mult(a, b)
      c = 0; i = 0; while(i > -b) do c -= a; i -= 1; end
      return -c
    end
    c = 1; i = 0; while(i > -b) do c = mult(c, a); i -= 1; end
    return c
  end
  c = a; i = -1; while(i > -b) do c = exp(a, c); i -= 1; end
  return c
end

OP has stated that comparison is allowed.

Answer 2

Wise, 31 29

:::[:^|>::>^]|[:^?-!]^
::^? [::><^[-~!~-?]^>?->!]^
!:-~[:^&:]^?-&

When I saw this question I thought it would be the perfect question to answer in Wise. The way Wise is set up it is impossible to make an answer that does not qualify for this challenge because all of Wise's operations are bitwise.

• :, !, and ? are all stack operations which I am considering to be variable assignments so they do not count towards the score

• [] constitute a while loop so they don't count towards the score.

• ^,|, and & are bitwise XOR, OR, and AND respectively

• >,< are the bitshifts,

• ~ is bitwise negation and - is regular negation.

Explanation

First we want to take the absolute value of the number so that we can check if the number is a power of 2.

:[:^|>::>^]|

is a program I wrote a while ago to get the sign bit of a number.

[:^?-!]^

will negate the number if the top of the stack is -1, that is if our input was negative.

Now that we have a positive number we want to check if it is a power of 2. to do this we take the sum of the digits (in base 2) and check if it is one. To do that we set up a zero on the bottom of the stack:

::^?

and loop through adding the last digit and dividing by 2 (bit-shifting once)

[::><^[-~!~-?]^>?-!]^!

While we are doing this we divide a copy of our original input by -2 (->) each time we loop. If the result -1 and the absolute value of the input was a power of 2 it is a power of -2.

Now we subtract one -~ and take the logical not of the digit sum.

[:^&:]^

We roll this result to the bottom with ? and finish up with a logical and with -&