Algorithm faster than Newton's for calculating $\sqrt{2}$

Question

It is well known that the iteration scheme

$$ x_{n+1} = \frac{1}{2} (x_n + \frac{2}{x_n })$$

converges to $\sqrt{2}$ very fast. More precisely, it converges quadratically. The problem is, is there any even faster algorithm? Namely, can we find another polynomial $P(x, 1/x)$ of $x$ and $1/x$ with rational coefficients, such that the iteration scheme

$$x_{n+1} = P \left(x_n , \frac{1}{x_n} \right)$$

converges even faster?

The conjecture is that no such algorithm exists. But I have no idea how to prove it.

Answer 1

Here's one that converges faster (fewer steps), at least in a certain range:

$x_{n+1}=-{1\over32}x_n^3+{5\over8}x_n+{7\over8}{1\over x_n}$

That has the desired properties of $P(\sqrt 2)=\sqrt 2$ and a local minimum at $x=\sqrt 2$:

It can be seen that the curve (and thus the iterates starting from $x < 3$ anyway) is closer to $\sqrt 2$ than the Newton curve.

The ratio of first seven iterates to $\sqrt 2$, starting from $x=3$:

new&improved      Newton
2.121320343559642 2.121320343559642
0.935443345944703 1.296362432175337
1.001184535464119 1.033875824007604
1.000000349950901 1.000554985146933
1.000000000000031 1.000000153918834
1.000000000000000 1.000000000000012
1.000000000000000 1.000000000000000

Of course, it's only about one step ahead, and there's the additional cost of the cube factor