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

Python: Lists (difference between Lists and Tuples)

#Lecture 6 Lists

”’

Lists look like Tuples, but they have some critical differences. It’s very important to make out the differences

Tuples Lists

===================== ===================================

used () parenthesis Uses [] parenthesis

singlets need , (5,) No additional comma reqired [5]

Immutable, means elements can’t Important feature, Lists are mutable

be modified e.x.,: Trees=[‘Mango’, ‘Neem’, ‘Tamarind’]

we can replace Neem i.e. Trees[1]=’Banian’

Now Trees List will looks as

Trees=[‘Mango’, ‘Banian’, ‘Tamarind’]

”’

Trees=[‘Mango’, ‘Neem’, ‘Tamarind’]

Fruits=[‘Apple’, ‘Banana’]

print Trees, Fruits

#Modify the Trees lists

Trees[1]=’Banian’

print Trees

#using methods like append, we can extend Lists

Fruits.append(‘Mango’)

print Fruits

#Now we will see another example called “Aliasng”

Plants=[Trees,Fruits]

Plants1=[[‘Mango’, ‘Banian’, ‘Tamarind’], [‘Apple’, ‘Banana’, ‘Mango’]]

#if you print both look alike

#print Plants

#print Plants1

#Now modify Trees lists using append method

Trees[1]=’Neem’

print Plants

print Plants1

”’

OUTPUTs varies

Plants output [[‘Mango’, ‘Neem’, ‘Tamarind’], [‘Apple’, ‘Banana’, ‘Mango’]]

Plants1 output [[‘Mango’, ‘Banian’, ‘Tamarind’], [‘Apple’, ‘Banana’, ‘Mango’]]

”’

python – oddTuples

#Python Function which returns odd Tuples

”’

Write a procedure called oddTuples, which takes a tuple as input,

and returns a new tuple as output, where every other element of the input tuple is copied,

starting with the first one. So if test is the tuple (‘I’, ‘am’, ‘a’, ‘test’, ‘tuple’),

then evaluating oddTuples on this input would return the tuple (‘I’, ‘a’, ‘tuple’).

”’

def oddTuples(aTup):

”’

aTup: a tuple

returns: tuple, every other element of aTup.

”’

# Your Code Here

num=1

t1=()

for i in aTup:

if num%2 == 1:

t1= t1+(i,)

num+=1

else:

num+=1

return t1

print oddTuples((1, ‘two’, 3, ‘four’, 5))

python programme to calculate greatest common divisior (GCD) using recursion

def gcdIter(a, b):

”’

a, b: positive integers

returns: a positive integer, the greatest common divisor of a & b.

”’

# Your code here

Recursive Method

 if a == b:

 return a

  elif a > b:

 return gcdIter(a-b, b)

elif b > a:

return gcdIter(a, b-a)

What software can be used to write python programs on windows desktop ?

1. What software can be used to write python programs on windows desktop ?

Enthought Canopy you can download from this link 

You can use standard python programming tool IDLE

2. Python Reference

http://docs.python.org/2/contents.html

go here for the “official”/technical explanation of what a particular function/operator does, examples of correct syntax, what the various libraries are, etc.

edx course referring text book

Introduction to Computation and Programming Using Python, Revised And Expanded Edition
by John V. Guttag