On Finding Square Roots with Bisection Method

When I first started out to write code for finding the nth root of a given number (except for nth root of negative numbers when n is even), I did not realize that there are some fine nuances to be taken care of in the code. For example, whenever we are using a bisection method, we ought to decide the lower and upper bounds. For example, when we want to find the square root of a number x, we can reasonably assume, the lower bound is 0 and the upper bound is x. However, this assumption fails, if we consider the following cases:

  • The number can be a positive or a negative number
  • The number can be less than or greater than 1.

If the number is a negative number, then the lower bound becomes x and the upper bound becomes 0. If the number is less than 1, then the nth root of the number falls – not between 0 and the number, but between the number and 1 (that is how fractions work!). So, I wrote this logic for deciding lower and upper bounds given a number. A bit verbose, but readable:

if abs(x) > 1:
        low = min(0,x)
        high = max(0,x)
    elif x < 0:
        low = -1
        high = x
        low = x
        high = 1

However, it turns, out there is a more simpler (and bit non-intuitive) version of it:

low = min(-1, x)
high = max(x, 1)

If we think about the first snippet carefully, we see that the second snippet is just a condensed version of it, but it needs some real experience to come out with it. We may be extending the lower or upper bounds a bit more than is necessary, but the code is simple and more elegant. With bisection method, we will get over the extended boundary in just a couple of passes!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s