聊聊平方根运算的优化

可能有人连平方根是怎么计算的都不知道，我指的是计算机是怎么计算的。
其实有很多种办法都可以计算平方根，我们一般会用#include <math.h>
那库函数用的是哪种算法呢。
用的是牛顿迭代法，什么是牛顿迭代法？看如下算式

newton.PNG

Gn是什么，是上一次的预估，可以证明，当这个计算被不停迭代的话，结果会无限逼近我们想要的那个。
上一个代码实现：

int isqrt(unsigned x) {
  unsigned x1;
  int s, g0, g1;

  if (x <= 1) return x;
  s = 1;
  x1 = x - 1;
  if (x1 > 65535) {s = s + 8; x1 = x1 >> 16;}
  if (x1 > 255)   {s = s + 4; x1 = x1 >> 8;}
  if (x1 > 15)    {s = s + 2; x1 = x1 >> 4;}
  if (x1 > 3)     {s = s + 1;}

  g0 = 1 << s;               // g0 = 2**s.
  g1 = (g0 + (x >> s)) >> 1; // g1 = (g0 + x/g0)/2.

  while (g1 < g0) {          // Do while approximations
     g0 = g1;                // strictly decrease.
     g1 = (g0 + (x/g0)) >> 1;
  }
  return g0;
}

待续...