牛顿迭代法求平方根
牛顿法可以求一些非线性方程的近似解. 而对于求平方根, 可以将 $y = \sqrt{x}$ 化成方程 $x^2 - a = 0$ 中求 $x$ 的值, $x$ 即为 $a$ 的开根号, 根据牛顿法定义, 可以写出以下程序
1double mysqrt(const double input, double approximation = 1, unsigned int iterations = 8)
2{
3 if (input < 0 || approximation <= 0)
4 {
5 throw std::runtime_error("Input and approximation should bigger than zero.");
6 }
7
8 double y;
9 double k;
10 for (unsigned int i = 0; i < iterations; ++i)
11 {
12 y = approximation * approximation - input;
13 k = 2 * approximation;
14 approximation = -y / k + approximation;
15 //approximation = -(approximation * approximation - input) / (2 * approximation) + approximation;
16 }
17 return approximation;
18}
画成图差不多这样, 是一个不断迭代, 精度越来越高的过程.
实际运行的结果, 在迭了8代的情况, 已经差不多已经到double类型的极限了.