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: The contract actually does unambigously define a function.

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