Implement hyperexponentiation/tetration without the use of '^'

28

5

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)
  • 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

MrZander

Posted 2012-04-19T07:17:34.313

Reputation: 871

4One 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 – 2012-04-19T08:38:41.453

@PeterTaylor Thanks, updated. – MrZander – 2012-04-19T21:12:26.413

3Also worth adding a test for the edge case x 0 => 1. My original solution didn't handle that case. – Peter Taylor – 2012-04-19T21:20:37.137

Thanks, added that as well. I also added that speed is not a requirement. – MrZander – 2012-04-19T21:21:53.517

3The 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 – 2012-04-20T03:32:11.233

@userunknown It seemed to help out other people. Peter Taylor, for example. It was just another incentive, for fun. – MrZander – 2012-04-20T05:20:46.883

1What does "at least 4 3" mean exactly? My C solution computes 4 3 nicely, but is inaccurate for many smaller numbers (which are not powers of 2). – ugoren – 2012-04-20T12:16:05.747

1@ugoren you need to be able to compute numbers lower than that accurately. – MrZander – 2012-04-20T17:20:15.027

1

Basically this without exponentiation.

– Engineer Toast – 2017-09-19T12:20:21.920

2@EngineerToast I posted this golf 4 years before the one you linked... – MrZander – 2017-09-19T23:13:40.183

@MrZander HA! Good point. I failed to note either timestamp. My apologies. – Engineer Toast – 2017-09-20T12:03:02.127

2The conditions and scoring are kind of strange. You don't allow the use of power operations? Or you do allow them, but they are a +10 point bonus? – Simply Beautiful Art – 2017-12-04T23:58:20.447

1@SimplyBeautifulArt The scoring was meant as a deterrent, this is a code golf. Meaning, if you used a power operator, it would be worth 10 points towards your golf score, of which you want to be low. But yeah, I can see how it's unclear. This was posted a long time ago haha. I'll update it. – MrZander – 2017-12-05T00:03:04.353

1The strange thing is that it's kinda hard for me to implement exponentiation in less than 10 bytes in Ruby, so it was actually worth the 10 point price. – Simply Beautiful Art – 2017-12-05T00:03:58.370

1@SimplyBeautifulArt The original goal of the question was to not use the power operator, so I have made that the "rule". Thanks for pointing it out. – MrZander – 2017-12-05T00:06:14.143

Answers

16

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.

defhlt

Posted 2012-04-19T07:17:34.313

Reputation: 1 717

Nicely done. (pad) – Gareth – 2012-08-15T10:20:16.733

@Gareth Thanks, but was does pad mean here? Sorry, English is not my mother tongue. – defhlt – 2012-08-15T10:25:59.357

5My message was too short so I needed to pad it out. :-) – Gareth – 2012-08-15T10:30:24.040

Could you get pentation just by providing one more @$~ in the conjunction? – Jonah – 2017-09-19T23:03:08.210

@Jonah You'd need the /, but yes. you're just folding as many times as needed over the nested folding function. – HyperNeutrino – 2017-10-22T20:44:10.473

15

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

ceased to turn counterclockwis

Posted 2012-04-19T07:17:34.313

Reputation: 5 200

1I trust you will have an answer for me by 3012? ;) – MrZander – 2012-04-19T21:26:17.533

6I'll need some help from Moore's law, but that given I might. – ceased to turn counterclockwis – 2012-04-19T22:00:14.513

12

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.

~])*{[]+*{*}*}*

Ilmari Karonen

Posted 2012-04-19T07:17:34.313

Reputation: 19 513

This produces fatal errors, e.g. with "2 3" ~])*{[]+*{*}*}*. – r.e.s. – 2012-04-20T03:37:54.233

@r.e.s., it produces the correct answer for me. – Peter Taylor – 2012-04-20T06:29:28.937

@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 – 2012-04-20T10:40:24.947

(+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. – 2012-04-20T13:18:16.667

1ideone.com/547LG – r.e.s. – 2012-04-20T16:01:27.323

Unfortunately, this script leaves an empty stack (instead of the required output 1) when the second input number is 0; i.e., x 0 --> empty. – r.e.s. – 2012-04-21T02:48:46.957

@r.e.s.: Thanks for spotting that. Looks like I need to spend three extra chars to fix it. :( – Ilmari Karonen – 2012-04-21T06:58:24.507

10

J, 16 19 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 2s 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

Gareth

Posted 2012-04-19T07:17:34.313

Reputation: 11 678

Could you provide an explanation? This looks interesting. – MrZander – 2012-04-19T21:23:01.127

@MrZander I've edited my answer to add an explanation. – Gareth – 2012-04-19T21:48:55.477

Not sure if I have a better understanding or more confusion, but thanks haha. – MrZander – 2012-04-19T21:50:43.493

The explanation implies that the whole thing is doing exponentiation rather than tetration. Which of us is missing something? – Peter Taylor – 2012-04-19T22:28:45.663

@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 – 2012-04-20T07:24:05.297

Unfortunately, this script does not produce the correct output (1) when the second input number is 0; e.g., 1 0 --> domain error ... – r.e.s. – 2012-04-21T02:58:49.580

@r.e.s. Hmmm...I'm not sure how I'll meet that criterion... - in my defence, the case x 0 = 1 wasn't actually in the question when I posted my answer. – Gareth – 2012-04-21T10:40:41.983

@r.e.s. Ok, found a fix at a cost of 3 characters. – Gareth – 2012-04-21T10:54:35.193

In what way is ]$[ different from $ or ~$? – FUZxxl – 2012-04-23T12:14:31.497

@FUZxxl That's a very good point. Can't see the wood for the trees sometimes. :-) – Gareth – 2012-04-23T12:43:09.563

@Gareth, I can't understand how come that ^/4$3 runs out of memory, but your solution doesn't – defhlt – 2012-08-15T08:55:37.257

@ArtemIce My solution will turn 4 3 into a list of 256 4s and then multiply them. Adding an extra iteration to get rid of the * and use + instead will generate a list of 4s so long that it won't fit into memory. – Gareth – 2012-08-15T09:15:01.573

@Gareth oh, I should be using ^/4$~3 instead! Now I've come up with an answer http://codegolf.stackexchange.com/a/6992/4878

– defhlt – 2012-08-15T10:07:48.930

8

GolfScript (24 chars - 5 = 19 points)

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

is insanely slow.

(or 20 chars)

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

is much faster.

Peter Taylor

Posted 2012-04-19T07:17:34.313

Reputation: 41 901

2

Since GolfScript is a Ruby program, we can test on ideone :) http://ideone.com/GTIfP. I've also emailed ideone suggesting they add support for GolfScript.

– mellamokb – 2012-04-19T16:44:58.657

@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 – 2012-04-19T21:18:28.483

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 – 2012-04-19T21:26:26.833

+1 http://ideone.com/eW2F3 :)

– mellamokb – 2012-04-20T13:36:08.620

6

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

boothby

Posted 2012-04-19T07:17:34.313

Reputation: 9 038

If we assume the arguments are comma sepearated, you could use input() or use eval(raw_input()) Cheers – st0le – 2012-04-23T15:00:49.173

1@st0le, please read the question – boothby – 2012-06-22T07:47:30.187

Nice one. The second line can be golfed even more: exec"eval('a*'*"*b+'1'+"+'1')"*b – flornquake – 2013-05-13T23:42:36.167

@flornquake good catch! thanks! – boothby – 2013-05-14T01:48:49.310

4

Br**nfuck, 128-5=123 bytes

+<<+<<,<,[>[>+>>+<<<-]>[<+>-]>[>[>>+>+<<<-]>>>[<<<+>>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>[-]>[<<+>>-]<<<<-]>>[<<+>>-]+<[-]<<<<-]>>>.

Input is in the form of characters with code points of the numbers desired as inputs. Output is the same.

An explanation is coming when I have the time below. Do I get bonus points for not using exponentiation, multiplication, OR even addition?

Cell 3 (0-indexed) is the running total x.
This calculates the nth tetration of a.

+<<+<<,<,                                       Initialize tape with [n, a, 0, 1, 0, 1]
[                                               While n:
  >[>+>>+<<<-]>[<+>-]                             Copy a 3 cells to right: [n, a, 0, x, a, 1]
  >[                                              While x:
    >[>>+>+<<<-]>>>[<<<+>>>-]                       Copy a 2 cells to right: [n, a, 0, x, a, 1, a, 0]
    <<[>[>+>+<<-]>>[<<+>>-]<<<-]                    Cell 7 = prod(cell 5, cell 6)
    >[-]>[<<+>>-]<<<<-]                             Move this value to cell 5. End while.
  >>[<<+>>-]+<[-]<<<<-]                           Update x to result of exponentiation. End while.
>>>.                                            Print the result!

This works (tested) for x 0, 0 x, x 1, 1 x, x 2, 2 3, and 2 4. I tried 3 3, but it ran for several hours without finishing (in my Java implementation—probably not optimal) (EDIT: in @Timwi's EsotericIDE [It's great! Y'all should try it] as well. No luck.). In theory, this works up to the cell size of the specific implementation.

Khuldraeseth na'Barya

Posted 2012-04-19T07:17:34.313

Reputation: 2 608

1"Br**nfuck" Yes "brain" is a very offensive word xD. sorry I needed to – FireCubez – 2018-11-15T22:45:38.097

4

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.

user unknown

Posted 2012-04-19T07:17:34.313

Reputation: 4 210

3

Ruby 66 59 characters

def e(x,y)
r=1
(1..y).each{t=x
(2..r).each{t*=x}
r=t}
r
end

Cristian Lupascu

Posted 2012-04-19T07:17:34.313

Reputation: 8 369

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. – 2012-04-21T03:09:47.897

@r.e.s. you are right. I fixed the code. Thanks! – Cristian Lupascu – 2012-04-21T07:31:49.693

3

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)

Blazer

Posted 2012-04-19T07:17:34.313

Reputation: 1 902

1Is multiplication by iterated addition really fast enough to evaluate 4***3?! – Peter Taylor – 2012-04-19T14:38:55.340

2@PeterTaylor yes? it completes in less than a second for me – Blazer – 2012-04-19T17:28:47.223

Wow. The equivalent GolfScript version takes aaaaaaages. – Peter Taylor – 2012-04-19T21:24:05.933

As in, I've left it running overnight and it still hasn't finished. – Peter Taylor – 2012-04-20T06:26:01.110

@PeterTaylor: Have you tried 3***3? I interrupted my Scala program after a few minutes. – user unknown – 2012-04-20T08:32:43.900

Since efficiency is not a criterion, you can reduce the score to 147-5=142 (this doesn't display properly in a comment, but you should get the idea): r=range def f(k,x,y): i=0 if k==1: for n in r(y):i+=x if k==2: i+=1 for n in r(y):i=f(1,i,x) if k==3: i+=1 for n in r(y):i=f(2,x,i) return i. Invoke: f(3,x,y). (In some browsers, you can view the comment with properly displayed code by using View Source. Or, in Chrome, right-click and Inspect Element.) – r.e.s. – 2012-04-21T10:13:02.767

1Six years later, you can also save some bytes by replacing your m function with m=lambda x,y:sum(x for _ in r(y)) – Jack Brounstein – 2018-06-29T16:11:56.597

3

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)

ardnew

Posted 2012-04-19T07:17:34.313

Reputation: 2 177

4an incorrect one too – ardnew – 2012-04-19T16:19:00.127

3

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

Mr.Wizard

Posted 2012-04-19T07:17:34.313

Reputation: 2 481

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. – DavidC – 2012-08-09T10:27:50.220

@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 – 2012-08-09T10:37:03.813

To eliminate Times, try this: t[h_, n_] := Sum[h, {i, n}]. Then run m[m@t][3, 4]. – DavidC – 2012-08-09T10:46:37.403

@David, yes, that should work, but not for Code-Golf. ;-) (BTW you could write Sum[h, n].) – Mr.Wizard – 2012-08-09T10:47:44.767

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. – DavidC – 2012-08-09T10:48:52.783

The question says -5 points, but with that I'm down to 33. Thanks, @David! – Mr.Wizard – 2012-08-09T10:57:16.907

I get the following error message with your 33 char code: Table::iterb: Iterator {Underscript[\[Sum], 4]1} does not have appropriate bounds. >> – DavidC – 2012-08-09T12:03:10.397

@David please ping me in Mathematica Chat when you read this. – Mr.Wizard – 2012-08-10T07:22:08.713

3

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)

PLL

Posted 2012-04-19T07:17:34.313

Reputation: 139

2

Perl 6, 32 bytes

->\a,\b{(1,{[*] a xx$_}...*)[b]}

Try it online!

(1, { [*] a xx $_ } ... *) is a lazy sequence that generates the power tower, each element being the a list which consists of the first input parameter a replicated (xx) a number of times equal to the previous element ($_), that list then being reduced with multiplication ([*]). From that sequence we simply pluck out the b-th element.

Sean

Posted 2012-04-19T07:17:34.313

Reputation: 4 136

2

Lambda calculus, 10-5

(using Church encoding and De Bruijn indeces)
λλ(1λ13)λ1

Explanation

Without De Bruijn indeces: λa,b.(b λc.ca)λc.c:

λa,b.                                                 define the anonymous function f(a,b)=
     (b                                                apply the following function b times
        λc.                                                    the anonymous function g(c)=
           ca)                 apply c to a because of church encoding this is equal to a^c
              λc.c                              the identity function, 1 in church encoding

If you define exp_a(x)=a^x this program defines a↑↑b=exp_a^b(1) where ^b denotes function itteration.

I'm not sure if this is allowed because ca is technically equivalent to a^c how ever it is not a real built-in and only a side effect of the way integers are encoded in lambda calculus.

fejfo

Posted 2012-04-19T07:17:34.313

Reputation: 359

Hm, is there an interpreter so that I can try this? If there's no implementation of a language, then you can't use it to solve challenges here. Languages are based on their implementations here. – Erik the Outgolfer – 2019-03-09T19:56:57.023

2

Lua: 133 chars, multiplication-less

a,b=io.read():match"(%d+) (%d+)"a,b,ba=a+0,b+0,a for i=1,b-1 do o=1 for i=1,a do o=o+o for i=1,ba-b do o=o+o end end a=o end print(o)

I was originally going to use string repetition hacks to do fake multiplication, but it likes to fail on large values. I could possibly use dynamic compilation and loadstring to make it smaller, but it's getting late here... I need sleep.

Entering "4 3" into stdin outputs:

1.3407807929943e+154

Dwayne Slater

Posted 2012-04-19T07:17:34.313

Reputation: 111

2

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)

ugoren

Posted 2012-04-19T07:17:34.313

Reputation: 16 527

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 – 2012-04-20T08:29:41.330

@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 – 2012-04-20T12:10:29.153

2

C, 117 105 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());
}

ugoren

Posted 2012-04-19T07:17:34.313

Reputation: 16 527

Looks like 118 chars to me: http://ideone.com/9D5SU

– mellamokb – 2012-04-19T16:28:56.963

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 – 2012-04-19T19:40:30.023

@Sir_Lagsalot, double has more than enough precision for 4^256. It only has one significant digit. – ugoren – 2012-04-19T20:03:12.350

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 – 2012-04-19T20:15:44.410

@Sir_Lagsalot: See the ideone link I provided. It prints out the whole number. – mellamokb – 2012-04-19T21:03:05.723

@Sir_Lagsalot, I tested gcc/Linux, it prints it all. Maybe the format string %lf isn't handled the same way on your system. – ugoren – 2012-04-20T12:19:27.350

2

VBA, 90 Chars

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

Gaffi

Posted 2012-04-19T07:17:34.313

Reputation: 3 411

2

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'
        ! already swaps its inputs.
        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.

kernigh

Posted 2012-04-19T07:17:34.313

Reputation: 2 615

2

Ruby, 47 46 45

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

defhlt

Posted 2012-04-19T07:17:34.313

Reputation: 1 717

2

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
main=interact$show.f.(\[x,y]->x&>y).map(f.read).words

walpen

Posted 2012-04-19T07:17:34.313

Reputation: 3 237

1

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

Erik Haliewicz

Posted 2012-04-19T07:17:34.313

Reputation: 401

1

Python 3 – 68

(including the 10-point penalty for the power operator)

a,b=input().split()
r=1
exec("r=%s**r;"%a*int(b))
print(r)

flornquake

Posted 2012-04-19T07:17:34.313

Reputation: 1 467

1

Ruby, 43 39 points

->a,b{c=1;eval"c=eval('a*'*~-c+?a);"*b}

Try it online

Ruby, also 43 39 points

t=->a,b{b<1?1:eval("a*"*~-t[a,b-1]+?a)}

Try it online


The following are no longer valid(?)

Ruby, 26 + (1 power operation)*10 points

t=->a,b{b<1?1:a**t[a,b-1]}

Try it online

Ruby, 28 + (1 power operation)*10 points

->a,b{c=1;b.times{c=a**c};c}

Try it online

Simply Beautiful Art

Posted 2012-04-19T07:17:34.313

Reputation: 2 140

1

Yabasic, 71 bytes

A function that takes input a and b as a space delimited string.

Input""a,b
d=a^(b>0)
For i=2To b
c=a
For j=2To d
c=c*a
Next
d=c
Next
?d

Try it online!

Taylor Scott

Posted 2012-04-19T07:17:34.313

Reputation: 6 709

1

Rockstar, 233 bytes

Rockstar is a quite new computer programming language, designed for creating programs that are also song lyrics. Rockstar is heavily influenced by the lyrical conventions of 1980s hard rock and power ballads.

The solution takes two inputs, one per each line (string manipulation is very limited). It uses multiplication operator, so no bonus to apply for :/

P takes A,B
N is 1
C is 1
While C is as low as B
Let N be N of A
Build C up

Give back N

T takes E,F
If F is empty
Give back 1
Else
Knock F down
Let G be T taking E,F
Give back P taking E,G


Listen to X
Listen to Y
Say T taking X,Y

Ungolfed, here's a more lyric version (comments are in parentheses, which are standard comments in Rockstar). Variable names may take up more words, and all words count ('my power' is different from 'the power' and from 'Power')

Power takes the force and the cross          (function def, two parameters: 'the force', 'the cross')
  Build my arm up                            ('my arm' := 1) (literally: 'my arm'++, but my arm was initialized with 0)
  Build my faith up                          ('my faith' := 1)
  While my faith is as weak as the cross     (While loop, condition: 'my faith' <= 'the cross')
    Let my arm be the force of my arm        ('my arm' := 'the force' * 'my arm' )
    Build my faith up                        ('my faith' ++ )
                                             (empty line to terminate While block)
  Give back my arm                           (return 'my arm')
                                             (empty line to terminate function block)
Tower takes the force and the enemy          (function def, two parameters: 'the force', 'the enemy')
  If the enemy is nowhere                    (If, condition: 'the enemy' == 0) (literally: 'the enemy' == NULL, but NULL is considered 0 in arithmetics)
    Build Victory up                         (Victory := 1, this is a bit diffeerent from the golfed version)
    Give back Victory                        (return Victory)
  Else                                       (else)
    Knock the enemy down                     ('the enemy' -- )
    Let the defense be Tower taking the force and the enemy ('the defense' := Tower ('the force', 'the enemy'))
    Give back Power taking the force and the defense        (return Power ('the force', 'the defense'))
                                             (empty line to terminate If block)
                                             (empty line to terminate Function block)
Listen to us                                 (input: 'us')
Listen to your enemy                         (input: 'your enemy')
Scream Tower taking us and your enemy        (output: Tower('us', 'your enemy'))

gaborsch

Posted 2012-04-19T07:17:34.313

Reputation: 249

1

R, 71 - 5 = 66 bytes

function(x,y,b=x){for(i in 2:y)b=cumprod(z<-rep(x,b))[sum(z|1)];cat(b)}

Try it online!

-5 for avoiding *, which was harder than I expected. It explodes really fast and won't work (unless it had more memory) but it satisfies all necessary criteria.

Sumner18

Posted 2012-04-19T07:17:34.313

Reputation: 1 334

1

PHP, 139 125 bytes

function f($x,$y){return gmp_strval($y?(function($x,$y){for($a=1;$i<$y;$i++)$a=gmp_mul($x,$a);return$a;})($x,f($x,$y-1)):1);}

Uses GMP library for the arbitrary-length math. It does compute the result instantly and able to solve 2***5 as well.

The longer (198 bytes - 5 = 193) version that does not multiply:

function f($x,$y){return gmp_strval($y?(function($x,$y,$a=1){for(;$i<$y;$i++)$a=(function($x,$y){$a=0;for(;$i<gmp_intval($y);$i++)$a=gmp_add($x,$a);return$a;})($x,$a);return$a;})($x,f($x,$y-1)):1);}

Output Tests:

2, 0 -> 1
Exec time 0.00009513 seconds
2, 2 -> 4
Exec time 0.00006819 seconds
2, 4 -> 65536
Exec time 0.00002694 seconds
4, 3 -> 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
Exec time 0.00011992 seconds

If you were curious the result of 2***5, here it is:

2, 5 -> 2003529930406846464979072351560255750447825475569751419265016973710894059556311453089506130880933348101038234342907263181822949382118812668869506364761547029165041871916351587966347219442930927982084309104855990570159318959639524863372367203002916969592156108764948889254090805911457037675208500206671563702366126359747144807111774815880914135742720967190151836282560618091458852699826141425030123391108273603843767876449043205960379124490905707560314035076162562476031863793126484703743782954975613770981604614413308692118102485959152380195331030292162800160568670105651646750568038741529463842244845292537361442533614373729088303794601274724958414864915930647252015155693922628180691650796381064132275307267143998158508811292628901134237782705567421080070065283963322155077831214288551675554073345107213112427399562982719769150054883905223804357045848197956393157853510018992000024141963706813559840464039472194016069517690156119726982337890017641517190051133466306898140219383481435426387306539552969691388024158161859561100640362119796101859534802787167200122604642492385111393400464351623867567078745259464670903886547743483217897012764455529409092021959585751622973333576159552394885297579954028471943529913543763705986928913757153740001986394332464890052543106629669165243419174691389632476560289415199775477703138064781342309596190960654591300890188887588084733625956065444888501447335706058817090162108499714529568344061979690565469813631162053579369791403236328496233046421066136200220175787851857409162050489711781820400187282939943446186224328009837323764931814789848119452713007440220765680910376203999203492023906626264491909167985461515778839060397720759279378852241294301017458086862263369284725851403039615558564330385450688652213114813638408384778263790459607186876728509763471271988890680478243230394718650525660978150729861141430305816927924971409161059417185352275887504477592218301158780701975535722241400019548102005661773589781499532325208589753463547007786690406429016763808161740550405117670093673202804549339027992491867306539931640720492238474815280619166900933805732120816350707634351669869625020969023162859350071874190579161241536897514808261904847946571736601005892476655445840838334790544144817684255327207315586349347605137419779525190365032198020108764738368682531025183377533908861426184800374008082238104076468878471647552945326947661700424461063311238021134588694532200116564076327023074292426051582811070387018345324567635625951430032037432740780879056283663406965030844225855967039271869461158513793386475699748568670079823960604393478850861649260304945061743412365828352144806726676841807083754862211408236579802961200027441324438432402331257403545019352428776430880232850855886089962774458164680857875115807014743763867976955049991643998284357290415378143438847303484261903388841494031366139854257635577105335580206622185577060082551288893332226436281984838613239570676191409638533832374343758830859233722284644287996245605476932428998432652677378373173288063210753211238680604674708428051166488709084770291208161104912555598322366244868556651402684641209694982590565519216188104341226838996283071654868525536914850299539675503954938371853405900096187489473992880432496373165753803673586710175783994818471798498246948060532081996066183434012476096639519778021441199752546704080608499344178256285092726523709898651539462193004607364507926212975917698293892367015170992091531567814439791248475706237804600009918293321306880570046591458387208088016887445835557926258465124763087148566313528934166117490617526671492672176128330845273936469244582892571388877839056300482483799839692029222215486145902373478222682521639957440801727144146179559226175083889020074169926238300282286249284182671243405751424188569994272331606998712986882771820617214453142574944015066139463169197629181506579745526236191224848063890033669074365989226349564114665503062965960199720636202603521917776740668777463549375318899587866282125469797102065747232721372918144666659421872003474508942830911535189271114287108376159222380276605327823351661555149369375778466670145717971901227117812780450240026384758788339396817962950690798817121690686929538248529830023476068454114178139110648560236549754227497231007615131870024053910510913817843721791422528587432098524957878034683703337818421444017138688124249984418618129271198533315382567321870421530631197748535214670955334626336610864667332292409879849256691109516143618601548909740241913509623043612196128165950518666022030715613684732364660868905014263913906515063908199378852318365059897299125404479443425166774299659811849233151555272883274028352688442408752811283289980625912673699546247341543333500147231430612750390307397135252069338173843322950701049061867539433130784798015655130384758155685236218010419650255596181934986315913233036096461905990236112681196023441843363334594927631946101716652913823717182394299216272538461776065694542297877071383198817036964588689811863210976900355735884624464835706291453052757101278872027965364479724025405448132748391794128826423835171949197209797145936887537198729130831738033911016128547415377377715951728084111627597186384924222802373441925469991983672192131287035585307966942713416391033882754318613643490100943197409047331014476299861725424423355612237435715825933382804986243892498222780715951762757847109475119033482241412025182688713728193104253478196128440176479531505057110722974314569915223451643121848657575786528197564843508958384722923534559464521215831657751471298708225909292655638836651120681943836904116252668710044560243704200663709001941185557160472044643696932850060046928140507119069261393993902735534545567470314903886022024639948260501762431969305640666366626090207048887438898907498152865444381862917382901051820869936382661868303915273264581286782806601337500096593364625146091723180312930347877421234679118454791311109897794648216922505629399956793483801699157439700537542134485874586856047286751065423341893839099110586465595113646061055156838541217459801807133163612573079611168343863767667307354583494789788316330129240800836356825939157113130978030516441716682518346573675934198084958947940983292500086389778563494693212473426103062713745077286156922596628573857905533240641849018451328284632709269753830867308409142247659474439973348130810986399417379789657010687026734161967196591599588537834822988270125605842365589539690306474965584147981310997157542043256395776070485100881578291408250777738559790129129407309462785944505859412273194812753225152324801503466519048228961406646890305102510916237770448486230229488966711380555607956620732449373374027836767300203011615227008921843515652121379215748206859356920790214502277133099987729459596952817044582181956080965811702798062669891205061560742325686842271306295009864421853470810407128917646906550836129916694778023822502789667843489199409657361704586786242554006942516693979292624714524945408858422726153755260071904336329196375777502176005195800693847635789586878489536872122898557806826518192703632099480155874455575175312736471421295536494084385586615208012115079075068553344489258693283859653013272046970694571546959353658571788894862333292465202735853188533370948455403336565356988172582528918056635488363743793348411845580168331827676834646291995605513470039147876808640322629616641560667508153710646723108461964247537490553744805318226002710216400980584497526023035640038083472053149941172965736785066421400842696497103241919182121213206939769143923368374709228267738708132236680086924703491586840991153098315412063566123187504305467536983230827966457417620806593177265685841681837966106144963432544111706941700222657817358351259821080769101961052229263879745049019254311900620561906577452416191913187533984049343976823310298465893318373015809592522829206820862230332585280119266496314441316442773003237792274712330696417149945532261035475145631290668854345426869788447742981777493710117614651624183616680254815296335308490849943006763654806102940094693750609845588558043970485914449584445079978497045583550685408745163316464118083123079704389849190506587586425810738422420591191941674182490452700288263983057950057341711487031187142834184499153456702915280104485145176055306971441761368582384102787659324662689978418319620312262421177391477208004883578333569204533935953254564897028558589735505751235129536540502842081022785248776603574246366673148680279486052445782673626230852978265057114624846595914210278122788941448163994973881884622768244851622051817076722169863265701654316919742651230041757329904473537672536845792754365412826553581858046840069367718605020070547247548400805530424951854495267247261347318174742180078574693465447136036975884118029408039616746946288540679172138601225419503819704538417268006398820656328792839582708510919958839448297775647152026132871089526163417707151642899487953564854553553148754978134009964854498635824847690590033116961303766127923464323129706628411307427046202032013368350385425360313636763575212604707425311209233402837482949453104727418969287275572027615272268283376741393425652653283068469997597097750005560889932685025049212884068274139881631540456490350775871680074055685724021758685439053228133770707415830756269628316955687424060527726485853050611356384851965918968649596335568216975437621430778665934730450164822432964891270709898076676625671517269062058815549666382573829274182082278960684488222983394816670984039024283514306813767253460126007269262969468672750794346190439996618979611928750519442356402644303271737341591281496056168353988188569484045342311424613559925272330064881627466723523751234311893442118885085079358163848994487544756331689213869675574302737953785262542329024881047181939037220666894702204258836895840939998453560948869946833852579675161882159410981624918741813364726965123980677561947912557957446471427868624053750576104204267149366084980238274680575982591331006919941904651906531171908926077949119217946407355129633864523035673345588033313197080365457184791550432654899559705862888286866606618021882248602144999973122164138170653480175510438406624412822803616648904257377640956326482825258407669045608439490325290526337532316509087681336614242398309530806549661879381949120033919489494065132398816642080088395554942237096734840072642705701165089075196155370186264797456381187856175457113400473810762763014953309735174180655479112660938034311378532532883533352024934365979129341284854970946826329075830193072665337782559314331110963848053940859283988907796210479847919686876539987477095912788727475874439806779824968278272200926449944559380414608770641941810440758269805688038949654616587983904660587645341810289907194293021774519976104495043196841503455514044820928933378657363052830619990077748726922998608279053171691876578860908941817057993404890218441559791092676862796597583952483926734883634745651687016166240642424241228961118010615682342539392180052483454723779219911228595914191877491793823340010078128326506710281781396029120914720100947878752551263372884222353869490067927664511634758101193875319657242121476038284774774571704578610417385747911301908583877890152334343013005282797038580359815182929600305682612091950943737325454171056383887047528950563961029843641360935641632589408137981511693338619797339821670761004607980096016024823096943043806956620123213650140549586250615282588033022908385812478469315720323233601899469437647726721879376826431828382603564520699468630216048874528424363593558622333506235945002890558581611275341783750455936126130852640828051213873177490200249552738734585956405160830583053770732533971552620444705429573538361113677523169972740292941674204423248113875075631319078272188864053374694213842169928862940479635305150560788126366206497231257579019598873041195626227343728900516561111094111745277965482790471250581999077498063821559376885546498822938985408291325129076478386322494781016753491693489288104203015610283386143827378160946341335383578340765314321417150655877547820252454780657301342277470616744241968952613164274104695474621483756288299771804186785084546965619150908695874251184435837306590951460980451247409411373899927822492983367796011015387096129749705566301637307202750734759922943792393824427421186158236161317886392553095117188421298508307238259729144142251579403883011359083331651858234967221259621812507058113759495525022747274674369887131926670769299199084467161228738858457584622726573330753735572823951616964175198675012681745429323738294143824814377139861906716657572945807804820559511881687188075212971832636442155336787751274766940790117057509819575084563565217389544179875074523854455200133572033332379895074393905312918212255259833790909463630202185353848854825062897715616963860712382771725621313460549401770413581731931763370136332252819127547191443450920711848838366818174263342949611870091503049165339464763717766439120798347494627397822171502090670190302469762151278521956142070806461631373236517853976292092025500288962012970141379640038055734949269073535145961208674796547733692958773628635660143767964038430796864138563447801328261284589184898528048048844180821639423974014362903481665458114454366460032490618763039502356402044530748210241366895196644221339200757479128683805175150634662569391937740283512075666260829890491877287833852178522792045771846965855278790447562192663992008409302075673925363735628390829817577902153202106409617373283598494066652141198183810884515459772895164572131897797907491941013148368544639616904607030107596818933741217575988165127000761262789169510406315857637534787420070222051070891257612361658026806815858499852631465878086616800733264676830206391697203064894405628195406190685242003053463156621891327309069687353181641094514288036605995220248248886711554429104721929134248346438705368508648749099178812670565665387191049721820042371492740164460943459845392536706132210616533085662021188968234005752675486101476993688738209584552211571923479686888160853631615862880150395949418529489227074410828207169303387818084936204018255222271010985653444817207470756019245915599431072949578197878590578940052540122867517142511184356437184053563024181225473266093302710397968091064939272722683035410467632591355279683837705019855234621222858410557119921731717969804339317707750755627056047831779844447637560254637033369247114220815519973691371975163241302748712199863404548248524570118553342675264715978310731245663429805221455494156252724028915333354349341217862037007260315279870771872491234494477147909520734761385425485311552773301030342476835865496093722324007154518129732692081058424090557725645803681462234493189708138897143299831347617799679712453782310703739151473878692119187566700319321281896803322696594459286210607438827416919465162267632540665070881071030394178860564893769816734159025925194611823642945652669372203155504700213598846292758012527715422016629954863130324912311029627923723899766416803497141226527931907636326136814145516376656559839788489381733082668779901962886932296597379951931621187215455287394170243669885593888793316744533363119541518404088283815193421234122820030950313341050704760159987985472529190665222479319715440331794836837373220821885773341623856441380700541913530245943913502554531886454796252260251762928374330465102361057583514550739443339610216229675461415781127197001738611494279501411253280621254775810512972088465263158094806633687670147310733540717710876615935856814098212967730759197382973441445256688770855324570888958320993823432102718224114763732791357568615421252849657903335093152776925505845644010552192644505312073756287744998163646332835816140330175813967359427327690448920361880386754955751806890058532927201493923500525845146706982628548257883267398735220457228239290207144822219885587102896991935873074277815159757620764023951243860202032596596250212578349957710085626386118233813318509014686577064010676278617583772772895892746039403930337271873850536912957126715066896688493880885142943609962012966759079225082275313812849851526902931700263136328942095797577959327635531162066753488651317323872438748063513314512644889967589828812925480076425186586490241111127301357197181381602583178506932244007998656635371544088454866393181708395735780799059730839094881804060935959190907473960904410150516321749681412100765719177483767355751000733616922386537429079457803200042337452807566153042929014495780629634138383551783599764708851349004856973697965238695845994595592090709058956891451141412684505462117945026611750166928260250950770778211950432617383223562437601776799362796099368975191394965033358507155418436456852616674243688920371037495328425927131610537834980740739158633817967658425258036737206469351248652238481341663808061505704829059890696451936440018597120425723007316410009916987524260377362177763430621616744884930810929901009517974541564251204822086714586849255132444266777127863728211331536224301091824391243380214046242223349153559516890816288487989988273630445372432174280215755777967021666317047969728172483392841015642274507271779269399929740308072770395013581545142494049026536105825409373114653104943382484379718606937214444600826798002471229489405761853892203425608302697052876621377373594394224114707074072902725461307358541745691419446487624357682397065703184168467540733466346293673983620004041400714054277632480132742202685393698869787607009590048684650626771363070979821006557285101306601010780633743344773073478653881742681230743766066643312775356466578603715192922768440458273283243808212841218776132042460464900801054731426749260826922155637405486241717031027919996942645620955619816454547662045022411449404749349832206807191352767986747813458203859570413466177937228534940031631599544093684089572533438702986717829770373332806801764639502090023941931499115009105276821119510999063166150311585582835582607179410052528583611369961303442790173811787412061288182062023263849861515656451230047792967563618345768105043341769543067538041113928553792529241347339481050532025708728186307291158911335942014761872664291564036371927602306283840650425441742335464549987055318726887926424102147363698625463747159744354943443899730051742525110877357886390946812096673428152585919924857640488055071329814299359911463239919113959926752576359007446572810191805841807342227734721397723218231771716916400108826112549093361186780575722391018186168549108500885272274374212086524852372456248697662245384819298671129452945515497030585919307198497105414181636968976131126744027009648667545934567059936995464500558921628047976365686133316563907395703272034389175415267500915011198856872708848195531676931681272892143031376818016445477367518353497857924276463354162433601125960252109501612264110346083465648235597934274056868849224458745493776752120324703803035491157544831295275891939893680876327685438769557694881422844311998595700727521393176837831770339130423060958999137314684569010422095161967070506420256733873446115655276175992727151877660010238944760539789516945708802728736225121076224091810066700883474737605156285533943565843756271241244457651663064085939507947550920463932245202535463634444791755661725962187199279186575490857852950012840229035061514937310107009446151011613712423761426722541732055959202782129325725947146417224977321316381845326555279604270541871496236585252458648933254145062642337885651464670604298564781968461593663288954299780722542264790400616019751975007460545150060291806638271497016110987951336633771378434416194053121445291855180136575558667615019373029691932076120009255065081583275508499340768797252369987023567931026804136745718956641431852679054717169962990363015545645090044802789055701968328313630718997699153166679208958768572290600915472919636381673596673959975710326015571920237348580521128117458610065152598883843114511894880552129145775699146577530041384717124577965048175856395072895337539755822087777506072339445587895905719156736
Exec time 0.11125493 seconds

640KB

Posted 2012-04-19T07:17:34.313

Reputation: 7 149

1

APL(NARS), chars 46, bytes 92

{⍺ ⍺{(a b)←⍺⋄⍵≤1:{⍵:b⋄1}⍵⋄(a,a{×/⍵⍴⍺}b)∇⍵-1}⍵}

test:

  h←{⍺ ⍺{(a b)←⍺⋄⍵≤1:{⍵:b⋄1}⍵⋄(a,a{×/⍵⍴⍺}b)∇⍵-1}⍵}
  3 h 0
1
  2 h 2
4
  2 h 4
65536
  4 h 3
1.340780793E154

without the use of pow=* in APL where ⍵>0; but i use multiplication ×...

RosLuP

Posted 2012-04-19T07:17:34.313

Reputation: 3 036

1

APL (Dyalog Classic), 23 bytes

f←{⍵=0:1⋄⊃⌽{×/⍵⍴⍺}\⍵⍴⍺}

Try it online!

RosLuP

Posted 2012-04-19T07:17:34.313

Reputation: 3 036

1

JavaScript (Node.js), 41 bytes

Have some BigInts

a=>g=b=>b--?(P=n=>n--?a*P(n):1n)(g(b)):1n

Try it online!

Shieru Asakoto

Posted 2012-04-19T07:17:34.313

Reputation: 4 445

1

JavaScript, 85 bytes

function(s){for(s=s.split(" "),a=b=s[0],i=0;++i<s[1];)for(j=a,a=b;--j;)a*=b;return a}

JavaScript (ES6), 83 bytes

r=f=>(i,n,j=i)=>--n?j:r(f)(i,n,f(i,j));s=>r(r((a,b)=>a*b),(s=s.split(" "))[0],s[1])

Naruyoko

Posted 2012-04-19T07:17:34.313

Reputation: 459

1

Haskell: 88-5 chars without multiplication, 59 chars with multiplication

Without multiplication:

h x y=foldr(\x y->foldl(\x y->foldl(+)0(replicate x y))1(replicate y x))1(replicate y x)

There are probably ways that I could golf that down a little.

With multiplication:

h x y=foldr(\x y->foldl(*)1(replicate y x))1(replicate y x)

And finally, the ungolfed program:

mult x y = foldl (+) 0 (replicate x y)
expo x y = foldl (mult) 1 (replicate y x)
h x y = foldr (expo) 1 (replicate y x)

This is probably the simplest way to do this problem, which is defining multiplication as repeated addition, exponentiation as repeated multiplication, and tetration as repeated exponentiation.

Aearnus

Posted 2012-04-19T07:17:34.313

Reputation: 251

1

Racket 58 (no *)

(define(t x y)(if(= y 0)1(for/product([i(t x(- y 1))])x)))

Matthew Butterick

Posted 2012-04-19T07:17:34.313

Reputation: 401

for/product is walking a fine line on the "no multiplication" rule, haha. – MrZander – 2014-09-18T16:17:27.360

1

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

Paul

Posted 2012-04-19T07:17:34.313

Reputation: 256

1

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

Ev_genus

Posted 2012-04-19T07:17:34.313

Reputation: 341

Impressive, how long did the 36k take? – MrZander – 2012-08-17T17:56:07.530

19.375 seconds including print. – Ev_genus – 2012-08-17T21:28:18.783