Teaching Kids Programming: Videos on Data Structures and Algorithms
We have learned that we can use the binary search algorithm to guess the root – which then converges to the answer we are looking for. We can also use the Recursive algorithm to compute the square root.
Let’s assume the 
where 
is the biggest square number that is less or equal to n.
Then, we can rewrite it as:
Recursively replacing the 
Thus, we can implement as the following, converging the real root until the Error (EPS) is small enough:
1 2 3 4 5 6 7 8 9 10 | def rSqrt(n, a, EPS = 1e-8): b = n - a * a x = a + b/a t = x # while error is still big while abs(x*x - n) > EPS: x = a + b/(a+t) # converge the answer t = x return x |
def rSqrt(n, a, EPS = 1e-8):
b = n - a * a
x = a + b/a
t = x
# while error is still big
while abs(x*x - n) > EPS:
x = a + b/(a+t)
# converge the answer
t = x
return xTest the solution by comparing to Math.sqrt function:
1 2 | print(rSqrt(150, 12)) # 12.247448713888222 print(sqrt(150)) # 12.24744871391589 |
print(rSqrt(150, 12)) # 12.247448713888222 print(sqrt(150)) # 12.24744871391589
This algorithm works for floating numbers as well. This is recursive algorithm however, the implementation is iterative.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
646 wordsloading...
Last Post: How to Sort List by Hamming Weight in C++?
Next Post: Teaching Kids Programming - Ugly Number Detection Algorithm
