Designing a Sqrt Function in Python

Question

This is a bit of an academic exercise. I am implementing the sqrt function in Python. Here is 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 problem is that this does not work when the number is not a perfect square. I want to reverse engineer this function using log n complexity, which will return the sqrt value to the specified number of decimal places. So something like

def sqrt(num, param):
    pass

In this way,

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

Can someone help me with this. Thank.

Answer 1

You can use the Babylonian method.

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

It converges very quickly. Here is 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 cycle forwith whilethe accuracy condition and return the result, and not just print it.

Answer 2

Newton Method,

#!/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)

5.0, :

  5.00000000005

Answer 3

def sqrt(num, param):
    return float(str(num**0.5)[:param+len(str(num).split("."))+1])

You can do it with 1/2 power