Iteration/Loops in Python (from Guttag)

An example

---

def findRoot(x, power, epsilon):
    """Uses bisection search to find a root
    require:
        epsilon > 0 & power >= 1
    ensure
        Result = x**(1/power) within epsilon
    i.e. Returns a float 'Result' such that 
    Result**power is within epsilon of x.
    If such a float does not exist, it returns None
    e,g. 1.26171875 = 2**(1/3), so findRoot(2, 3, 0.01) = 1.26171875""" 
    if x < 0 and power%2 == 0:
        return None
    low = min(-1.0, x)
    high = max(1.0, x)
    ans = (high + low)/2.0
    while abs(ans**power - x) >= epsilon:
        if ans**power < x: 
            low = ans
        else:
            high = ans
        ans = (high + low)/2.0 
    return ans

def testFindRoot():
    epsilon = 0.0001
    for x in (0.25, -0.25, 2, -2, 8, -8):
        for power in range(1, 4):
            print ('Testing x = ' + str(x) +\
                ' and power = ' + str(power))
            result = findRoot(x, power, epsilon) 
            if result == None:
                print (' No root')
            else:
                print (' ', result**power, '~=', x)

testFindRoot()

---

Discussion

Defining the problem

Imagine that someone asks you to write a program that finds the square root of any nonnegative number. What should you do?

You should probably start by saying that you need a better problem statement. For example, what should the program do if asked to find the square root of 2? The square root of 2 is not a rational number. This means that there is no way to precisely represent its value as a finite string of digits (or as a float), so the problem as initially stated cannot be solved.

The right thing to have asked for is a program that finds an approximation to the square root—i.e., an answer that is close enough to the actual square root to be useful.

We might do an exhaustive enumeration but bisection search is more efficient. In the program above we provide a program to find an approximation to a root.

Functions and abstraction/decompostion

We pack the program in a function findRoot. Functions are a way of creating computational elements that we can think of as primitives. Just as we have the built-in functions max and abs, we would like to have the equivalent of a built-in function for finding roots and for many other complex operations. Functions facilitate this by providing decomposition and abstraction.

Specifications

We also provide specification of the function defines a contract between the implementer of a function and those who will be writing programs that use the function. We will refer to the users of a function as its clients. This contract can be thought of as containing two parts:

1. Assumptions (require): These describe conditions that must be met by clients of the function. Typically, they describe constraints on the actual parameters. Almost always, they specify the acceptable set of types for each parameter, and not infrequently some constraints on the value of one or more of the parameters. For example, the first two lines of the docstring of findRoot describe the assumptions that must be satisfied by clients of findRoot.
2. Guarantees (ensure): These describe conditions that must be met by the function, provided that it has been called in a way that satisfies the assumptions.

Documentation

The docstring of findRoot describe the guarantees that the implementation of the function must meet.

Testing

The function testFindRoot is almost aslong as findRoot itself. To inexperienced programmers, writing test functions such as this often seems to be a waste of effort. Experienced programmers know, however, that an investment in writing testing code often pays big dividends. It certainly beats typing test cases into the shell over and over again during debugging (the process of finding out why a program does not work, and then fixing it). It also forces us to think about which tests are likely to be most illuminating.