Using Newton's method calculate $ \frac{1}{\sqrt{a}} $ without division Suggest algorithm for the numerical calculation $ \frac{1}{\sqrt{a}} \ a > 0 $ without division, use Newton's method. 
My idea is: 
$$ \frac{1}{\sqrt{a}} = (\sqrt{a})^{-1} = a^{-\frac{1}{2}}$$
$$ x = a^{-\frac{1}{2}} \Rightarrow f(x)=x^2 - a^{-1}$$
And next step is calulate $ f'(x)=2x $, but after substitution I got: $$ x_{n+1} = \frac{x_n^2+a^{-1}}{2x_n}$$ And know I still have divion, I guess. Maybe you've better idea on this task?
 A: After using dark magic to make an initial guess $y_0$, the fast inverse square root algoritm essentially approximates $y=1/\sqrt{x}$, $x > 0$, by using the iteration
$$
y_{n+1} = \frac{3}{2}y_n - \frac{1}{2}xy_n^3.
$$
There is no division here, unless you count the multiplication by the constants $3/2$ and $1/2$.
If the limit as $n \to \infty$ exists then it is a solution to  the cubic equation
$$
y = \frac{3}{2}y - \frac{1}{2}xy^3.
$$
Of course the only solutions are $y=0$ and $y=\pm 1/\sqrt{x}$.  We can do some analysis using the standard techniques for discrete dynamical systems to determine when the iteration will converge and to which point.
Let
$$
f(y) = \frac{3}{2}y - \frac{1}{2}xy^3.
$$
Then $f'(0) = 3/2 > 1$, so $y=0$ is an unstable equilibrium of the system.  We also have $f'(1/\sqrt{x}) = 0$, which is $<1$ in absolute value, so that the points $y=\pm 1/\sqrt{x}$ are stable equilibria.
In other words, if $y_0$ is close enough to $\pm 1/\sqrt{x}$ then $y_n$ will converge to $\pm 1/\sqrt{x}$.  We can determine how close we need to be by calculating
$$
f'(y) = \frac{3}{2}\left(1-xy^2\right).
$$
We require $|f'(y)| < 1$ in order for $f$ to be a contraction, and this is equivalent to
$$
-\frac{2}{3} < 1 - xy^2 < \frac{2}{3}.
$$
Rearranging, we end up with
$$
\frac{1}{3x} < y^2 < \frac{5}{3x}.
$$
So, if
$$
\sqrt\frac{1}{3x} < y_0 < \sqrt\frac{5}{3x}
$$
then $y_n \to 1/\sqrt{x}$ as $n \to \infty$, and if
$$
-\sqrt\frac{5}{3x} < y_0 < -\sqrt\frac{1}{3x}
$$
then $y_n \to -1/\sqrt{x}$ as $n \to \infty$.
Like the traditional Newton's method, this iterative scheme also converges quadratically.  If we let $y_n = 1/\sqrt{x} + \epsilon_n$, then the system becomes
$$
\epsilon_{n+1} = -\frac{3\sqrt{x}}{2} \epsilon_n^2 - \frac{x}{2} \epsilon_n^3.
$$
A: Apply Newton's Method to $f(x) = x^{-2} - a$.
