6.00.1x Week 2

In week 2, I learnt to write functions in Python. The format of function in Python is as follows:

whereas in C, it is written as:

To program a basic function such as function to find the square root of a number, there are many approaches. We can use:
1. Linear search (exhaustive enumeration) – a type of guess and check
2. Bisection search
3. Newton-Raphson method

linear search or exhaustive enumeration

Assuming we don’t have a calculator with us, how would you find a square root of a number, say square root of 137. We can take a guess, 1, since 1^{2}=1 is smaller than 137, we have to increment our guess, by a fixed step, say 2, the next guess will be 3, since 3^{2}=9 is still smaller than 137, we have to keep incremented our guess by the fixed step, until guess exceeds the number. This method is called linear search or exhaustive enumeration, this method is not good enough because when the number gets bigger, more number of steps are required to be tested. Also, the step size cannot be too big, if not our guess may slip pass the answer, in turn, this means more tests because each guess increments by only a small step.

Bisection search method

Next, we use a far more efficient approach, the bisection search method. As the name implies, bi means two, it eliminates half of the guesses on each operation. Return to our example, to find the square root of 137, using Bisection search, we have to set a lower and upper bound. Initially, the lower bound will be 0 and upper bound will be 137, because our answer may lie within this range. First, we take the midpoint of lower and upper bound, and take it as our guess. Is \mbox{Guess}=\dfrac{(0+137)}{2}=69 , is 69^{2}=4761 smaller or bigger than 137? It is bigger, so we know we over guessed, the answer lies in numbers lower than 69 (guess), so we move our upper bound to \mbox{guess} , now our range is (0, 69). Set the new guess as the midpoint of lower and the new upperbound, check the new guess, if it is bigger than the answer, make the guess the new upper bound, if it is smaller than the answer, make the guess the new lower bound. Continue until the \mbox{guess}^{2} is almost equals to the number. This method has two advantages, it can find accurate answer to many decimal places, also, it takes far shorter time compared to previous method.

Bisection search by Ling Gen Sheng Shaun
Bisection search by Ling Gen Sheng Shaun

Newton-Raphson method

The fastest method among the three is Newton-Raphson method. The Newton-Raphson method were founded by both Newton and Raphson at the same time, it is used to find root of a polynomial function. A polynomial is an expression with variables raised to a power and their coefficients. An example of polynomial of degree 3 is:

3x^{3}+2x^{2}-4x+7

A root of polynomial function is the value of x when y=0 (when the polynomial function intersects the x-axis).


Newton-Raphson method states that, with a guess, a better guess is:
\mbox{guess} - \dfrac{\mbox{polynomial(guess)}}{\mbox{polynomial}'\mbox{(guess)}}
For example to find a root of 3x^{3}+2x^{2}-4x+7=y, we take a guess 1, substitute into the equation, 3(1)^{3}+2(1)^{2}-4(1)+7=8 , it is not equals to zero, so it’s not the root. A better guess will be \mbox{guess}-\dfrac{(3x^{3}+2x^{2}-4x+7)}{(9x^{2}+4x-4)} , which is 1-\dfrac{8}{9}=0.1111 , continue the iteration until the y becomes very close to 0. The guess will be the root.

We can make finding a square root of a number into finding a root in a polynomial. Take the number 137, we want to find the square root of this number. \mbox{answer}=\sqrt{137} , \mbox{answer}^2=137 , \mbox{answer}^2-137=0 .
Now it seems familiar, because it can be expressed as a polynomial function:

x^{2}-\mbox{number}=y

Don’t worry about the details, just know what to find a square root of a number is same as finding the root of polynomial function.

Take a guess, substitute into the equation, x^{2}-\mbox{number}=y , the number we want to find is 137, we will take the first guess, x as 1. So, 1^{2}-137=-136 , this is not equals to zero, meaning 1 is not the root of the polynomial, and so is not equals to sqare root of 137. Take another guess, \mbox{guess}-\dfrac{x^{2}-\mbox{number}}{2x}=1-\dfrac{1^2-137}{2(1)}=-68 , it still is not equals to zero, so continue taking new guesses until the equation gets near to zero, then the guess is the square root of the number.

Closing statement

The above methods can be implemented into computable scripts.
1. Refer here for implementation of linear search (exhaustive enumeration). – finding cube root, same concept.
2. Refer herefor Bisection search implementation.
3. Refer here for Newton-Raphson implementation.
Why do we need to find faster methods in calculating the square root if the computer can do billions of operations per second? Because for some problems, the time taken can increase exponentially if the number gets larger. In a chess game, there are more moves than there are number of atoms in the universe, it is not feasible to iterate over each possible move, we have to find a clever and faster way eventhough our computers are very fast.

Leave a Reply