**1. Approximation (Guess and check to an accuracy of two decimal point dp=0.01)**

Disadvantage of this method is it takes manny guess to find the answer and using step value. If we use step value of small it takes too many guess and too much time to find the answer. If we take big step value, it may fail to find the anaswer itself, though big values takes less guess and less time.

#Square root by approximation by guess and check method

#measure the number of guess

*x = 25*

*dp = 0.01*

*step = dp**2*

*numGuesses = 0*

*ans = 0.0*

*while (abs(ans**2 – x)) >= dp and ans <= x:*

* ans += step*

* numGuesses += 1*

*print(‘numGuesses = ‘ + str(numGuesses))*

*if abs(ans**2-x) >= dp:*

* print(‘Failed on square root of ‘ + str(x))*

*else:*

* print(str(ans) + ‘ is close to the square root of ‘ + str(x))*

**OUTPUT**:

numGuesses = 49990

4.999 is close to the square root of 25

###### 2. Bisection (Take midpoint between 0 and x and compare it’s higher or smaller

http://www.mathpath.org/Algor/squareroot/algor.square.root.binary.htm

Ex., Find the square root of 25 upto 2 decimal points (epsilon=0.001)

dp=0.01 (we are trying to find square root of 25 to an accuracy of .01 decimals)

# bisection search for square root

”’

This is efficient method compare to Approximation guess and check method

Example below finding square root of 25 to an accuracy of 2 decimal points 0.01

”’

*x = 25*

*dp = 0.01*

*numGuesses = 0*

*low = 0.0*

*high = x*

*ans = (high + low)/2.0*

*while abs(ans**2 – x) >= dp:*

* print(‘low = ‘ + str(low) + ‘ high = ‘ + str(high) + ‘ ans = ‘ + str(ans))*

* numGuesses += 1*

* if ans**2 < x:*

* low = ans*

* else:*

* high = ans*

* ans = (high + low)/2.0*

*print(‘numGuesses = ‘ + str(numGuesses))*

*print(str(ans) + ‘ is close to square root of ‘ + str(x))*

**OUTPUT**:

*It took 13 guesses to find the answer, very efficient compare to previous approximation guess and check method*

*low = 0.0 high = 25 ans = 12.5*

*low = 0.0 high = 12.5 ans = 6.25*

*low = 0.0 high = 6.25 ans = 3.125*

*low = 3.125 high = 6.25 ans = 4.6875*

*low = 4.6875 high = 6.25 ans = 5.46875*

*low = 4.6875 high = 5.46875 ans = 5.078125*

*low = 4.6875 high = 5.078125 ans = 4.8828125*

*low = 4.8828125 high = 5.078125 ans = 4.98046875*

*low = 4.98046875 high = 5.078125 ans = 5.029296875*

*low = 4.98046875 high = 5.029296875 ans = 5.0048828125*

*low = 4.98046875 high = 5.0048828125 ans = 4.99267578125*

*low = 4.99267578125 high = 5.0048828125 ans = 4.99877929688*

*low = 4.99877929688 high = 5.0048828125 ans = 5.00183105469*

*numGuesses = 13*

*5.00030517578 is close to square root of 25*

###### 3. Newton-Raphson (General approximation algorithms)

Newton and Raphson same time proposed this General Approximation algorithms, hence it got popular with bot the namess. Formula we use for this method is shown below. This method will be very efficient as it takes very less time and less number of guesses.

Formula is guess -(guess^2 – k) / 2*guess

*# Newton-Raphson for square root*

*”’*

*Newton and Raphson same time proposed this General Approximation algorithms, hence it got popular with bot the #namess. Formula we use for this method is shown below. This method will be very efficient as it takes very less time and #less number of guesses. *

*#Formula is guess -(guess^2 – k) / 2*guess*

*#dp decimal point g Guess*

”’

*dp = 0.01*

*x = 25.0*

*g = x/2.0*

*while abs(g*g – x) >= dp:*

* g = g – (((g**2) – x)/(2*g))*

* print(g)*

*print(‘Square root of ‘ + str(x) + ‘ is about ‘ + str(g))*

*output:*

*7.25*

*5.34913793103*

*5.01139410653*

*5.00001295305*

*Square root of 25.0 is about 5.00001295305*

**Acknowledgement**: These are taken from Eric Grimmson lectures in edx for the course “6.00.1x Introduction to Computer Science and Programming”