首页 > 数学相关 > 数论应用 > 巴比伦算法求平方根
2014
04-11

巴比伦算法求平方根

算法描述:
这种方法比较久远了,类似牛顿迭代法。

x^2=n ,给出n 要求x 的值。

1 从一个任意的值x开始(越靠近根越好)。
2 初始化y = 1.
3. 重复一下步骤直到求得近似值:
  a) 取x和y的平均数为下一个近似的根
  b) y = n/x

不管刚开始x,y的相差有多大,最终都会向中间靠拢的,最后 x*y = n。例如 n=50时

x=50   y=1
x=25.5   y=1.96078
x=13.7304   y=3.64156
x=8.68597   y=5.75641
x=7.22119   y=6.92407
x=7.07263   y=7.06951

代码实现:

/*Returns the square root of n. Note that the function */
float squareRoot(float n)
{
  /*使用n作为初始化,其实还有待优化 */
  float x = n;
  float y = 1;
  float e = 0.000001; /* e 确定精度 */
  while(x - y > e)
  {
    x = (x + y)/2;
    y = n/x;
  }
  return x;
}

int main()
{
  int n = 50;
  printf ("Square root of %d is %f", n, squareRoot(n));
  getchar();
}

例子:

n = 4 /*n 被用作初始解 */
Initialize x = 4, y = 1
下一个近似解 x = (x + y)/2 (= 2.500000), 
y = n/x  (=1.600000)
下一个近似解 x = 2.050000,
y = 1.951220
下一个近似解 x = 2.000610,
y = 1.999390
下一个近似解 x = 2.000000, 
y = 2.000000
停止: (x - y) > e .

如果我们可以确定n是完全平方数(解为整数),可以使用下面的方法。对于非完全平方数,程序 会进入死循环

unsigned int squareRoot(int n)
{
  int x = n;
  int y = 1;
  while(x > y)
  {
    x = (x + y)/2;
    y = n/x;
  }
  return x;
}

/* 测试*/
int main()
{
  int n = 49;
  printf (" root of %d is %d", n, squareRoot(n));
  getchar();
}

参考:http://www.geeksforgeeks.org/square-root-of-a-perfect-square/