#################################################################################
############# Exercice 1 ###############################################################
########################################################################################

#####Question (a)######################################

print("--------------Exercice 1 ------------------\n \n \n ")

##we apply directly the inductive formula. 

### memory consumption m(n) = m(n-1) + m(n-2) + 2*24 
### m(n) = O( l^n).

#### complexity c(n) : number of additions, multiplications
## = c(n-1) + c(n-2) + 3
### c(n) = O(l^n) exponential complexity
def rec_sequence(n):
    if((n==0) or (n==1)):
        return 1
    else:
        return 3*rec_sequence(n-1) + 2 * rec_sequence(n-2)
        
print("\t question (a)\n\n")

print("S_0 is " + str(rec_sequence(0)))        

print("S_1 is " + str(rec_sequence(1)))
print("S_2 is " + str(rec_sequence(2)))
print("S_3 is " + str(rec_sequence(3)))
print("S_4 is " + str(rec_sequence(4)))



print("\t Question (b) \n\n")


########################question (b)########################################
############ Complexity O(n)#########################
############# memory consumption: u,v,p, value = 4* 24bytes.



def for_sequence(n):
    if((n==0) or (n==1)):
        return 1
    else:
        ## initialize u=u{p-1}, v= u_{p-2}
        u=1
        v=1
        value=0
        ## we compute u_p stored in value for p between 2 and n
        for p  in range (2, n+1):
            value=3*u + 2* v
            ## on the next loop we will compute u_{p+1 }, so we need to initialize u to u_p and v to u_{p-1}
            ### here we first assign v the value of u, then u to value
            v=u
            u=value
        return value    

print("S_0 is " + str(for_sequence(0)))        

print("S_1 is " + str(for_sequence(1)))
print("S_2 is " + str(for_sequence(2)))
print("S_3 is " + str(for_sequence(3)))
print("S_4 is " + str(for_sequence(4)))



####################################Exercice 2##########################################
#####################################################################################

print("---------------------\n Exercice 2 \n\n\n\n")

from math import *

def usual_sqrt(a):
    if (a< 0):
        print ("Error ")
        return -1
    else:
        return sqrt(a)    

print("The sqrt using the standard math library gives sqrt(2) = "+ str(usual_sqrt(2)))


complexity_newton=0

## temp stores the value u_n of the sequence in the newton method
## we assume that a>0 already.
## we assume that epsilon>0 already 
def rec_newton_sqrt(a, epsilon, temp):            
    ## compute the difference and compare with epsilon, 
    if(abs(a -(temp*temp)) <= epsilon):
        ## smaller we are done, temp stores the square root up to sqrt(epsilon)
        return temp
    else:
        ### still larger, we iterate the newton method
        new_value= temp - ( (temp*temp ) - a)/ (2* temp)
        global complexity_newton
        ## increment
        complexity_newton+=1
        return rec_newton_sqrt(a, epsilon, new_value)



def newton_sqrt(a, epsilon):
    if (a< 0):
        print ("Error ")
        return -1
    if (epsilon <=0):
        print("Error The precision epsilon is non-positive")
        return -1
    ## to count the complexity, we set the complexity to zero at the start. 
    global complexity_newton
    complexity_newton=0    
    ## note that our comparison takes the squares, so iff we want the sqrt uup to a precision epsilon, the squres must be at a precision epsilon^2.    
    return rec_newton_sqrt(a,epsilon*epsilon, a )    
        
print("Our custom sqrt function using the newton method gives sqrt(2)= "+ str(newton_sqrt(2,0.0001)) + " up to a precision 0.0001" )


print("Our custom sqrt function using the newton method gives sqrt(13)= "+ str(newton_sqrt(13,pow(0.1,7))) + " up to a precision 10^{-7}" )
print("To compute this, we applied the newton method "+str(complexity_newton)+ " times")