To answer your first question, consider that $\text{ceil}(\log_{10} a)$ gives you an estimate of the number of digits of $a$. To wit,
$$\log_{10} 15 \approx 1.176$$
$$\log_{10} 156 \approx 2.193$$
$$\log_{10} 5632 \approx 3.751$$
In other words, 5632 is 10 raised to a number that is not quite 4 (since $10^4 = 10000$).
So, when you compute the difference, taking $\log_{10}$ should give you an estimate of the number of digits in the error.
To answer your second question, since the log term has a coefficient of 2, the estimate of the number of digits doubles each time.
There is such a formula: consider
$$\frac{x_n+\sqrt y}{x_n-\sqrt y}=\frac{\frac{x_{n-1}^2+y}{2x_{n-1}}+\sqrt y}{\frac{x_{n-1}^2+y}{2x_{n-1}}-\sqrt y}=\frac{(x_{n-1}+\sqrt y)^2}{(x_{n-1}-\sqrt y)^2}=\left(\frac{x_{n-1}+\sqrt y}{x_{n-1}-\sqrt y}\right)^2.$$
By recurrence,
$$\frac{x_n+\sqrt y}{x_n-\sqrt y}=\left(\frac{x_{0}+\sqrt y}{x_{0}-\sqrt y}\right)^{2^n}.$$
If you want to achieve $2^{-b}$ relative accuracy, $x_n=(1+2^{-b})\sqrt y$,
$$2^n=\frac{\log_2\frac{(1+2^{-b})\sqrt y+\sqrt y}{(1+2^{-b})\sqrt y-\sqrt y}}{\log_2\left|\frac{x_{0}+\sqrt y}{x_{0}-\sqrt y}\right|},$$
$$n=\log_2\left(\log_2\frac{2+2^{-b}}{2^{-b}}\right)-\log_2\left(\log_2\left|\frac{x_{0}+\sqrt y}{x_{0}-\sqrt y}\right|\right).$$
The first term relates to the desired accuracy. The second is a penalty you pay for providing an inaccurate initial estimate.
If the floating-point representation of $y$ is available, a very good starting approximation is obtained by setting the mantissa to $1$ and halving the exponent (with rounding). This results in an estimate which is at worse a factor $\sqrt 2$ away from the true square root.
$$n=\log_2\left(\log_2\left(2^{b+1}+1\right)-\log_2\left(\log_2\frac{\sqrt 2+1}{\sqrt 2-1}\right)\right)
\approx\log_2(b+1)-1.35.$$
In the case of single precision (23 bits mantissa), 4 iterations are always enough. For double precision (52 bits), 5 iterations.
On the opposite, if $1$ is used as a start and $y$ is much larger, $\log_2\left|\frac{1+\sqrt y}{1-\sqrt y}\right|$ is close to $\frac{2}{\ln(2)\sqrt y}$ and the formula degenerates to
$$n\approx\log_2(b+1)+\log_2(\sqrt y)-1.53.$$
Quadratic convergence is lost as the second term is linear in the exponent of $y$.
Best Answer
Hint: start with the fact that $f(x) = x^2-a$ has $\sqrt{a}$ as a root.
Use the Newton's Method formula:
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$
where $f(x_n) = x_n^2-a$ and $f'(x_n) = 2 x_n$.
Plug these into the above equation and the first result is obtained with a little algebra. For the second result, note that
$$\sqrt{a}-x_{n+1} = \sqrt{a}-\frac{1}{2} \left (x_n + \frac{a}{x_n} \right )$$
What you can do here is multiply that last piece out and factor out $-1/(2 x_n)$. What you should get is 3 terms that fit a pattern of a binomial squared. Look at the result you are trying to show to guide you.