Implement hyperexponentiation/tetration without the use of '^'

The Challenge

Implement tetration (aka Power Tower or Hyperexponentiation) with the least amount of characters.

The Conditions

• Don't use the 'power' operator or its equivalents (such as `pow(x,y)`, `x^y`, `x**y`, etc.)
• Input given as: `x y` (separated by a space)
• `x` is exponentiated by itself `y` times.
• Your method must be able to compute at least `4 3` (4 exponentiated by itself 3 times)

The Scoring

• Lowest score wins: (# of characters) + (10 * (# of 'power' operators))

• Bonus deduction if you do not use the multiplication operator (-5 points).

• No Speed/Memory requirements. Take as long as you want.

Examples

`x 0` = 1

`2 2` = 2^2 = 4

`2 4` = 2^(2^(2^2)) = 65536

`4 3` = 4^(4^4) = 4^256 = `13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096`

Open to suggestions/alterations/questions

-
One alteration which I think is fairly important is to replace "* operator" with "multiplication operator". In GolfScript `*` is multiplication in some contexts, but it's also the simple looping operator: `{block}N*` is equivalent to C-style `for(i=0;i<N;i++){block}`. The tricky edge case is string/array multiplication (`'a'3*` gives `'aaa'`), but that's unlikely to be an issue given that an array of `4***3` elements will overflow RAM. – Peter Taylor Apr 19 '12 at 8:38
@PeterTaylor Thanks, updated. – MrZander Apr 19 '12 at 21:12
Also worth adding a test for the edge case `x 0` => 1. My original solution didn't handle that case. – Peter Taylor Apr 19 '12 at 21:20
Thanks, added that as well. I also added that speed is not a requirement. – MrZander Apr 19 '12 at 21:21
The penalty for using multiplication is way too low. (:=bonus for not using it). I made a solution which didn't used it, and had to replace it to avoid stack overflows, and gained a 7 char win for a 5 char bonus loss. – user unknown Apr 20 '12 at 3:32

J, 1619 12 characters

``````*/@\$~/1,~\$~/
``````

or as a verb (17 characters):

``````h=:[:*/@\$~/1,~\$~/
``````

usage:

``````   h 2 4
65536
``````

or taking input from keyboard (24 27 20 characters):

``````*/@\$~/1,~\$~/".1!:1]1
``````

with thanks to FUZxxl for pointing out my stupidity. :-)

Explanation:

J is read from right to left, so using `2 4`:

`/` is used to insert the verb `\$~` between each pair of items in the list. `\$~` takes the left item and shapes it `\$` using the right item (the `~` reverses the arguments) - so this would be equivalent to `4 \$ 2` which gives you a list of `2`s which is four items long `2 2 2 2`.

Now we append 1 to the list `1,~` and then do the same thing again; `/` insert a verb `*/@\$~` between each pair of items in the list. This verb starts in the same way `\$~` but this time it `/` inserts a `*` between each item of the newly generated list. The `@` just makes sure that the `*/@\$~` works as one verb instead of two. This gives `2` multiplied by itself enough times to be equivalent to `2^4`.

J's vocabulary page - I find solving problems with J fun just because of the different way it sometimes does things.

Adding one further iteration to remove the `*` operator has 2 problems

• It comes out at 17 characters (`+/@\$~/,@\$~/1,~\$~/`) which, even with the -5 bonus, is too long
• It runs out of memory if the number gets too large so doesn't meet the requirement of being able to calculate `4 3`
-
 Could you provide an explanation? This looks interesting. – MrZander Apr 19 '12 at 21:23 @MrZander I've edited my answer to add an explanation. – Gareth Apr 19 '12 at 21:48 Not sure if I have a better understanding or more confusion, but thanks haha. – MrZander Apr 19 '12 at 21:50 The explanation implies that the whole thing is doing exponentiation rather than tetration. Which of us is missing something? – Peter Taylor Apr 19 '12 at 22:28 @PeterTaylor I suspect my explanation is not very clear. If it was doing tetration I would have just used `^/]\$[` which creates the list `2 2 2 2` and sticks the exponentiation operator between them. What this is doing is going a step further and doing the exponentiation by repeated multiplication. – Gareth Apr 20 '12 at 7:24

GolfScript (24 chars - 5 = 19 points)

``````~\1{1{0{+}?}?}{@\+@*}:?~
``````

is insanely slow.

(or 20 chars)

``````~\1{1{*}?}{@\+@*}:?~
``````

is much faster.

-
Since GolfScript is a Ruby program, we can test on ideone :) ideone.com/GTIfP. I've also emailed ideone suggesting they add support for GolfScript. – mellamokb Apr 19 '12 at 16:44
@mellamokb, it'll be nice if they do add it, but I'm not too optimistic because their stated policy is to add languages which are supported by their distro. – Peter Taylor Apr 19 '12 at 21:18
I read that too... but since they support Ruby, and GolfScript is just a Ruby program, it should be easy :) Just create a bash script that passes in the parameters. – mellamokb Apr 19 '12 at 21:26
+1 ideone.com/eW2F3 :) – mellamokb Apr 20 '12 at 13:36

Ruby, 66 59 characters

``````def e(x,y)
r=1
(1..y).each{t=x
(2..r).each{t*=x}
r=t}
r
end
``````
-
 Unfortunately, this script does not produce the correct output (`1`) when the second input number is `0`; rather, `e(x,0)` returns the value of `x`. – r.e.s. Apr 21 '12 at 3:09 @r.e.s. you are right. I fixed the code. Thanks! – w0lf Apr 21 '12 at 7:31

Python, 161 - 5 (no * operator) = 156

``````r=xrange
def m(x,y):
i=0
for n in r(y):i+=x
return i
def e(x,y):
i=1
for n in r(1,y+1):i=m(i,x)
return i
def t(x,y):
i=1
for n in r(y):i=e(x,i)
return i
``````

invoke:

``````t(2, 4)
``````
-
Is multiplication by iterated addition really fast enough to evaluate `4***3`?! – Peter Taylor Apr 19 '12 at 14:38
@PeterTaylor yes? it completes in less than a second for me – Blazer Apr 19 '12 at 17:28
Wow. The equivalent GolfScript version takes aaaaaaages. – Peter Taylor Apr 19 '12 at 21:24
As in, I've left it running overnight and it still hasn't finished. – Peter Taylor Apr 20 '12 at 6:26
@PeterTaylor: Have you tried 3***3? I interrupted my Scala program after a few minutes. – user unknown Apr 20 '12 at 8:32
show 1 more comment

Python, 112 chars

The numbers should be the 1st and 2nd argument: `python this.py 4 3`
`**` operator not used.
`*` used. It's quite trivial to implement, exactly like `**`, but costs more than 5 chars.

``````import sys
p=lambda y:y and x*p(y-1)or 1
t=lambda y:y>1 and p(t(y-1))or x
x,y=map(long,sys.argv[1:])
print t(y)
``````
-
 How do I use the code to compute 4 3? And, just of curiosity: Have you tried to implement * that way, and to compute 4 3 then? – user unknown Apr 20 '12 at 8:29 @userunknown, Input is by parameters. I added an explanation to the answer. I didn't try to add the `*` implementation, I believe the recursion depth would be too large for `4 3`. – ugoren Apr 20 '12 at 12:10

C, 117105 99 chars

EDIT: Merged the two functions `p` and `r` into one, saving some chars.
Of 99 chars, 52 do the actual calculation (including variable definitions). The other 47 are for handling input and output.
BUG: Badly handles powers of 0 (e.g. `0 2`). Should find a minimum cost fix. This isn't a bug, I forgot that `0 2` is undefined.

Successfully handles `4 3`, and even gives an exact result. However, can be inaccurate for some smaller numbers.
Prints the number with a trailing `.000000`.

``````x,y,z;
double R(){return--y?!z?y=R(),R(z=1):x*R():x;}
main(){
scanf("%d%d",&x,&y);
printf("%f\n",R());
}
``````
-
Looks like 118 chars to me: ideone.com/9D5SU – mellamokb Apr 19 '12 at 16:28
Testing this with 4 3 is only accurate to about 18 places, double doesn't have nearly enough precision to support an exact representation. – Sir_Lagsalot Apr 19 '12 at 19:40
@Sir_Lagsalot, double has more than enough precision for 4^256. It only has one significant digit. – ugoren Apr 19 '12 at 20:03
Ah good point, I wasn't thinking in binary. Does it actually print out the exact value for you? It gets truncated after the first 18 or so decimal digits on my machine, but I'm willing to accept that's system specific. – Sir_Lagsalot Apr 19 '12 at 20:15
@Sir_Lagsalot: See the ideone link I provided. It prints out the whole number. – mellamokb Apr 19 '12 at 21:03
show 1 more comment

Perl, 61 chars

here's a bizarre one

``````sub t
{
(\$x,\$y,\$z)=@_;
\$y>1&&t(\$x,\$y-1,eval\$x."*\$x"x(\$z-1||1))||\$z
}
``````

usage:

``````print t(2,4,1)
``````
-
an incorrect one too – ardnew Apr 19 '12 at 16:19

Haskell, 87 85 - 5 == 80 82

``````import Data.List
t x=genericLength.(iterate(sequence.map(const\$replicate x[]))[[]]!!)
``````

Uses neither of exponentiation, multiplication or addition (!), just list operations. Demonstration:

``````Prelude> :m +Data.List
Prelude Data.List> let t x=genericLength.(iterate(sequence.map(const\$replicate x[]))[[]]!!)
Prelude Data.List> t 2 2
4
Prelude Data.List> t 2 4
65536
Prelude Data.List> t 4 3
``````

...
ahm... you didn't say anything about performance or memory, did you? But given enough billions of years and some petabytes of RAM, this would still yield the correct result (genericLength can use a bigInt to count the length of the list).

-
I trust you will have an answer for me by 3012? ;) – MrZander Apr 19 '12 at 21:26
I'll need some help from Moore's law, but that given I might. – leftaroundabout Apr 19 '12 at 22:00
+1 for thinking outside the box. – Neil Apr 20 '12 at 15:15

GolfScript, 15 18 chars

``````~])*1\+{[]+*{*}*}*
``````

Yes, one of the `*`s is a multiplication operator (exercise: which one?) so I don't qualify for the 5 char bonus. Still, it's just barely shorter than Peter's solution.

This earlier 15-char version is otherwise the same, but produces no output when the second argument is 0. Thanks to r.e.s. for spotting the bug.

``````~])*{[]+*{*}*}*
``````
-
This produces fatal errors, e.g. with `"2 3" ~])*{[]+*{*}*}*`. – r.e.s. Apr 20 '12 at 3:37
@r.e.s., it produces the correct answer for me. – Peter Taylor Apr 20 '12 at 6:29
@r.e.s.: It assumes that there's nothing else on the stack but the input. If you want to provide the input in-line like in your example, first use `;` to remove the actual input string that the interpreter puts on the stack at start-up. Or just prepend a `[` to the code: both `;"2 3" ~])*{[]+*{*}*}*` and `"2 3" [~])*{[]+*{*}*}*` work fine for me. – Ilmari Karonen Apr 20 '12 at 10:40
(+1) Thanks! Those variations work and solve a mystery for me. The tutorial says "You don't have to pipe input in, but if you don't, it will not prompt for input, instead it will assume there is no input." So I've been using just `ruby golfscript.rb my_script.gs` on the command line, without knowing that it causes something ("", apparently) to be on the stack before the script is run -- which sometimes works, sometimes not. (Also, with `echo 2 3 | ruby golfscript.rb my_script.gs`, your program does work as-given.) – r.e.s. Apr 20 '12 at 13:18
ideone.com/547LG – r.e.s. Apr 20 '12 at 16:01

Scala:110

``````type B=BigInt
def r(a:B,b:B,f:(B,B)=>B):B=if(b>1)f(a,r(a,b-1,f))else a
def h(a:B,b:B)=r(a,b,r(_,_,r(_,_,(_+_))))
``````

ungolfed:

``````type B=BigInt
def recursive (a:B, b:B, f:(B,B)=>B): B =
if (b>1) f (a, recursive (a, b-1, f))
else a
recursive (2, 3, recursive (_, _, recursive (_, _, (_ + _))))
``````

explanation:

``````type B=BigInt
def p (a:B, b:B):B = a+b
def m (a:B, b:B):B = if (b>1) p (a, m (a, b-1)) else a
def h (a:B, b:B):B = if (b>1) m (a, h (a, b-1)) else a
def t (a:B, b:B):B = if (b>1) h (a, t (a, b-1)) else a
``````

plus, mul, high(:=pow), tetration all work in the same manner. The common pattern can be extracted as recursive method, which takes two BigInts and a basic function:

``````def r (a:B, b:B, f:(B,B)=>B):B =
if (b>1) f(a, r(a, b-1, f)) else a
r (4, 3, r (_,_, r(_,_, (_+_))))
``````

The underlines are placeholder for something which gets called in this sequence, for example the addition plus(a,b)=(a+b); therefore (+) is a function which takes two arguments and adds them (a+b).

unfortunately, I get issues with the stack size. It works for small values for 4 (for example: 2) or if I reduce the depth for one step:

``````def h(a:B,b:B)=r(a,b,r(_,_,(_*_))) // size -7, penalty + 5
def h(a:B,b:B)=r(a,b,r(_,_,r(_,_,(_+_))))
``````

The original code is 112 characters and would score, if valid, 107. Maybe I find out how to increase the stack.

The expanded algorithm can be transformed to tailrecursive calls:

``````type B=BigInt
def p(a:B,b:B):B=a+b
import annotation._
@tailrec
def m(a:B,b:B,c:B=0):B=if(b>0)m(a,b-1,p(a,c))else c
@tailrec
def h(a:B,b:B,c:B=1):B=if(b>0)h(a,b-1,m(a,c))else c
@tailrec
def t(a:B,b:B,c:B=1):B=if(b>0)t(a,b-1,h(a,c))else c
``````

The tailrecursive call is longer than the original method, but didn't raise a stackoverflow in the long version - however it doesn't yield a result in reasonable time. t(2,4) is fine, but t(3,3) already was stopped by me after 5 min. However, it is very elegant, isn't it?

``````// 124 = 119-5 bonus
type B=BigInt
def r(a:B,b:B,c:B,f:(B,B)=>B):B=if(b>0)r(a,b-1,f(a,c),f)else c
def t(a:B,b:B)=r(a,b,1,r(_,_,1,r(_,_,0,(_+_))))
``````

And now the same as above: use stinky multiplication (we even profit while rejecting the bonus of 5, because we save 7 characters: win=4 chars:)

``````// 115 without bonus
type B=BigInt
def r(a:B,b:B,c:B,f:(B,B)=>B):B=if(b>0)r(a,b-1,f(a,c),f)else c
def t(a:B,b:B)=r(a,b,1,r(_,_,1,(_*_)))
``````

invocation:

``````timed ("t(4,3)")(t(4,3))
t(4,3): 1
scala> t(4,3)
res89: B = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
``````

runtime: 1ms.

-

Python, 70

This uses nested `eval` calls, eventually producing a string `"a*a*a*a...*a"` which gets evaluated. Almost half of the score is wasted on getting the arguments... though I've noticed that a few other solutions don't bother with that.

``````a,b=map(int,raw_input().split())
exec"eval('*'.join('a'*"*b+'1'+'))'*b
``````
-
If we assume the arguments are comma sepearated, you could use `input()` or use `eval(raw_input())` Cheers – st0le Apr 23 '12 at 15:00
@st0le, please read the question – boothby Jun 22 '12 at 7:47
Nice one. The second line can be golfed even more: `exec"eval('a*'*"*b+'1'+"+'1')"*b` – flornquake May 13 at 23:42
@flornquake good catch! thanks! – boothby May 14 at 1:48

*Perhaps the no multiplication bonus is not good enough. I think the no multiplication answer is much more interesting, but this is code golf, so it's not the best. Here's an answer without `*`, and a better (shorter, and better scoring) answer with it:

90 chars, no power operators, uses multiplication = 90

``````Sub c(x,y)
f=IIf(y,x,1):For l=2 To y:b=x:For j=2 To f:b=b*x:Next:f=b:Next:MsgBox f
End Sub
``````

116 chars, no power operators, no multiplication bonus (-5) = 111

``````Sub c(x,y)
f=IIf(y,x,1):For l=2 To y:b=x:For j=2 To f:For i=1 To x:a=a+b:Next:b=a:a=0:Next:f=b:Next:MsgBox f
End Sub
``````

NOTE: VBA has issues printing the number when the result is very large (i.e. `4, 3`), but it does calculate correctly, so if, for example, you wanted to USE that number, you would be good to go. Also, even BIGGER numbers overflow (i.e. `3, 4`).

-

Javascript: 116 chars

``````function t(i){y=i.split(' ');a=y[0];b=y[1];return+b&&p(a,t(a+' '+(b-1)))||1}function p(a,b){return+b&&a*p(a,b-1)||1}
``````

t('4 3') Outputs:

``````1.3407807929942597e+154
``````
-

Factor, 187 characters

``````USING: eval io kernel locals math prettyprint sequences ;
IN: g
:: c ( y x o! -- v )
o 0 = [ x y * ] [ o 1 - o!
y x <repetition> 1 [ o c ] reduce ] if ;
contents eval( -- x y ) swap 2 c .
``````

Before golf:

``````USING: eval io kernel locals math prettyprint sequences ;
IN: script

! Calculate by opcode:
!   0 => x * y, multiplication
!   1 => x ^ y, exponentiation
!   2 => x ^^ y, tetration
:: calculate ( y x opcode! -- value )
opcode 0 = [
x y *
] [
! Decrement the opcode. Tetration is repeated exponentiation,
! and exponentiation is repeated multiplication.
opcode 1 - opcode!

! Do right-associative reduction. The pattern is
!   seq reverse 1 [ swap ^ ] reduce
! but a repetition equals its own reverse, and 'calculate'
y x <repetition> 1 [ opcode calculate ] reduce
] if ;

contents eval( -- x y )         ! Read input.
swap 2 calculate .              ! Calculate tetration. Print result.
``````

I did not remove the multiplication operator `*`. If I did so, then I would need to add some logic expressing that the sum of an empty sequence is 0, not 1. This extra logic would cost more than the -5 bonus.

Rule breaker, 124 + 10 = 134 characters

``````USING: eval kernel math.functions prettyprint sequences ;
contents eval( -- x y ) swap <repetition> 1 [ swap ^ ] reduce .
``````

This program has a lower score, but the exponentiation operator `^` breaks the rules. The rules say "(# of characters) + (10 * (# of 'power' operators))", so I applied the +10 penalty. However, the rules also say "Don't use the 'power' operator", so any program taking this penalty does break the rules. Therefore, this program of 134 characters is not a correct answer, and I must present my longer program of 187 characters as my answer.

-

Clojure - 122 + 10 = 132 Points

``````(def v(read))(prn((fn h[x,y,z](if(= y 0)1(if(= y 1)z(h x(- y 1)((fn p[n m](if(= m 1)n(*'(p n(- m 1))n)))x z)))))v(read)v))
``````

Definitely not the shortest as I rewrote the power function using multiplication. But, still, a fun, entirely recursive, example.

Run it as a script, not through REPL.

-

Python (111) (113) no *

``````r=lambda x,y:(x for _ in range(y));t=lambda x,y:reduce(lambda y,x:reduce(lambda x,y:sum(r(x,y)),r(x,y)),r(x,y),1)
``````

6***3 - 36k digits))

Upd: Have to add initial value, to fit t(X,0)=1

-
 Impressive, how long did the 36k take? – MrZander Aug 17 '12 at 17:56 9.375 seconds including print. – Ev_genus Aug 17 '12 at 21:28

Ruby, 47 46 45

`t=->x,n{r=x;2.upto(n){r=([x]*r).inject :*};r}`

-

Haskell 110 - 5 = 105

Tetration Peano Style. This is the most insanely slow solution possible, just a warning, but also avoids even addition.

``````data N=Z|S N
a&+Z=a
a&+S b=S\$a&+b
_&*Z=Z
a&*S b=a&+(a&*b)
_&^Z=S Z
a&^S b=a&*(a&^b)
_&>Z=S Z
a&>S b=a&^(a&>b)
``````

This relies on you having the patience to type out Peano numbers (and won't show the answer, If you actually want to run it, add these few lines (90 chars):

``````f 0=Z
f a=S\$f\$a-1
t Z=0
t(S a)=1+t a
``````
-

Mathematica, 40 33

This doesn't quite conform to the rules but it is not in contention for the shortest code anyway, and I hope that it will be of interest to someone.

``````m@f_:=Fold[f,1,#2~Table~{#}]&;

m[m@Sum]
``````

This builds a "tetration" function when it is run, but the arguments must be given in reverse order. Example:

``````m[m@Sum][3, 4]
``````

1340780792994259709957402499820584612747936582059239337772356144372176 4030073546976801874298166903427690031858186486050853753882811946569946 433649006084096

-
 Would you explain the code? Or display results on symbols rather than numbers? I notice that `Fold[g, 1, #2~Table~{#}] &[3, 4]` will produce `g[g[g[1, 4], 4], 4]` for instance. – David Carraher Aug 9 '12 at 10:27 @David `m[Times]` produces `Fold[Times, 1, Table[#2, {#1}]] &`, which is a power function: `m[Times][5, x]` ---> `x^5`; the same method is used for this new power function to produce a tetration function. Logically one could start with `Plus` but that fails almost immediately. – Mr.Wizard Aug 9 '12 at 10:37 To eliminate Times, try this: `t[h_, n_] := Sum[h, {i, n}]`. Then run `m[m@t][3, 4]`. – David Carraher Aug 9 '12 at 10:46 @David, yes, that should work, but not for Code-Golf. ;-) (BTW you could write `Sum[h, n]`.) – Mr.Wizard Aug 9 '12 at 10:47 Look at the scoring rules. You save 9 points by not using Times. The total score is still not better than yours but getting closer. – David Carraher Aug 9 '12 at 10:48

Haskell:  58  51 chars, with or without multiplication.

``````i f x 1=x;i f x n=f\$i f x\$n-1
t=i(\o n->i(o n)n)(+)4
``````

Ungolfed:

``````bump op n a = iterate (op n) n !! (fromIntegral \$ a-1)
tetrate = iterate bump (+) !! 3
``````

Shorter definition comes from inlining “bump”, and defining a custom version of “iterate”. Unfortunately the result is impossibly inefficient, but starting with (*) instead of (+) gives decent speed. In `ghci`:

``````Prelude> let i f x 1=x;i f x n=f\$i f x\$n-1
(0.00 secs, 1564024 bytes)
Prelude> let t=i(\o n->i(o n)n)(*)3
(0.00 secs, 1076200 bytes)
Prelude> t 4 3
13407807929942597099574024998205846127479365820592393377723561443721764030073546
976801874298166903427690031858186486050853753882811946569946433649006084096
(0.01 secs, 1081720 bytes)
``````
-

J, score is 7 (12 chars - 5 points for avoiding multiplication)

`+/@\$/@\$~/@\$~`

usage:

``````   4 +/@\$/@\$~/@\$~ 3
1.34078e154
t=.+/@\$/@\$~/@\$~  NB. define a function
4 t 3
1.34078e154
2 t 2
4
``````

Just few nested folds:

• Using multiplication it would be `*/@\$~/@\$~`
• Using power it would be `^/@\$~` where `\$~` creates array, `/` is a fold function.
-
Nicely done. (pad) – Gareth Aug 15 '12 at 10:20
@Gareth Thanks, but was does `pad` mean here? Sorry, English is not my mother tongue. – Artem Ice Aug 15 '12 at 10:25
My message was too short so I needed to pad it out. :-) – Gareth Aug 15 '12 at 10:30

Common Lisp 85 chars

``````(lambda(b c)(let((r b)u)(dotimes(c c r)(setf u 1 r(dotimes(c b u)(setf u(* u r)))))))
``````

I tried doing the multiplications through repeated addition, but it was way more than 5 characters. Same thing with macrolets, the declarations were not worth the gains.

Another solution, inspired by boothby's python solution. It's 1 character less than the above solution.

``````(lambda(a b)(eval`(*,@(loop for x below b nconc(loop for x below a nconc`(,a,a))))))
``````
-

Python, 64

Using some of boothby's ideas.

``````a,b=map(int,raw_input().split())
r=1;exec"r=eval('a*'*r+'1');"*b
``````

The result is stored in `r`.

-