 | |
| Credit: OpenClipart.org |
While you already know how to find the square root of a number, you might not be able to describe the process efficiently and precisely to a computer. This could mean embarrassment if you are a computer programmer. Knowing an algorithm is also required of a mathematician. Moreover, knowing something new is always good for knowledge-seekers (which I assume you are if you are reading my blog).
In this post, we will look at a good-enough method of finding square roots, known as the bisection method.
The General Bisection Method
 |
| Credit: clipartkid.com |
Bisection is the general method of finding any root in mathematics and computer science. The idea is to have a set of quantities which has the answer. You keep on narrowing the set while making sure the answer is still there. You pick the midpoint of the set and test it against the answer and repeat if it is not the answer.
The Algorithm
 |
| Credit: codewithc.com |
In this section, I will describe the general logic behind bisection method, step-by-step. For this purpose, we will take the example of finding square roots.
Suppose we have to find the square root of x. For bisection method, we have to prepare a set which would contain the answer; the set is {0...x}. The next step is to take the midpoint and compare it with the correct answer. We don't have the correct answer but we can check if the midpoint is the correct answer quite easily; if (0 + x) / 2 (the midpoint) squared is equal to x, the midpoint is the correct answer, else it is not: we must narrow the set and check the new midpoint. We can narrow the set by considering if the midpoint squared is greater or less than x. If it is greater than x, the midpoint must be greater than the square root of x and we must search the later half ({(0 + x) / 2 ... x}), else we must search the first half ({0 ... (0 + x) / 2}). Since we have already checked (0 + x) / 2, we can remove it from the search set altogether.
No comments:
Post a Comment