[algorithms-1] An application of divide and conquer: Find square root

Problem: Find square root of positive integer, k

Naive:

1. step = 0.001
2. epsilon = 0.01
3. guess = 0.0
4. 
   
5. while abs(guess ** 2 - k) > epsilon:
1. guess += step
6. print("square root of ", k, " is ", guess)

The naive approach described above takes a lot of time to complete. the bigger k is, the more time it takes to compute the square root.

Divide search space each time:

1. epsilon = 0.001
2. min = 0
3. max = k
4. guess = (max + min) / 2
5. while abs(guess ** 2 - k) > epsilon:
1. if guess ** 2 > k:
1. max = guess
2. else:
1. min = guess
6. print("square root of ", k, " is ", guess)

this time we are attempting to find the square root of k with a help of a boundary. with each iteration we are cutting the boundary in half. For k = 100, it took the program 57 iterations to find a good guess.

Divide error at each iteration:

We will be using Newton-Raphson method for finding the square root. We will need bit of math to do the magic. lets define a function f(x) = x ^ 2 - k, we want to find a value of x where f(x) = 0.

1. f(x) = x ^ 2 - k
2. x ^ 2 = k
3. x = sqrt(k)

 We will begin finding the square root of k with a guess, and in the next iteration, we will try to improve our guess. f'(x) is the first derivative, in our case, f'(x) = 2x.
lets say our next guess is x1 and we want f(x1) = 0. we know that,

1. f'(x) = (f(x1) - f(x)) / (x1 - x)
2. f'(x) = -f(x) / (x1- x)     [since f(x1) = 0]
3. x1 - x = - (f(x) / 2x)      [f'(x) = 2x]
4. x1 = x - (f(x) / 2x) 

we can say error = x1 - x, and from line 3, at each iteration we are dividing the error by 2 with each iteration. At line 4, we get the equation to update next guess x1, from previous guess x.

Lets write the program and run it.

1. epsilon = 0.01
2. guess = k/2.0
3. 
   
4. while abs(guess ** 2 - k) >= epsilon:
5.     guess = guess - (((guess**2) - k)/(2*guess))
6. 
   
7. print("square root of ", k, " is ", guess)

 for k = 10,000 the program takes only 9 iterations. 

Compare this logic to divide and conquer of the search space, 57 iterations and naive 100,000,000 iterations.

Source :
[1] mit lecture on square root using newton raphson
[2] intro to computation using python, mit ocw
[3] intro to computation using python. amazon