from math import *;


def halveringsmetoden(f, a, b, N, epsilon):
    i = 0
    m = (a + b)/2.0
    abserr = (b-a)/2.0
    m_list = [m];
    while i <= N and abserr > epsilon*abs(m):
        if f(m) == 0:
            a = m
            b = m
        if f(a)*f(m) < 0:
            b = m
        else:
            a = m
        i = i + 1
        
        m = (a + b)/2.0
        m_list.append(m);
        abserr = (b-a)/2.0
    return m, m_list

def sekantmetoden(f, x0, x1, N, epsilon):
    i = 0
    xpp = x0
    xp = x1
    z = x1
    abserr = abs(z)
    
    z_list = [z];
    while i <= N and abserr >= epsilon*abs(z):
        z = xp - f(xp)*(xp - xpp)/( f(xp) - f(xpp) )
        abserr = abs(z - xp)
        xpp = xp
        xp = z
        i = i + 1
        z_list.append(z);
    return z, z_list

def newtons_metode(f, df, x0, N, epsilon):
    i = 0
    xp = x0
    z = x0
    abserr = abs(z)
    z_list = [z]

    while i <= N and abserr >= epsilon*abs(z):
        z = xp - f(xp)/df(xp)
        abserr = abs(z-xp)
        xp = z
        i = i + 1
        z_list.append(z)

    return z, z_list


f  = lambda x: x*x - 2.0
df = lambda x: 2*x
a = 1
b = 2
epsilon = 1e-10
N = 60;


m, m_list = halveringsmetoden(f, a, b, N, epsilon)
zsec, zsec_list = sekantmetoden(f, a, b, N, epsilon)
znew, znew_list = newtons_metode(f, df, b, N, epsilon)

# The rest of this code is only for printing

M1 = len(m_list);
M2 = len(zsec_list);
M3 = len(znew_list);

M = max(len(m_list), len(zsec_list), len(znew_list))

root = sqrt(2);

my_string = '';
for i in range(M):
    my_string += "i: %2d, " % (i); 
    if i < M1:
        my_string += "Halv: %12e, " % (abs(m_list[i]-root)/abs(root));
    if i < M2:
        my_string += "Sek: %12e, " % (abs(zsec_list[i]-root)/abs(root));
    if i < M3:
        my_string += "New: %12e, " % (abs(znew_list[i]-root)/abs(root));

    my_string += '\n' # Add a newline character

print(my_string)