0
\$\begingroup\$

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 . 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.

\$\endgroup\$

closed as unclear what you're asking by xnor, mbomb007, Sriotchilism O'Zaic, Christopher, Steadybox Apr 6 '17 at 21:32

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ 2. what prevents using while(condition) { things; break; } as an if statement? \$\endgroup\$ – dkudriavtsev Apr 6 '17 at 19:19
  • 1
    \$\begingroup\$ @Alt-F4 1: Allowed, just takes 2 operations. 2: Not allowed by the rules. \$\endgroup\$ – programmer5000 Apr 6 '17 at 19:21
  • 10
    \$\begingroup\$ I think it would have been better to wait longer before posting this. The original challenge is only 3 hours old. I find challenges tend to feel less exciting when you've just solved a very similar one. Also, we've had way too many challenge to implement some arithmetic operation without using some more basic operation(s). \$\endgroup\$ – xnor Apr 6 '17 at 19:45
  • 1
    \$\begingroup\$ are loops operations? \$\endgroup\$ – dkudriavtsev Apr 6 '17 at 20:15
  • 3
    \$\begingroup\$ @programmer5000 I agree with xnor. You should definitely wait a couple days before posting a challenge based on another one. Maybe even use the Sandbox first. It's already feeling like it's getting old, simply because this is 2 in one day. \$\endgroup\$ – mbomb007 Apr 6 '17 at 20:21
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ There's an explicit list of operations that are allowed. A "repeat n times loop" isn't one of them; you'll need to maintain a loop counter explicitly. \$\endgroup\$ – user62131 Apr 6 '17 at 20:17
  • \$\begingroup\$ @ais523 fixed... \$\endgroup\$ – dkudriavtsev Apr 6 '17 at 20:23
2
\$\begingroup\$

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 -&

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.