How does the square root function work?

(Newer (and better) version of this post: Newton's Method)

I was doing some experimenting in Python, and I noticed that n ** .5 was much slower than math.sqrt(n). I made the computer calculate the square root of all the numbers 0 to 999 (inclusive) (Code below)

from timeit import timeit
def sqrtfunction():
    from math import sqrt
    g = list(range(1000))
    g = list(map(sqrt, g))
def regfunction():
    g = list(range(1000))
    g = list(map(lambda x: x ** .5, g))
print(timeit("regfunction()", "from __main__ import regfunction", number = 10000))
print(timeit("sqrtfunction()", "from __main__ import sqrtfunction", number = 10000))

The result was that the square root function was more than two times faster than x ** .5. What this means is the algorithm is much faster for calculating the square root, than calculating a fractional power, which is pretty much a given.

Logically, I used the "inspect" module, and did inspect.getsource(math.sqrt). However, it yielded an error, and I couldn't find out how they did it.

So, I began looking at square root algorithms and I found a good one: Newton's  Method of Approximation

What it does is it begins with an initial guess, and it finds the average between the guess and the number/ guess. It does that over and over again, iterating for 100 times, but usually arriving at the square root within 10 iterations. The code looks something like this:

def squareroot(x):
    guess = x/2 (random guess, better than 0)
    for i in range(25): #number of iterations
        guess = (guess + x/guess)/2 
    return guess

Running that function on 100, it returns 10 after 9 iterations. It continues staying small, as finding the square root of 17000 only takes 13 iterations. The first time power of 10 that had a noticeable difference after 25 iterations was 100000000000000, or 10^14 (difference between squareroot(10 ** 14)^2 and 10 ** 14 was around 700,000). With 50 iterations, squareroot(10^15)^2 and 10^15 had a difference of 0.125. However, at larger powers, such as 10^24 to 10^28, there's virtually no difference. After 10^29, it is consistently off, so that would be the cap at which it works.

So, to summarize:
25 iterations works up to 10^14, whereas 50 iterations works up to 10^29. 

The major problem with this is it's slow. It's takes  0.13158402500084776 seconds with the math.sqrt function while the squareroot function from above takes 4.827450188000512 seconds.

That's 36.68 times slower, so although it works well, it takes a lot longer. So, although I highly doubt they use this method, although it'd be faster in C, I think this is a very good and simple method, and it is one you could even do in your head to estimate the square root of a number.

-David Witten