用牛顿迭代法求整数的平方根

   这是一个挺常见的面试题，解法也五花八门。

   下面的代码用牛顿迭代法解决这个问题。因为输入和输出都是整数，所以只要前后两项相差小于1，就可以终止了

int sqrt(int x) {
  if (x < 0) abort();
  if (x == 0) return 0;
  if (x == 1) return 1;
  double t = x >> 1;
  t = (t + x / t) / 2;
  while (true) {
    double v = (t + x / t) / 2;
    if (fabs(v - t) < 1) {
      t = v;
      break;
    }
    t = v;
  }
  t=floor(t);
  if (t * t > x) t--;
  return t;
}

   我本来想用有理数运算来代替double，后来发现不行，迭代次数过多后，如果分子分母约分约不下去，就溢出了。

   上面这段代码其实也就只能应付面试，实际有很多比这个更优的方案，比如打表。