Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Finding Square Root

Problem: Write a routine to find the square root of any given number N.

Solution: Square root can be found if we observe the following:

If x is larger than the exact square root of of N, then N/x will be smaller than the exact square root of N
So, if we start with x as an approximation of the square root, then a better approximation can be obtained by xbetter = x + N/x
The above relation is repeatedly used unless the error between N and x2 becomes acceptable.

 ``` public class SquareRoot { static double squareRoot (double n) { double x = n/2; double sq = x*x; while ( Math.abs(n - sq) > 0.00001) { x = (x + n/x) / 2; sq = x*x; } return x; } static java.text.DecimalFormat df = new DecimalFormat ("###.####"); public static void main(String[] args) { for (int i=1; i<100; i++) { double d = Math.random()*(i); System.out.println ( "squareRoot(" + df.format(d) + ") = " + df.format(squareRoot(d))); } } } ``` Basically, if x becomes too lower than sqrt(N), then N/x helps to pull it towards sqrt(N). Similarly, N/x pulls x down if it becomes too large than sqrt(N). Together, both x and N/x converge to get as close to sqrt(N) as possible. Since both strive to converge towards sqrt(N), their sum is expected to converge towards 2*sqrt(N). That's why we divide by 2 in (x + N/x)/2

This method is an example of the Bisection Method used to find solution for any continuous function f(x).

Sample Execution:
```squareRoot(0.5442) = 0.7377
squareRoot(1.5065) = 1.2274
squareRoot(1.8271) = 1.3517
squareRoot(0.7056) = 0.84
squareRoot(4.1558) = 2.0386
squareRoot(3.256) = 1.8044
squareRoot(6.8183) = 2.6112
squareRoot(5.0967) = 2.2576
squareRoot(1.6155) = 1.271
squareRoot(6.8031) = 2.6083
squareRoot(4.6613) = 2.159
squareRoot(1.9851) = 1.4089
squareRoot(8.4973) = 2.915
squareRoot(4.5142) = 2.1247
squareRoot(12.0452) = 3.4706
squareRoot(6.3649) = 2.5229
squareRoot(15.6959) = 3.9618
squareRoot(9.8579) = 3.1397
squareRoot(2.4609) = 1.5687
squareRoot(8.8883) = 2.9813
squareRoot(8.145) = 2.854
squareRoot(12.9075) = 3.5927
squareRoot(6.6506) = 2.5789
squareRoot(19.7494) = 4.444
squareRoot(14.2949) = 3.7809
squareRoot(4.6301) = 2.1518
squareRoot(26.8343) = 5.1802
squareRoot(22.0154) = 4.6921
squareRoot(5.6844) = 2.3842
squareRoot(16.0184) = 4.0023
squareRoot(29.2209) = 5.4056
squareRoot(0.7095) = 0.8423
squareRoot(27.9501) = 5.2868
squareRoot(4.8855) = 2.2103
squareRoot(23.0454) = 4.8006
squareRoot(3.035) = 1.7421
squareRoot(35.6296) = 5.9691
squareRoot(34.8588) = 5.9041
squareRoot(30.7325) = 5.5437
squareRoot(13.2792) = 3.6441
squareRoot(38.3847) = 6.1955
squareRoot(41.006) = 6.4036
squareRoot(32.0239) = 5.659
squareRoot(26.3993) = 5.138
squareRoot(22.0394) = 4.6946
squareRoot(33.8697) = 5.8198
squareRoot(21.2756) = 4.6125
squareRoot(14.3281) = 3.7852
squareRoot(6.3561) = 2.5211
squareRoot(39.7245) = 6.3027
squareRoot(30.8754) = 5.5566
squareRoot(7.8828) = 2.8076
squareRoot(20.9994) = 4.5825
squareRoot(28.8414) = 5.3704
squareRoot(16.1088) = 4.0136
squareRoot(18.0775) = 4.2518
squareRoot(47.9229) = 6.9226
squareRoot(16.7141) = 4.0883
squareRoot(4.0523) = 2.013
squareRoot(14.8709) = 3.8563
squareRoot(8.6993) = 2.9495
squareRoot(22.8106) = 4.776
squareRoot(33.4576) = 5.7843
squareRoot(6.1761) = 2.4852
squareRoot(35.3567) = 5.9462
squareRoot(16.7111) = 4.0879
squareRoot(18.3519) = 4.2839
squareRoot(28.5795) = 5.346
squareRoot(57.3288) = 7.5716
squareRoot(53.7363) = 7.3305
squareRoot(44.4702) = 6.6686
squareRoot(14.8888) = 3.8586
squareRoot(30.4234) = 5.5157
squareRoot(8.6019) = 2.9329
squareRoot(70.9029) = 8.4204
squareRoot(19.6337) = 4.431
squareRoot(53.5202) = 7.3157
squareRoot(19.5097) = 4.417
squareRoot(27.7449) = 5.2673
squareRoot(43.2035) = 6.5729
squareRoot(58.2615) = 7.6329
squareRoot(11.6508) = 3.4133
squareRoot(58.3047) = 7.6358
squareRoot(75.6846) = 8.6997
squareRoot(37.5626) = 6.1288
squareRoot(17.6025) = 4.1955
squareRoot(25.8419) = 5.0835
squareRoot(31.9104) = 5.6489
squareRoot(17.5827) = 4.1932
squareRoot(23.8006) = 4.8786
squareRoot(23.0846) = 4.8046
squareRoot(90.9952) = 9.5391
squareRoot(79.1141) = 8.8946
squareRoot(20.407) = 4.5174
squareRoot(74.1938) = 8.6136
squareRoot(19.9565) = 4.4673
squareRoot(4.4215) = 2.1027
squareRoot(71.7229) = 8.4689
squareRoot(56.6333) = 7.5255
```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: