Fast square roots I need to compute the square roots of lots of numbers. The numbers increase monotonically by fixed step. For example, 1, 2, 3, ..., 1 000 000.
What is the fastest way to do so? Is it possible somehow to take the advantage of the growth and calculate the square roots incrementally?
I thought I would calculate the derivative and add it at each step. But the derivative contains again a square root so it doesn't help. Also, I don't mind to trade some precision for speed.
 A: I'd suggest to calculate the square root $s_k\stackrel!=\sqrt{a_k}$ by using $s_{k-1}+(s_{k-1}-s_{k-2})$ as an initial value for the iteration $x_{n+1}=(x_n+a_k/x_n)/2$.
A: Here's a neat way to compute the next square root once the numbers are large.  Let $s_n=\sqrt{n}$ be the previous value you computed and then use the Taylor expansion
$$ s_{n+1}=\sqrt{n}\sqrt{1+1/n}=s_n\sqrt{1+1/n}=s_n\left(1+\frac{1}{2n}-\frac{1}{8n^2}+\frac{1}{16n^3}-\frac{5}{128n^4}+\cdots\right)
$$
For example for $n=100$ the first three terms give you six correct digits.  For binary arithmetic note the convenient powers of two in the denominators.  The error will accumulate from one term to the next, but if we correct the answer in the cases $s_{m^2}=m$, then the error can't get too out of hand.  Also note that anytime $n$ is not a prime, say $n=kl$ you can of course use $s_n=s_ks_l$ to compute the square root.  I would at least do this for all even numbers, and then perhaps the odd numbered ones could be computed using the formula above.
I have another idea for how to make it faster using a rational approximation instead of a Taylor approximation, but I will need some time to work out the details.
A: Another approach: approximate the square root function by a polynomial, or maybe a rational function. The degree will depend on what accuracy you need and over how wide an interval. Calculating a good approximation is not easy, but you only have to do it once. If any of your numbers are close to zero, a polynomial won't work very well, so you'll have to use a rational approximation.
If your input numbers are in an arithmetic sequence (some constant step between each consecutive pair), then you can calculate values of the polynomial very quickly by forward differencing.
I'm not sure that this approach is any better than the other one suggested. Depends on what sort of hardware you have, what accuracy you require, etc.
A: As promised, here is another way to compute the square root using rational approximations.  The method converges as fast as Newton's method, but is not as well known.  I read about this in AMS monthly, but unfortunately I don't remember the issue or authors.  If anyone has a pointer to the article that would be great.  Let's use the formula 
$$
\sqrt{n+1}=\frac{n}{\sqrt{n-1}} \sqrt{1-1/n^2}
$$
as a starting point.  If $\sqrt{n-1}$ is known, we only need to compute $\sqrt{1-1/n^2}$.  Let's take $x=-1/n^2$ and let's try to find a fraction $(a+bx)^2/(c+dx)^2$ that is close to $1+x$.  It can be checked that 
$$
\frac{(4+3x)^2}{(4+x)^2}=1+x-\frac{x^3}{16}+\frac{x^4}{32}+\cdots=1+x+\mathcal{O}(x^3)
$$
does the trick.
Therefore we have
$$
\sqrt{1+x}=\frac{4+3x}{4+x}\sqrt{(1+x)\frac{(4+x)^2}{(4+3x)^2}}=\frac{4+3x}{4+x}\sqrt{1+\frac{x^3}{(4+3x)^2}}
$$
We can now repeat the whole procedure again by using $\frac{x^3}{(4+3x)^2}$ in place of $x$.
Thus we take $x_1=-1/n^2$, $x_2=x_1^3/(4+3x_1)^2$ and we get
$$ \sqrt{1-\frac{1}{n^2}}\approx \frac{(4+3x_1)(4+3x_2)}{(4+x_1)(4+3x_2)}
$$
and the error is already of order $\mathcal{O}(n^{-18})$, which for $n=10$ should be enough to reconstruct the square-root to double precision.  Even the first term $\frac{4+3x_1}{4+x_1}$ is probably pretty good for practical purposes.
