Designing a Sqrt function in Python

Question

This is a bit of an academic exercise. I'm implementing a sqrt function in Python. Here's my code,

def mySqrt(x):
    low, high = 1, x
    while low < high:
        mid = low + (high - low)/2
        if mid * mid > x:
            high = mid - 1
        elif mid * mid < x:
            low = mid
        else:
            return mid
    return low

The issue is that this doesn't work when the number isn't a perfect square. I want to redesign this function still using the log n complexity which would return the value of the sqrt to a specified number of decimal places. So it's something like,

def sqrt(num, param):
    pass

thus

sqrt(5, 2) = 2.41
sqrt(5, 3) = 2.414 

Can someone help me with this. Thanks.

Answer 1

You could use the Babylonian method.

def sqrt(x):
    n = 1
    for _ in range(10):
        print(n)
        n = (n + x/n) * 0.5

It converges extremely fast. Here's an example for sqrt(2):

1
1.5
1.41666666667
1.41421568627
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237

for sqrt(3):

1
2.0
1.75
1.73214285714
1.73205081001
1.73205080757
1.73205080757
1.73205080757
1.73205080757
1.73205080757

Now you just need to replace the for loop with a while and a precision condition and return the result instead of just printing it.

Answer 2

You can try Newton's Method to find square root

#!/usr/bin/env python
def ntsqrt(n):
    sgn = 0
    if n < 0:
        sgn = -1
        n = -n
    val = n
    while True:
        last = val
        val = (val + n / val) * 0.5
        if abs(val - last) < 1e-9:
            break
    if sgn < 0:
        return complex(0, val)
    return val

if __name__ == "__main__":
    print ntsqrt(25.0)

The above prints successfully the exact square root 5.0 and the values for each iteration go something like this:

  5.00000000005