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

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

下面的代码用牛顿迭代法解决这个问题。因为输入和输出都是整数,所以只要前后两项相差小于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,后来发现不行,迭代次数过多后,如果分子分母约分约不下去,就溢出了。

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

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥