Binary sorting is something trivial in algorithms – it is trivial, because a lot of people know how to do it, but because even those who claim to be the professors in algorithms and be the wise guys in the area are not able to write it flawlessly. Thus, there was a bug in java.util.Arrays, because someone did not want to test what happens when you search with big values.
Anyhow, in the current article I will present my algorithm for calculation of squared root with a binary search. It is definitely not the best one, but it works somehow:
So what do I do? Simply I define a precision that I want to achieve and in my case it is 0.00001 and I start a binary search to go find the best mid, which fits the following:
|
1 2 3 4 |
if ((mid-precision )>= mid * mid && mid * mid <= (precision+mid)) { break; } |
Once it is found, I simply display it and round the number to 5 digits after the comma. That is all folks. Here comes the code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
using System; class MainClass { public static void Main () { double test = 10000.00; double number = square_root (test); Console.WriteLine ("Calculation of square root {0}",(test)); Console.WriteLine (Math.Round(number,5)); } public static double square_root(double myNumber) { double precision = 0.00001; double low = 0; double high = myNumber; double mid = 0; while ((high - low)>precision) { mid = (double)((low + high) / 2); if ((mid-precision )>= mid * mid && mid * mid <= (precision+mid)) { break; } else if (mid * mid < myNumber) { low = mid; } else { high = mid; } } return mid; } } |
With the special support of C# in Linux! (probably I am the only blogger in the world blogging for C# in Mint and Ubuntu, but I like it… somehow).