Square Root

Coding Skill Exercise #10

Square Root

Implement a method to calculate square root of a given number.

Knowledge Gap Finder

If you are unable to code the solution, answer the following questions and reply to this email to get customized lesson.

Was the problem statement clear to you when you read it? What did you think of doing first? Were you reminded of a construct in general or a general structure of solution that you thought would be useful? Have you previously seen problems that resemble this one? Did you feel stuck at any point while working on this problem? What did you choose as your test case? Do you think you’ve covered all possible scenarios with your tests? What program design techniques did you apply to solve this problem? Are there any constructs of the programming language that you find difficult or confusing to use? What issues make programming constructs difficult to use? For example, the keyword used, the syntax, the examples, the documentation for the construct, etc.

Feel free to forward this email to your friends so they can subscribe here. https://codingskill.biz

title: Square Root excerpt: This covers the basic building blocks such as reduction, three way comparison and guessing. tags: three-way-comparison guessing integer-division reduction

Compute the square root of a number.

Recursive Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def wrapper(n, low, high)
  if low > high
    return -1
  end
  
  guess = (low + high)/2
  square = guess * guess

  if square == n
    return guess
  elsif square < n
    wrapper(n, guess, high)
  else
    wrapper(n, high, guess)
  end
end

def square_root(n)
  wrapper(n, 1, n)
end

p square_root(9)

This method works for even number but fails for odd number. Here is the working code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def wrapper(n, low, high)
  if low > high
    return -1
  end
  
  guess = (low + high)/2
  square = guess * guess

  if square == n
    return guess
  elsif square < n
    wrapper(n, guess, high)
  else
    wrapper(n, low, guess)
  end
end

def square_root(n)
  wrapper(n, 1, n)
end

p square_root(9)

Iterative Implementation

The recursive implementation can be converted to iterative version as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def square_root(n, low, high)
  guess = (low + high)/2
  square = guess * guess

  while square != n
    guess = (low + high)/ 2
    square = guess * guess

    if square < n
      low = guess
    else
      high = guess
    end
  end
  
  guess
end


p square_root(9, 1, 9)

Newton’s Method

Loops are often used in programs that compute numerical results by starting with an approximate answer and iteratively improving it.

For example, one way of computing square roots is Newton’s method. To compute the square root of a, start with an estimate, x and you compute a better estimate with the following formula:

y = 1/2(x + a/x)

Let a = 4 and x = 3, plugging these values into the formula gives us 2.1666.

1
2
3
4
5
6

def square_root(a, x)
  0.5 * (x + a/x)
end

p square_root(4.0, 3.0)
p square_root(4.0, 2.16)

The first guess for square root of 4 is 3, the first square root value is 2.16. We change the next guess to 2.16 (improvement over previous guess 3). This returns 2.00. The values improve and eventually stop changing.

We don’t know how many iterations is required to terminate the loop. Since floating point equality is only approximately right. We can use absolute value to see if the difference between x and y are within a given difference. If they are close enough, we can break out of the loop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def square_root(a, x)
  loop do
    y = (x + a/x) / 2

    if (x-y).abs < 0.001
      break
    end

    x = y
  end
  
  return x
end

p square_root(4,3)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def sqrt_babylonian(num)
    x = num
    y = 1.0
    accuracy_level = 0.000001              
    while x-y > accuracy_level
        x = (x+y)/2
        y = num/x
    end
    x
end

p sqrt_babylonian(26) 
p Math.sqrt(26)

Building Blocks

• Guessing
• Three Way Comparison