Newton Iteration Sqrt

sqrt.py

def newtonSqrt(n, eps=1e-8):
    """
    - ASSUME    
            f(x) = x^2 - n
            when f(x)=0, x will be the root of n.
    - DEDUCE BY Taylor Series Formula
            f(x) = f(x0) + (x - x0)f'(x0)
    - WHEN f(x)=0
            x = x0 - f(x0)/f'(x0)
            x will be closer to the root than x0
    - DEDUCE
            x(n+1) = xn - f(xn)/f'(xn)
    - SIMPLIFY
            x(n+1) = (xn + n/xn) / 2 
    """
    root = n
    while abs(root**2 - n) > eps:
        lastVal = root
        root = (root + n/root) / 2
        if abs(lastVal - root) <= eps:
            break
    return root
    
    
import random

eps = 1e-5
for i in range(50):
    num = random.randint(1, 1e9)
    print(num)
    assert num - newtonSqrt(num)**2 <= eps, f'failed when newtonSqrt({num})'

print('Accept')