开方算法

开方算法依据公式

开平方公式
(a+b)²-a²=b(2a+b)
开立方公式
(a+b)³-a³=b(3a²+3ab+b²)

1.开方作法本原图
2.二项式定理

1.竖式开方法
2.迭代求根法
3.二分法

---

---

牛顿迭代法

---

迭代公式: t = (t+x/t)/2.0

double sqrt(double x) {
  double eps = 1e-12;
  double t = x;
  while (abs(t - x / t) > eps * t) {
    t = (t + x / t) / 2.0;
  }
  return t;
}

double sqrt2(double x) {
  double eps = 1e-12;
  double t = x;
  double lastt;
  do {
    lastt = t;
    t = (t + x / t) / 2.0;
  } while (abs(t-lastt) > eps);
  return t;
}

---

二分法

---

double sqrt3(double x) {
  double eps = 1e-12;
  double left = 0, right = x;
  double m = x;
  double lastt;
  do{
    lastt = m;
    m = (left + right) * 0.5f;
    if (m*m >= x) {
      right = m;
    }
    else {
      left = m;
    }
  } while (abs(m - lastt) > eps);
  return m;
}

---

参考

开方算法
牛顿迭代法