SICP Square Root Procedure

I haven't progressed much further in SICP. There have been so many interruptions. We traveled to Santa Clara for Pycon, where my husband, sontek, lead a tutorial on gevent, socketio, and realtime web (all things currently above my comprehension). Our son met Steve Holden, the chair of the Python Foundation, and many other developers known in the world of Python. I was hanging out in the lobby of the conference center one day so that I could see some of my husband despite the time involvement of the conference. Oddly enough, my SICP book got just as much attention as having a baby in a stroller and being female. I was more than the elephant in the room. I was a pink elephant wearing roller skates.

Continuing with SICP, I want to discuss the square root procedure example. It is excellent at demonstrating a lot of basic programming principles. Of course, Python has excellent math tools that make defining a procedure for square root unneccesary, but let's just do it for fun. First, we need to understand Newton's Method.

Let's pretend we did not know the square root of 9. We GUESS the answer is 2. But 2 squared is 4. So how do we get closer to the answer? We take the average of our GUESS and X, which is 9, divided by our most recent guess. The average would be 2.75 ( (9/2+2)/2 ). Now 2.75 becomes our new GUESS. We repeat, until guess squared is equal to 9, our x. So what does our code need to do?

make a guess -> square guess to check if good enough -> take the average of guess and x divided by guess if not good enough -> use computed average to improve guess -> square guess to check if good enough -> take the average...
An iterative procedure (repeating) until when?

Some numbers may take a very long time to solve exactly, or the square root may be a decimal with over 10 numbers beyond the decimal, so we also need to allow for some error. When we check if the square of the guess is equal to our x value, we can allow a difference less than .001, between the squared guess and the value of x, ending the iterations. We also need to define what our original guess will be. SICP uses 1.0, so let's try that. In both lisp and python, a number with a decimal allows floating numbers to be computed, while an integer without a decimal does not. Some of our definitions are modular, or reusable, so I'm going to give square, average, and abs their own definitions. I am ignoring the built-in absolute value, just so we can do more coding. I'm calling the absolute value definition abs2. I solve this problem in a different order than SICP, so I'm going to show my logic, in Python.

First, I wrote my code in Vim, so I could fix typos easily and experiment more quickly. In my terminal, I created sqrtsicp.py:

vim sqrtsicp.py

Our modular definitions mentioned previously are easy. Let's get them out of the way.

def square(x):
    return x*x

#naming absolute as abs2 to avoid built-in "abs"
def abs2(x):
    if x<0:
        return -x
   else:
        return x

def average(x,y):
   return (x+y)/2

Now for the hard part. We'll skip the first guess right now. The iterative part involves checking if our guess is good enough, then improving our guess if it is not good enough (good enough is false), only to try to determine if our improved guess is good enough.

def sqrt_iter(guess):
   if good_enough(guess):
       return guess
   else:
       return sqrt_iter(improve(guess))

Next we define how we determine if good_enough is true and how to improve our guess. Both of these need to know the value of x to compute.

def good_enough(guess,x):
   return abs2(square(guess)-x)<.001

def improve(guess,x):
    return average(guess,x/guess)

Now we have two problems. One, the x is being used for good_enough() and improve() without receiving the value of x from sqrt_iter(). Second, we need a starting guess. This is the point where I put good_enough(), improve() and sqrt_iter() all together and give it an initial guess. Our variable x is a constant and can be passed in from the overall procedure sqrt().

def sqrt(x):
    def good_enough(guess):
         return abs2(square(guess)-x)<.001
    def improve(guess):
         return average(guess,x/guess)  
    def sqrt_iter(guess):      
         if good_enough(guess):          
             return guess
         else:
             return sqrt_iter(improve(guess))
     return sqrt_iter(1.0)

It's good structuring to have all your definitions before your actions. The final line is the return function that causes the dominos to fall. sqrt_iter() calls itself on the new guess if our latest guess was not good enough. "Calling itself" is known as recursion. Now just make it a program. Within my file, I define the main procedure (not sure of the programmers vernacular)where my program is going to ask what to take the square root of. I want the input to be any positive number, including decimals. I want to use exception handling to ask for a floating number if the user inputs a string. I'm also going to define the decimal places for the output of the square root procedure to 3 digits past the decimal. If a negative number is entered, I ask for a positive number and attempt the program again. If a string is entered, I say "Oops, that's not a number" before calling the program again.

def main():
    try:
        x=float(raw_input("What number do you want to find the square root of? "))
        answer = sqrt(x)
        print("The answer is \n%.3f") %answer
    except:
        print("Oops, that is not a number")
        main()

if __name__=="__main__":
    main()

Those three pieces combined are a completed program. In my terminal, I can run it by typing:
python sqrtsicp.py

Playing with it, I attempt to find the square root of -9, 874, .04, and L. All my results are what I expect. This may be a good candidate for selenium testing or a unit test in more complicated programs. For another example of exception handling, view my Caesar's Shift. For more information of float from wikipedia, read this article. You can also refresh your math tools knowledge, including absolute value here.