# this file available at: https://arachnoid.com/files/python01/
from typing import Tuple

# see https://en.wikipedia.org/wiki/Newton%27s_method

def newton_root_debug(x: float, debug: bool = False) -> Tuple[float,int]:
    """
    Newton's method for finding square roots. Returns
    x**(1/2) and the number of iterations required.
    """
    if debug:
        print(f'{"x =":<3s} {x:2.1f}')
        print(f'\t{"i":>3s} {"r":^19s} {"abs(x-r*r)":^12s}')
        print(f'\t{"-" * 46}')
    r: float = x / 2.0
    i: int = 0
    epsilon : float = 1e-14
    od = 0
    while True:
        d : float = r*r - x
        ad = abs(d)
        if ad <= epsilon or abs(od) == ad or i >= 16: break
        od = d
        r -= d/(2*r)
        i += 1
        if debug:
            print(f'\t{i:3d} {r:19.16f} {abs(x-r*r):12.8e}')
    # return result and iteration count
    return (r,i)

def newton_root(x: float) -> float:
    """
    Newton's method for finding square roots
    Returns x**(1/2) 
    """
    r : float = x / 2.0
    epsilon : float = 1e-14
    od = 0
    for _ in  range(17):
        d : float = r*r - x
        ad = abs(d)
        if ad <= epsilon or od == ad: break
        od = ad
        r -= d/(2*r)
    return r

def main():
    fwidth = 19
    debug = False
    if debug:
        top = 9
    else:
        top = 33
        print(f'{"x":^4s} {"x**(1/2)":^{fwidth}s} {"newton(x)":^{fwidth}s} {"error":^10}')
        print('-' * 60)
    for x in range(2,top):
        ya : float = x**(1/2)
        yb = newton_root(x)
        if not debug:
            print(f'{x:>4.1f} {ya:{fwidth}.16f} {yb:{fwidth}.16f} {abs(yb-ya):>10.3e}')

if __name__ == "__main__":
    main()