How do you write your own function for finding the most accurate square root of an integer?
After googling it, I found this (archived from its original link), but first, I didn't get it completely, and second, it is approximate too.
Assume square root as nearest integer (to the actual root) or a float.
Depending on your needs, a simple divide-and-conquer strategy can be used. It won't converge as fast as some other methods but it may be a lot easier for a novice to understand. In addition, since it's an O(log n) algorithm (halving the search space each iteration), the worst case for a 32-bit float will be 32 iterations.
Let's say you want the square root of 62.104. You pick a value halfway between 0 and that, and square it. If the square is higher than your number, you need to concentrate on numbers less than the midpoint. If it's too low, concentrate on those higher.
With real math, you could keep dividing the search space in two forever (if it doesn't have a rational square root). In reality, computers will eventually run out of precision and you'll have your approximation. The following C program illustrates the point:
#include <stdio.h>
#include <stdlib.h>
int main (int argc, char *argv[]) {
float val, low, high, mid, oldmid, midsqr;
int step = 0;
// Get argument, force to non-negative.
if (argc < 2) {
printf ("Usage: sqrt <number>\n");
return 1;
}
val = fabs (atof (argv[1]));
// Set initial bounds and print heading.
low = 0;
high = mid = val;
oldmid = -1;
printf ("%4s %10s %10s %10s %10s %10s %s\n",
"Step", "Number", "Low", "High", "Mid", "Square", "Result");
// Keep going until accurate enough.
while (fabs(oldmid - mid) >= 0.00001) {
oldmid = mid;
// Get midpoint and see if we need lower or higher.
mid = (high + low) / 2;
midsqr = mid * mid;
printf ("%4d %10.4f %10.4f %10.4f %10.4f %10.4f ",
++step, val, low, high, mid, midsqr);
if (mid * mid > val) {
high = mid;
printf ("- too high\n");
} else {
low = mid;
printf ("- too low\n");
}
It's a common interview question asked by Facebook etc. I don't think it's a good idea to use the Newton's method in an interview. What if the interviewer ask you the mechanism of the Newton's method when you don't really understand it?
I provided a binary search based solution in Java which I believe everyone can understand.
public int sqrt(int x) {
if(x < 0) return -1;
if(x == 0 || x == 1) return x;
int lowerbound = 1;
int upperbound = x;
int root = lowerbound + (upperbound - lowerbound)/2;
while(root > x/root || root+1 <= x/(root+1)){
if(root > x/root){
upperbound = root;
} else {
lowerbound = root;
}
root = lowerbound + (upperbound - lowerbound)/2;
}
return root;
}
You can test my code here: leetcode: sqrt(x)