#!/usr/bin/env python
# coding: utf-8

# # Newton method for square root

# Consider the function
# $$
# f(x) = x^2 - a
# $$
# The roots are $\pm \sqrt{a}$. The Newton method is
# $$
# x_{n+1} = \frac{1}{2} \left( x_n + \frac{a}{x_n} \right)
# $$

# In[15]:


from math import sqrt
a = 2.0
r = sqrt(a)


# Define the function and its derivative.

# In[16]:


def f(x):
    return x**2 - a

def df(x):
    return 2.0*x


# Now implement Newton method as a function.

# In[17]:


def newton(f,df,x0,M=100,eps=1.0e-15):
    x = x0
    for i in range(M):
        dx = - f(x)/df(x)
        x  = x + dx
        print('%3d %20.14f %20.14e %20.14e'%(i,x,x-r,abs(f(x))))
        if abs(dx) < eps * abs(x):
            return x
    print('No convergence, current root = %e' % x)


# We call Newton method with a complex initial guess for the root.

# In[18]:


x0 = 2.0
x = newton(f,df,x0)


# From the last column, we observe that in each iteration, the number of correct decimal places doubles.