## 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