求平方根

sqrt.java

/*
* 求一个数的平方根
* @param c: 数
* @return 该数的平方根
*/
public static double sqrt(double c) {
 double err = 1e-15; //  误差因子
 double t = c;       //  随便猜一个近似值 t
 while (Math.abs(t - c/t) > err * t) {
   t = (c/t + t) / 2.0; 
 }
  return t;
}

原理.md

求 c 的 sqrt，其实是求方程 x^2 - c = 0，x 的根，这个方法其实是牛顿迭代法( https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95 )： 演示图( https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95#/media/File:NewtonIteration_Ani.gif )

Xn 在 f(x) 处的切线 y-f(Xn) = f'(Xn)(X-Xn)，当y = 0 时，解得

• X = -f(Xn)/f'(Xn) + Xn
• 下一个 Xn 的值为 X
  • X(n+1) = Xn - f(Xn)/f'(Xn)
  • 最终 X(n+1) 无限趋近 方程的解

方程为x^2 - c = 0

f'(Xn) = 2

X(n+1) = Xn - f(Xn)/f'(Xn) = Xn - (Xn^2 - c) / 2Xn = 1/2 (Xn + a/Xn)

迭代公式为 X(n+1) = (Xn + a/Xn) / 2

leetcode：https://leetcode-cn.com/problems/sqrtx/