Originally posted by LittleBear
If only I could remember how to get the square root of a number using only paper and pencil... :'(
For square root, I recommend using the "Divide and Average" algorithm. It has quadratic convergence (ie, it smokes), and it can be generalized for nth root. From what I see in the algorithms presented here, they seem to have linear convergence (ie, they're slow).
Here's Divide and Average.
Say you want to find the square root of the number k.
Set X(0) to be a guess of the square root of k.
Now, set X(n+1) = (1/2)*(X(n)+(k/(X(n))).
Another good thing about Divide and Average is that if you make a mistake, your mistake gets smaller, and smaller with every iteration. With linear convergence methods, if you make a mistake, your results are worthless, regardless of how far you carry the calculation after your mistake. With Divide and Average, you can make a mistake at every step, and each mistake gets damped more and more, as you iterate, so you always approach the answer you are interested in.