連分数展開で 2 の平方根を求める

mathmatics

$x^{2} = 2$ とする。

\begin{aligned}
x &= 1 + x - 1 \\
  &= 1 + \frac{1}{\frac{1}{x - 1}} \\
  &= 1 + \frac{1}{\frac{1 + x}{(x - 1)(x + 1)}} \\
  &= 1 + \frac{1}{\frac{1 + x}{x^2 - 1}} \\
  &= 1 + \frac{1}{1 + x} \\
\end{aligned}

$x = 1 + \frac{1}{1 + x}$ を再帰的に代入する。

\begin{aligned}
x &= 1 + \frac{1}{1 + x} \\
  &= 1 + \frac{1}{1 + 1 + \frac{1}{1 + x}} \\
  &= 1 + \frac{1}{2 + \frac{1}{1 + x}} \\
  &= 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{1 + x}}} \\
  &= 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{1 + x}}}} \\
\end{aligned}
#include <iostream>

double sqrt_2(double x, int nb_iters) {
    x = 1.0 / (1.0 + x);
    for (int i = 0; i < nb_iters; ++i) {
        x = 2.0 + 1.0 / x;
    }
    return 1.0 + 1.0 / x;
}

int main()
{
    for (int n = 0; n < 10; ++n) {
        std::cout << n << ": " << sqrt_2(0, n) << '\n';
    }
    std::cout << std::flush;
    return 0;
}