Python: Finding Square Root – in 3 methods

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”

Advertisements

Author: rajukv

Hadoop(BigData) Architect and Hadoop Security Architect can design and build hadoop system to meet various data science projects.

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