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
|
|
This method works for even number but fails for odd number. Here is the working code:
|
|
Iterative Implementation
The recursive implementation can be converted to iterative version as follows:
|
|
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.
|
|
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.
|
|
|
|
Building Blocks
- Guessing
- Three Way Comparison