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.
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: The contract actually does unambigously define a function.
The problem doesn't really need more analysis, since the contract is already in a recursive form.
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
.
Complete this function, using recursion. Use +
, but not the *
operator
def mult( x, y ) :
"""
pre: y is an integer, y >= 1
post: result == x * y
"""
mult( 4,5 ) # Should give 20
Complete this function using recursion. Use your mult
function instead of the built in *
operator.
def exp( x, y ) :
"""
pre: y is an integer, y >= 1
post: result == x to the power y
"""
exp( 3, 4 ) # Should give 81
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
"""
tower( 2, 5 ) # Should give 256
After that warm up, it shouldn't be too hard to write the superOp
function described in the first section
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.
"""
superOp( 4, 5, 1) # Should give 20
superOp( 3, 4, 2 ) # Should give 81
superOp( 2, 5, 3) # Should give 65536
superOp(3, 2, 4) # Should give 19683
superOp(2,3,4) # Should give 256
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.
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
multMine( 4, 5) # Should give 20
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 )
expMine( 3, 4 ) # Should give 81
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 )
towerMine( 2, 5 ) # Should give 65536
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)
superOpMine( 4, 5, 1) # Should give 20
superOpMine( 3, 4, 2 ) # Should give 81
superOpMine( 2, 5, 3) # Should give 65536
superOpMine(3, 2, 4) # Should give 19683
superOpMine(2,3,4) # Should give 256
superOpMine(2,2,5) # Should give 4
This one was obtained from superOpMine
by tail-recursion elimination.
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
iterativeSuperOp( 4, 5, 1) # Should give 20
iterativeSuperOp( 3, 4, 2) # Should give 81
iterativeSuperOp( 2, 5, 3) # Should give 65536
iterativeSuperOp( 3, 2, 4 ) # Should give 19683
iterativeSuperOp(2, 3, 4 ) # Should give 256
iterativeSuperOp( 2, 2, 5) # Should give 4
This one was obtained from implementing the contract in a fairly straight-forward way.
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
iterativeSuperOpPrime( 4, 5, 1) # Should give 20
iterativeSuperOpPrime( 3, 4, 2) # Should give 81
iterativeSuperOpPrime( 2, 5, 3) # Should give 65536
iterativeSuperOpPrime( 3, 2, 4) # Should give 19683
iterativeSuperOpPrime( 2, 3, 4) # Should give 256
iterativeSuperOpPrime( 2, 2, 5) # Should give 4
I was actually able to compute the $x=2, y=3, z=5$ case without a stack overflow.
iterativeSuperOpPrime( 2, 3, 5)