## Counting computational steps -- a tutorial.

## We will work with the following four procedures taken from MCS-178.
## Make sure you understand each of them before continuing.
def power1(b, e):
    pow = 1
    while (e > 0):
        pow = pow * b
        e = e - 1
    return pow

def power2(b, e):
    pow = 1
    while (e > 0):
        if ((e % 2) == 0):
            b = b * b
            e = e / 2
        else:
            pow = pow * b
            e = e - 1
    return pow

def power3(b, e):
    if (e == 0):
        return 1
    else:
        return b * power3(b, e - 1)

def sumOfPowers(b, n):
    total = 0
    for e in range(n):
        total = total + power1(b, e)
    return total

## We can modify each of these four procedures to return a pair of values;
## the first value is the same answer as before.  The second value is a
## count of how many computational steps were performed.  At this point,
## we need to decide what our definition is of "computational step."  The
## code below keeps count of how many multiplications are performed.  I've
## put some notes in about how this is done, because the details vary
## depending on whether the procedure does any subprocedure calls.  You
## should make sure of three things:
##  (1) You understand how these procedures count multiplications.
##  (2) You see how to change them to, for example, count all of (+,-,*,/).
##  (3) You understand why such a change wouldn't matter for a Theta analysis.

def power1Steps(b, e):
    pow = 1
    steps = 0
    while (e > 0):
        pow = pow * b      ## Note: every line that does a multiplication
        steps = steps + 1  ## comes together with increasing the count.
        e = e - 1
    return pow, steps

def power2Steps(b, e):
    pow = 1
    steps = 0
    while (e > 0):
        if ((e % 2) == 0):
            b = b * b
            steps = steps + 1
            e = e / 2
        else:
            pow = pow * b
            steps = steps + 1
            e = e - 1
    return pow, steps

def power3Steps(b, e):
    if (e == 0):
        return 1, 0
    else:                                  ## Recursive case: find out how many
        pow, steps = power3Steps(b, e - 1) ## steps are done in the recursion
        return b*pow, steps+1              ## and then note that we do one more.

def sumOfPowersSteps(b, n):
    total = 0
    steps = 0
    for e in range(n):
        pow, newSteps = power1Steps(b, e) ## Similar to recursion; the number of
        total = total + pow               ## steps done in the subprocedure
        steps = steps + newSteps          ## gets added into our count of steps.
    return total, steps

## In sumOfPowersSteps, all the multiplications come from the subprocedure.
## If you instead were counting arithmetic operations in general, you'd have
## to count the additions done in the line "total = total + pow".

## Now we can get concrete numbers of steps just by running these procedures.
## But to get a general formula for how the number of steps scales up with
## increasing values of e or n, we need to do some analysis.  In principle,
## this is no different from what you would do to figure out the answers
## computed by any procedure.  For example, you can figure out that power1(b,e)
## returns b^e.  Similarly, you can figure out that power1Steps(b,e) returns
## a pair of values.  The first value is b^e, and the second value is....

## In the power1Steps procedure, note that the only place steps is increasing is
## in the loop, and it is increasing by 1 every trip through the loop.  Here,
## the question is just how many trips through the loop.  Note that if e=0,
## the loop body is executed 0 times.  Checking that boundary condition is
## important for avoiding a common error, an off-by-one error.  Given
## that e decreases by 1 each trip through the loop, you ought to be able
## to convince yourself that there are e trips through the loop.  Thus, if
## we use the notation T1(e) to mean the number of multiplications done by
## power1, we have T1(e)=e. If we instead also included additions in our count,
## we'd have T1'(e)=2e.  And if we counted multiplications, additions, and the
## > test, we'd have T1''(e)=3e+1.  Notice that here we've got 3 operations
## performed for each trip through the loop body, plus 1 extra operation. That
## extra operation is the final > test when e=0.  Any operations positioned
## entirely before or after the loop would add in similarly.

## Before proceding, it would be worth checking whether the formula we derived
## for T1(e) actually agrees (for some specific values of e) with the second
## value returned by the power1Steps procedure. Try it out.

## The analysis for power2Steps is similar in that there is one multiplication
## per trip through the loop body.  Figuring out how many times the loop body
## is executed is difficult in general.  Therefore, concentrate on the case
## where e = 2^k, for some natural number k.  Again, to avoid off-by-one errors,
## start by looking at what happens when k=0.  In that case, we have e=1.
## Because e is odd, we would take the second branch, where e is decreased by 1.
## At that point e would no longer be >0 and the loop would terminate.  Thus,
## for k=0, we have 1 execution of the loop body.  Given what is done in the
## loop body, we see that this also means 1 multiplication.  Now check what
## happens for larger values of k.  Each time k increases by 1, the value of
## e doubles.  That makes for one just extra trip through the branch used when
## e is even, because that branch cuts e in half.  (You might find it helpful
## to try a few small cases, such as k=1 and k=2, which correspond to e=2 and
## e=4.)  The bottom line is that we have T2(2^k) = k+1.  Of course, it would
## be nice to rewrite this in terms of e.  Assuming that e=2^k, we can take
## the log of both sides and find that k = lg e.  Thus, T2(e) = (lg e) + 1.
## Again, try this out for some specific values of e that are powers of 2.

## For power3Steps, we wind up with a recurrence relation, parallel to the
## recursive form of the procedure:
##
##  T3(0) = 0
##  T3(e) = 1 + T3(e-1), when e > 0
##
## This leaves the problem of finding a closed form solution. In one way or
## another, you ought to be able to convince yourself that T3(e) = e.

## Next we can turn our attention to sumOfPowerSteps.  Call its total
## number of multiplications Ts(n), all of which are done in the subprocedure.
## Just as T3 was defined in terms of T3 (in the recurrence relation), we
## find that Ts needs to be defined in terms of T1.  The form of the equation
## parallels the form of the procedure.  Specifically, we have
##
## Ts(n) = the sum for e in the range 0<=e<n of T1(e)
##
## Substituting in our earlier formula for T1(e), whe have
##
## Ts(n) = the sum for e in the range 0<=e<n of e = n(n-1)/2
##
## As always, this would be good to check for some sample values of n.

## Having analyzed the procedures exactly, we could cast each of them into
## Theta form. (For T2, we ought to check that values of e that aren't powers
## of 2 stay within the same order of growth.)  However, it is also often
## possible to do the analysis in Theta form in the first place, rather than
## starting exact and moving to Theta later.  For example, in T1, we could
## note that the loop executes Theta(e) times, without having to worry about
## whether it is exactly e or e-1 or e+1; the concern for off-by-one errors
## goes away.  Similarly, we can readily see that Theta(1) operations are
## done in each execution of the loop body, without needing to worry about
## exactly how many.  (This would be important if the loop body were more
## complicated or we were counting more than just multiplications.)  All that
## this means is that the number of operations in each execution of the loop
## body doesn't grow with e.  With these two pieces, we can conclude that the
## total work is Theta(e).

## This is also a convenience in working with the recurrences for recursive
## procedures.  For T3, we'd be able to avoid talking about the base case
## and just write
##
## T3(e) = T3(e-1) + Theta(1)
##
## again, this is enough to show that T3(e) = Theta(e).  In our discussion of
## divide and conquer algorithms, we've been taking this approach.  As an
## exercise, you can recast power2 into the form of a divide and conquer
## algorithm, write the corresponding recurrence relation, and solve it
## using the master theorem.  Hopefully you find T2(e) = Theta(log e).