Square root function hyperbolic estimator

Question

According to this article, the following formula gives a good approximation for the square root function $$ {\displaystyle {\sqrt {S}}\approx \left({\frac {-190}{a+20}}+10\right)\cdot 10^{n}} $$

Where $S = a\times 10^{2n} $

Unfortunately there is no explaination where the numbers -190, 20 and 10 come from. I have played around with this a little bit, trying to create a similar estimate for base 8 instead of base 10, because I'm trying to implement an efficient square root function and powers of two are nicer to deal with than powers of ten. Can anyone explain where the constants come from?

Answer 1

Notice that if $S = a \cdot 10^{2n}$, then $\sqrt{S} = \sqrt{a} \cdot 10^n$, so the formula given is just giving an approximation for $\sqrt{a}$ and scaling it up by a suitable power of 10.

As for the approximation, which is $\sqrt{a} \approx \left(\frac{-190}{a+20} + 10\right)$, given the article's description of it as a "near optimal" approximation to the square root function it looks like the method to finding the constants involves setting $x^2 \approx \frac{ax + b}{cx + d}$ and using an optimisation approach to minimise the error of the approximation on the range $x \in [1, 100]$. This might have involved an exact calculation of the optimal coefficients followed by a rounding step, or it might have involved a few simplifications and/or linearisations, or even just some basic trial and error.

Answer 2

In terms of approximations, many things can be done using for example the $[n,n]$ Padé approximant around $a=49$ to avoid radicals.

The simplest would be $$P_1=\frac {7+\frac{3}{28} (a-49) } {1+\frac{1}{196} (a-49) }=\frac{7 (3 a+49)}{a+147}$$ which is better than the approximation you refer to.

We could even do better minimizing the norm $$\Phi=\int_0^{100} \left(\sqrt a - \frac{\alpha \,a+\beta}{a+\gamma }\right)^2 \,da$$

Writing $$\frac {\partial \Phi}{\partial \alpha}=\frac {\partial \Phi}{\partial \beta}=\frac {\partial \Phi}{\partial \gamma}=0$$ we have explicit expressions of $\alpha$ and $\beta$ as functions of $\gamma$.

What remains is a nasty equation in $\gamma$. Using a root-finder and making the results rational $$\alpha=\frac{3995}{237}\qquad \beta=\frac{27205}{249}\qquad \gamma=\frac{15241}{184}$$

These values give $\Phi_{\text{min}}=1.6691$ while $P_1$ leads to $\Phi=9.2381$. (which is $5.6$ times larger).

We can improve using $$P_2=\frac {7 (5 a^2+490 a+2401)} { a^2+490 a+12005}$$ $$P_3=\frac {49 (a^3+245 a^2+7203 a+16807)} {a^3+1029 a^2+84035 a+823543 }$$ and so on.

Edit

For finding the zero of function $$f(x)=x^2-a$$ using the first iteration of Newton method $$x_0=\frac{7 (3 a+49)}{a+147}\quad \implies \quad x_1=\frac{(a+49) \left(a^2+686 a+2401\right)}{14 (a+147) (3 a+49)}$$ which reduces the infinite norm by a factor of $14.5$.

Update

Better is to use $a=36$ to get $$P_1=\frac{18 (a+12)}{a+108}$$ for which $\Phi=4.0434$.

Then $$x_0=\frac{18 (a+12)}{a+108}\quad \implies \quad x_1=\frac{(a+36) \left(a^2+504 a+1296\right)}{36 (a+12) (a+108)}$$ for which the norm is $0.0823$