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