There are various questions on this forum that appear similar, but my question pertains to writing code that can compute the $n^{\text{th}}$ root of a number $a$ correct to $p$ decimal places, where the value of $p$ is limited by the machine representation (but is unbounded in principle). I've implemented a straight-forward algebraic approach in Python. Without loss of generality, let's say we wish to compute the square root of $2$ to $10$ decimal places.
This is equivalent to finding the root of the equation $P_0(x) = -2 + x^2 = 0$, using only integers. Using binary search, I find the largest integer $r_0$ such that $P_0(x=r_0) \leq 0$. Then $r_0$ comprises the whole number part of the answer. To find the first decimal place, we substitute the variable $x$ in $P_0$ with $r_0 + x/10$. We get the equation $P_1(x) = -2 + (r_0 + x/10)^2 = 0$. Again, using binary search, compute the largest integer $r_1$ (actually $0 \leq r_1 \leq 9$) such that $P_1(x=r_1) \leq 0$. And so on we go, each time substituting $x$ with $r_i + x/10$ to find the $(i+1)^\text{th}$ decimal place. The problem is, that the coefficients of the resulting quadratic equations $P_i$ explode. E.g.
$P_0(x) = -2 + x^2 = 0$, "root" $r_0 = 1$
$P_1(x) = -100 + 20x + x^2 = 0$, "root" $r_1 = 4$
$P_2(x) = -400 + 280x + x^2 = 0$, "root" $r_2 = 1$
$P_3(x) = -11900 + 2820x + x^2 = 0$, "root" $r_3 = 4$
$\ldots$
$P_{10}(x) = -105527215600 + 28284271240x + x^2 = 0$, "root" $r_{10} = 3$
Eventually, the coefficients would be too large to be represented on a computer (although my laptop running Anaconda 4.0.0 64-bit distribution has produced $\sqrt{2}$ to $10000$ decimal places w/o a problem).
My question is: Is there a way to approximate the coefficients for the quadratic equations, to keep them within certain bounds, and still continue to obtain subsequent digits correctly? In particular, is there a counter-example which shows that nothing but the exact coefficients would yield the correct results? Does it help to know that the "root" $r_i$ of each quadratic equation $P_i$, $i > 0$, lies between $0$ and $9$?