Square Root Algorithm

Posted: March 17, 2016 in Uncategorized

There are N number of ways to compute square root of a number

we can use the existing library (math) in python to compute the square root

However, there is a constrain in number of decimal digits . Hence, we need an algorithm which can compute a square root and provide n decimal digits .

The following algorithm uses Digit by digit calculation from this wikipedia link

Square Root Computation Algorithms

I have created a python script which will compute square root of 2 with 100 decimal digits .

And i verified the digits from this link

First 100 Digits for SQRT of 2 – Verification

The algorithm is not optimized. However, it gives me the result quickly for first 100 digits

For multiple irrational number , populate the irr list (by default contains 2)

To control number of digits after decimal change decimal variable (by default set to 100)

<br data-mce-bogus="1">
import time
import math

starttime = time.time()

global flag, start, end, decimal
flag = True
start = 0
end = 1
decimal = 100


def main():

answer = 0
irr = [2]

# for each irrational number
for num in irr:

# Step - 1 : Converting number to string and appending 200 zeros
str_num = str(num)
for i in range(0, 210):
str_num = str_num + "0"

# Step - 2: Setting Flag : if lenght of the number is odd we need to take one digit or else two digits
if len(str_num) % 2 != 0:
flag = True
else:
flag = False

start = 0
end = 0
ap_new_dig = 0

# Step - 3: Logic to take one or 2 digits
if flag:
start = 0
end = 1

else:
start = 0
end = 2

temp_num = str_num[start:end]
temp_int_num = int(temp_num)

# Step - 4 : Calculate the initial quotiend and remainder

quo = int(math.sqrt(temp_int_num))
rem = temp_int_num - int(quo ** 2)

# Step - 5 : Here is the main logic to iterate the steps
counter = 0
while counter < decimal - 1 :

# Step - 6 : Bring down the digits
if flag:
start = start + 1
end = start + 2
flag = False
else:
start = start + 2
end = start + 2
new_dig = str_num[start:end]

# Step -7 : Add the digits with previous remainder
ap_new_dig = str(rem) + new_dig

# Step - 8 : Compute a number less than max ap_new_digit
double_num = quo * 2
max_val = 0
t = 0
for i in range(1, 10):
if int( str(double_num) + str(i) ) * i <= int(ap_new_dig):
t = int( str(double_num) + str(i) ) * i
max_val = i
else:
break

# Step - 9 : Find new quotient and remainder
quo = int ( str(quo) + str(max_val) )
rem = int(ap_new_dig) - t

counter = counter + 1

# Final Quotient will be the answer
print "Square Root of N is" , quo



main()

print "Time taken ", time.time() - starttime

Excecution:
 

>>>
Square Root of N is 1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572
Time taken  0.0269999504089

 

 

Advertisements

Comments are closed.