# Addition, multiplication, exponentiation and beyond¶

## The problem¶

When Alice was in school she noticed that multiplication is just repeated addition and exponentiation is just repeated multiplication. For example $x \times 5$ is $x+x+x+x+x$ and $x^5$ is $x \times x \times x \times x \times x$. "Can you go further?", she wondered to herself. Is there a repeated exponentiation? For example, $x \oplus 5$ could be defined as $$(((x^x)^x)^x)^x$$ (This is sometimes call the tower of powers function.) And can that be repeated so that $x \otimes 5 = (((x \oplus x) \oplus x) \oplus x) \oplus x$?

What if we call $+$ the first operator, $*$ the second, exponentation the third, and so on. Can we go on forever?

Let's define a function $superOp$ so that $superOp(x,y,1) = x+y$, $superOp(x,y,2) = x*y$, $superOp(x,y,3) = x^y$, $superOp(x,y,4) = x \oplus y$, etc.

### A Contract¶

We can use the following contract

def superOp( x, y, z )
"""
pre: y and z are integers with y >= 1 and z >= 1
post: If z is 1, the result is (...(x+x)+ ...)+x, with y xs.
And if z is 2, the result is (...(x*x)* ...)*x, with y xs
And if z is 3, the result (...(x to the x) to the ... ) to the x,  with y xs.
And if z is 4 or more the result is superOp( ... superOp( superOp(x, x, z-1), x, z-1) ..., x, z-1), with y xs.
"""


This is a strange looking contract, because it refers to the superOp function itself. However, because the third argument is smaller in the self referential case, this is ok.

## Problem analysis¶

The problem doesn't really need more analysis, since the contract is already in a recursive form.

## Design¶

### Some warm-up problems¶

Before writing the design or code for superOp, I found it useful to do some warm-up problems.

If you have trouble with any of the three warm-up problems, take a look at my solutions for them before attempting to code superOp.

### Multiplication recursively¶

Complete this function, using recursion. Use +, but not the * operator

In [28]:
def mult( x, y ) :
"""
pre: y is an integer, y >= 1
post: result == x * y
"""

In [29]:
mult( 4,5 ) # Should give 20


### Exponentiation¶

Complete this function using recursion. Use your mult function instead of the built in * operator.

In [30]:
def exp( x, y ) :

"""
pre: y is an integer, y >= 1
post: result == x to the power y
"""

In [31]:
exp( 3, 4 ) # Should give 81


### Super exponention¶

In [32]:
def tower( x, y ) :

"""
pre: y is an integer, y >= 1
post: result == ( ... ((x to the power x) to the power x) ... to the power x), with y x's
"""

In [33]:
tower( 2, 5 ) # Should give 256


### Design the superOp function¶

After that warm up, it shouldn't be too hard to write the superOp function described in the first section

In [34]:
def superOp( x, y, z ) :
"""
pre: y and z are integers with y >= 1 and z >= 1
post: If z is 1, the result is (...(x+x)+ ...)+x, with y xs.
And if z is 2, the result is (...(x*x)* ...)*x, with y xs
And if z is 3, the result (...(x to the x) to the ... ) to the x,  with y xs.
And if z is 4 or more the result is superOp( ... superOp( superOp(x, x, z-1), x, z-1) ..., x, z-1), with y xs.
"""

In [35]:
superOp( 4, 5, 1) # Should give 20

In [36]:
superOp( 3, 4, 2 ) # Should give 81

In [37]:
superOp( 2, 5, 3) # Should give 65536

In [38]:
superOp(3, 2, 4) # Should give 19683

In [39]:
superOp(2,3,4) # Should give 256

In [40]:
superOp(2,2,5) # Should give 4


You can try larger numbers, but I found that with $z=5$, larger values for $x$ and $y$ led to stack overflows.

## My design¶

Note: I didn't bother with pseudocode for this design, because the Python is quite straight-forward. Pseudocode would not have added anything to the discussion.

### First the three warm-up problems¶

In [44]:
def multMine( x, y ) :
"""
pre: y is an integer, y >= 1
post: result == x * y
"""
assert isinstance(y, int) and y >= 1
if y==1: return x
else: return multMine( x, y-1) + x

In [45]:
multMine( 4, 5)  # Should give 20

Out[45]:
20
In [46]:
def expMine( x, y ) :

"""
pre: y is an integer, y >= 1
post: result == x to the power y
"""
assert isinstance(y, int) and y >= 1
if y==1: return x
else: return multMine( expMine( x, y-1), x )

In [47]:
expMine( 3, 4 ) # Should give 81

Out[47]:
81
In [48]:
def towerMine( x, y ) :

"""
pre: y is an integer, y >= 1
post: result == ( ... ((x to the power x) to the power x) ... to the power x), with y x's
"""
assert isinstance(y, int) and y >= 1
if y==1: return x
else: return expMine( towerMine( x, y-1), x )

In [49]:
towerMine( 2, 5 ) # Should give 65536

Out[49]:
65536

### My solution to the superOp contract¶

In [50]:
def superOpMine( x, y, z ) :
"""
pre: y and z are integers with y >= 1 and z >= 1
post: If z is 1, the result is (...(x+x)+ ...)+x, with y xs.
And if z is 2, the result is (...(x*x)* ...)*x, with y xs
And if z is 3, the result (...(x to the x) to the ... ) to the x,  with y xs.
And if z is 4 or more the result is superOpMine( ... superOpMine( superOpMine(x, x, z-1), x, z-1) ..., x, z-1), with y xs.
"""
assert isinstance(y, int) and y >= 1
if y==1: return x
elif z==1: return superOpMine( x, y-1, 1) + x
else: return superOpMine( superOpMine( x, y-1, z), x, z-1)

In [51]:
superOpMine( 4, 5, 1) # Should give 20

Out[51]:
20
In [52]:
superOpMine( 3, 4, 2 ) # Should give 81

Out[52]:
81
In [53]:
superOpMine( 2, 5, 3) # Should give 65536

Out[53]:
65536
In [54]:
superOpMine(3, 2, 4) # Should give 19683

Out[54]:
19683
In [55]:
superOpMine(2,3,4) # Should give 256

Out[55]:
256
In [56]:
superOpMine(2,2,5) # Should give 4

Out[56]:
4

### Some design alternatives¶

This one was obtained from superOpMine by tail-recursion elimination.

In [57]:
def iterativeSuperOp( x, y, z ) :
"""
pre: y and z are integers with y >= 1 and z >= 1
post: If z is 1, the result is (...(x+x)+ ...)+x, with y xs.
And if z is 2, the result is (...(x*x)* ...)*x, with y xs
And if z is 3, the result (...(x to the x) to the ... ) to the x,  with y xs.
And if z is 4 or more the result is iterativeSuperOp( ... iterativeSuperOp( iterativeSuperOp(x, x, z-1), x, z-1) ..., x, z-1), with y xs.
"""
assert isinstance(y, int) and y >= 1
while y>1 and z>1:
x, y, z = iterativeSuperOp( x, y-1, z), x, z-1
if y==1 : return x
else: return iterativeSuperOp( x, y-1, 1) + x

In [62]:
iterativeSuperOp( 4, 5, 1)  # Should give 20

Out[62]:
20
In [63]:
iterativeSuperOp( 3, 4, 2) # Should give 81

Out[63]:
81
In [64]:
iterativeSuperOp( 2, 5, 3) # Should give 65536

Out[64]:
65536
In [65]:
iterativeSuperOp( 3, 2, 4 ) # Should give 19683

Out[65]:
19683
In [66]:
iterativeSuperOp(2, 3, 4 ) # Should give 256

Out[66]:
256
In [67]:
iterativeSuperOp( 2, 2, 5) # Should give 4

Out[67]:
4

This one was obtained from implementing the contract in a fairly straight-forward way.

In [70]:
def iterativeSuperOpPrime( x, y, z) :
"""
pre: y and z are integers with y >= 1 and z >= 1
post: If z is 1, the result is (...(x+x)+ ...)+x, with y xs.
And if z is 2, the result is (...(x*x)* ...)*x, with y xs
And if z is 3, the result (...(x to the x) to the ... ) to the x,  with y xs.
And if z is 4 or more the result is iterativeSuperOpPrime( ... iterativeSuperOpPrime( iterativeSuperOpPrime(x, x, z-1), x, z-1) ..., x, z-1), with y xs.
"""
assert isinstance(y, int) and y >= 1
if z==1: return x*y
result = x
while y > 1:
result = iterativeSuperOpPrime(result, x, z-1)
y = y-1
return result

In [71]:
iterativeSuperOpPrime( 4, 5, 1)  # Should give 20

Out[71]:
20
In [72]:
iterativeSuperOpPrime( 3, 4, 2)  # Should give 81

Out[72]:
81
In [73]:
iterativeSuperOpPrime( 2, 5, 3) # Should give 65536

Out[73]:
65536
In [74]:
iterativeSuperOpPrime( 3, 2, 4)   # Should give 19683

Out[74]:
19683
In [75]:
iterativeSuperOpPrime( 2, 3, 4) # Should give 256

Out[75]:
256
In [76]:
iterativeSuperOpPrime( 2, 2, 5) # Should give 4

Out[76]:
4

I was actually able to compute the $x=2, y=3, z=5$ case without a stack overflow.

In [77]:
iterativeSuperOpPrime( 2, 3, 5)

Out[77]:
340282366920938463463374607431768211456