The Zen Of Python

I found these fantastic guiding principles of the design of Python published here by Tim Peters, and  once I saw them, I was like, Man! I ought to share these, so look them up on the site, or if you don't want to leave programming for COWARDS just yet, I'm quoting them here for you ;)  :

The Zen of Python


Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!

Those quotes are pure gold. One could think of writing them down on a board and keep that board hanged in front of his eyes, right above the computer screen!

Awesome, awesome stuff!

Back to Basics: Square Root Implementation in Python and C# (Newton's Method)

In my last post I introduced to you an extra simple algorithm to calculate square roots, it's called the Bi Section method. The Bi (pronounced by) part comes form the word binary. This is due to the fact that each time we pick a guess we pick it at a point in the middle between an upper bound and a lower bound. This technique is very useful in many cases in computer science (e.g. Binary Search is a very famous example of that).

As you see the Bi Section method is really simple, however, it's not that effective.
This time I will introduce a different method to calculate square roots, this method is called "Newton-Raphson's method", it's named after Issac Newton, and Joseph Raphson.

This method is known to be really effective --especially when the initial guess is near from the correct answer-- and it's considered to be the  best known method for finding successively better approximations to the zeroes (or roots) of a real-valued function. 
Explaining this method will require a certain amount of familiarity with Calculus and Algebra, so I'm not going to delve into this here. However, I will show you the code to do it in Python and C# (which, surprisingly you will find very simple). 


First, the code in Python:

def sqrtWithPrecisonNR(x, precision):   
    assert x >= 0, 'x must be non-negative, not' + str(x)
    assert precision > 0, 'epsilon must be positive, not' + str(precision)
    x = float(x)
    guess = x/2.0    
    diff = guess**2 -x
    ctr = 1
    while abs(diff) > precision and ctr <= 100:
        guess = guess - diff/(2.0*guess)
        diff = guess**2 -x
        ctr += 1
    assert ctr <= 100, 'Iteration count exceeded'
    print 'NR method. Num. iterations:', ctr, 'Estimate:', guess
    return guess

Second, the code in C#: 

float SqrtWithPrecisonNR(float x, float precision)
        {
            if (x < 0 || precision <= 0)
                throw new ArgumentException("x, and precission gotta be non negative numbers");
            float guess = x/2.0f;
            float diff = guess*guess - x;
            int counter = 1;
            while(Math.Abs(diff) > precision && counter <= 100)
            {
                guess = guess - diff/(2.0f*guess);
                diff = guess*guess - x;
                counter++;
            }
            if(counter > 100)
                throw new Exception("100 iterations done with no good enough answer");
            Console.WriteLine("Num of Iterations: {0} , estimate: {1}", counter, guess);
            return guess;
        }

Now, I want you to try this method with the last one and see the difference.
Here's a helper function that will test the two methods with input 2 as the root and 0.000001 precision:

def testMethods():
    sqrtWithPrecision(2, 0.000001)
    sqrtWithPrecisionNR(2, 0.000001)    

You should see that the Newton's method is much faster and this difference in speed will be totally apparent when you try it on bigger numbers.

For more details about the Newton's method including the mathematical stuff see here

Back to Basics: Square Root Implementation in Python

Two days ago a friend of mine who is a computer science student asked me about the simplest square root algorithm that I know about. Well, I know how pesky students suffer when trying to computer square roots, so I had to choose an easy one.

I know about the famous Cramack method but this sounds complicated to me (though it's the most efficient method AFAIK). So I preferred the goody (Guess, Evaluate, Improve) method. So for example if I want to calculate the square root of the number let's say, 2, my strategy will be like the following: 


1- Pick a guess (1 for example)
2- Evaluate that guess: is 1 * 1 near enough to 2 (see the bold near enough expression!)
3- If the guess is not near enough, Improve it. 


Note that I didn't use the term "equals" when evaluating the expression, rather I used the term "near enough" and this is because, with numbers that are not full squares (like 2 for example), the square root is going to be a floating point number (square root of 2 = 1.414213562373095). Now if you multiply this number --the square root of 2-- by itself, you should expect to have 2 as an answer. Well, that's not gonna happen, rather you're going to get (2.0000000000000004). This is happening due to the way that computers handle floating point numbers --which is a topic of other series of posts by itself. In this case if you used the term equals (or == operator) when evaluating the guess you will never make it, and your program will not halt. That's why I carefully used the term near enough. Defining what near enough means is your choice now, for certain situations you might consider a number that is less than the square root by 0.1 is near enough or 0.001 or 0.0001, etc. This depends on the level of precision that you need for your specific scenario.


The implementation: 
Here's a python implementation of this algorithm.

## calculates the square root of a positive number
## with the passed in precision
def sqrtWithPrecision(x, precision):
    ## The precision must be greater than zero,
    ## root must be a positive number
    assert(precision > 0, str(precision), 'is not a valid value, it must be a positive integer')
    assert x > 0, 'root can not be a negative number'
    low = 0
    high = max(x, 1)
    counter = 0
    guess= (low + high) /2.0
    while abs (guess ** 2 -x) > precision and counter <= 100:
        if(guess ** 2 < x):
            low = guess
        else:
            high = guess
        guess = (low + high) / 2.0
        counter += 1
    assert counter <= 100, '100 iterations done and no good answer'
    ## printing the number of iterations,
    ## in productive code, you might want to remove the next line
    print 'Num of iterations:', counter, 'Estimate:', guess
    return guess

And here's a c# example:

float sqrtWithPrecision(float x, float precision)
        {
            if (x < 0 || precision <= 0)
                throw new ArgumentException("x, and precission gotta be non negative numbers");
            float low = 0;
            float high = Math.Max(1f, x);
            float guess = (low + high)/2f;
            int counter = 0;
            while( Math.Abs(guess * guess - x) > precision && counter <= 100)
            {
                if (guess * guess < x)
                    low = guess;
                else
                    high = guess;
                guess = (low + high)/2f;
                counter++;
            }
            if(counter > 100)
                throw new Exception("100 iterations done with no good answer");
            Console.WriteLine("Num of Iterations: {0} , estimate: {1}", counter, guess);
            return guess;
        }