Approximation
The following is a simple and amazingly accurate way to get a rational approximation to square roots:
- To find $\sqrt n$, guess a fraction $p/q$ near $\sqrt n$. (So $nq^2 \approx p^2$).
- Let $a = nq^2 + p^2$.
- Let $b = nq^2 - p^2$.
- $\displaystyle \sqrt n \approx \frac{a - b^2/(2a)}{2pq}$
For accuracy we want $|b|$ to be small, and can usually get it to be 1, without much effort.
Explanation
Start with $s_0=p/q$ and use the Babylonian Method to get a first estimate $$s_1 = \frac{s_0 + n/s_0}{2} = \frac{p^2 + nq^2}{2pq} = \frac{a}{2pq}$$ This excess will always be an overestimate by approximately $$\frac{(s_0 - n/s_0)^2}{2s_1} = \frac{(p^2 - nq^2)^2}{4pqa} = \frac{b^2}{4apq}$$ Subtracting this excess gives the approximation formula.
Problem
I want to get an estimate of (or a bound for) the error of approximation. My guess is it is something like $|p/q-\sqrt n|^4$.
Examples
For $\sqrt 2$ try $p/q=3/2$, $a=7$, $b=1$, $\sqrt 2 \approx \frac{17 - 1/34}{12}$
$\qquad\color{red}{1.41421}356237310 \quad\text{exact}\\ \qquad\color{red}{1.41421}568627451 \quad\text{approximation}$
If instead we start with a better estimate $p/q=7/5$ we get $a=99$, $b=1$ and $\sqrt 2 \approx \frac{99 - 1/198}{70}$, giving a much better accuracy:
$\qquad\color{red}{1.41421356}237310 \quad\text{exact}\\ \qquad\color{red}{1.41421356}421356 \quad\text{approximation}$
For $\sqrt 3$ try $p/q=7/4$, $a=97$, $b=1$, $\sqrt 3 \approx \frac{97 - 1/194}{56}$
$\qquad\color{red}{1.7320508}0756888 \quad\text{exact}\\ \qquad\color{red}{1.7320508}1001472 \quad\text{approximation}$
For $\sqrt 5$ try $p/q=9/4$, $a=161$, $b=1$, $\sqrt 5 \approx \frac{161 - 1/322}{72}$
$\qquad\color{red}{2.236067977}49979 \quad\text{exact}\\ \qquad\color{red}{2.236067977}91580 \quad\text{approximation}$
For $\sqrt 7$ try $p/q=8/3$, ...
$\qquad\color{red}{2.64575131}106459 \quad\text{exact}\\ \qquad\color{red}{2.64575131}233596 \quad\text{approximation}$
For $\sqrt 11$ try $p/q=10/3$, ...
$\qquad\color{red}{3.316624790}35540 \quad\text{exact}\\ \qquad\color{red}{3.316624790}61977 \quad\text{approximation}$
For $\sqrt 13$ try $p/q=18/5$, ...
$\qquad\color{red}{3.60555127546}399 \quad\text{exact}\\ \qquad\color{red}{3.60555127546}653 \quad\text{approximation}$
For $\sqrt 15$ try $p/q=31/8$, ...
$\qquad\color{red}{3.8729833462074}2 \quad\text{exact}\\ \qquad\color{red}{3.8729833462074}5 \quad\text{approximation}$
As an example where $b \ne 1$, for this last example, if we tried $p/q = 27/7$, we would get $a=1464$, $b=6$ giving the answer $\frac{1464 - 36/2928}{378}$ which 3.872983346 3440
$\qquad\color{red}{3.872983346}20742 \quad\text{exact}\\ \qquad\color{red}{3.872983346}34400 \quad\text{approximation}$
If you start with a rational number, use Newton method to generate a more and more accurate rational number.
For example, for $\sqrt{15}$, using as you did $x_0=\frac {31}8$, you will generate numbers $x_n=\frac{a_n}{b_n}$ $$\left( \begin{array}{cccc} n & a_n & b_n & \text{decimal} \\ 0 & 31 & 8 & 3.8750000000000000000 \\ 1 & 1921 & 496 & 3.8729838709677419355 \\ 2 & 7380481 & 1905632 & 3.8729833462074524357 \\ 3 & 108942999582721 & 28128961537984 & 3.8729833462074168852 \end{array} \right)$$
If you start with $x_0=\frac p q$ for $x^2=a$ ($a$ being an integer or a rational number), you have $$x_1=\frac{a q}{2 p}+\frac{p}{2 q}$$ $$x_2=\frac{a p q}{a q^2+p^2}+\frac{a q}{4 p}+\frac{p}{4 q}$$ $$x_3=\frac{1}{8} \left(\frac{16 a p q \left(a q^2+p^2\right)}{a^2 q^4+6 a p^2 q^2+p^4}+\frac{4 a p q}{a q^2+p^2}+\frac{a q}{p}+\frac{p}{q}\right)$$