# Importing required python libraries
import math
import numpy as np

def fun(x):
  val = x**4-14*x**3+60*x**2-70*x
  return val

#Fibonacci Function
def fibonacci(n):
  f0=0
  f1=1
  #Initialize an empty array
  arr = [0]*n
  arr[0]= 0
  arr[1]= 1
  for i in range(2,n):
    arr[i]=arr[i-1]+arr[i-2]
  return arr[1:]

# Fibonacci search Method 
def fibonacci_search(a,b,eps):
  
    ''' The number of iterations needed to reach the given range between two values,i.e|a-b|< epsilon
         (1+2*epsilon)^/F_(n+1) <= 0.3(final range)/2(given initial range)'''

    N = math.ceil((1+2*eps)/(0.3/(b-a)))
  
    arr = fibonacci(N+1)
    #Comparing the value of N, in our fibonacci sequence

    for i in range(0,len(arr)):
      if arr[i] >= N:
        N=i-1  #because F_(N+1)>= N, so value of iteration N, will be less than N+1.
        break
    
    print("We need :",N,"iteration to reach within the given range")
  
    ''' We will use iteration to arrive at the required range.
      Since, for the first time we need to calculate 2 evaluation points, we will keep the first iteration 
      out of the iteration look'''
    #Iteration : 1
    ro = 1 - (arr[N]/arr[N+1])
    a1 = a + ro*(b-a)
    b1 = a + (1-ro)*(b-a)
    f1= fun(a1)
    f2 = fun(b1)

    for i in range(1,N+2):
      if abs(a-b) <= 0.3:
        print("The final range between a & b : ",abs(b-a),"\t")
        break
      f1= fun(a1)
      f2= fun(b1)
      ro = 1 - (arr[N-i]/arr[N+1-i]) # recalculating the value of rho, for every interval
      if ro == 0.5: #special case for the last iteration being handled in this if clause.
        if f1 <= f2:
          b = b1
          b1 = a1  
          print("a:",a,"b:",b,"\t")
          print("Iteration :",i,"f1: ",f1," f2: ",f2,"\t")
          a1 = a + (ro-eps)*(b-a) 
        else:
          a = a1
          a1 = b1
          print("a:",a,"b:",b,"\t")
          print("Iteration :",i,"f1: ",f1," f2: ",f2,"\t")
          b1 =  a + (ro+eps)*(b-a)
      else:  # for rest of the iterations before the last iteration, the following steps are executed.
        if f1 <= f2:
          print("a:",a,"b:",b,"\t")
          print("Iteration :",i,"f1: ",f1," f2: ",f2,"\t")
          b=b1
          b1=a1
          a1 = a + ro*(b-a) 
        else:
          print("a:",a,"b:",b,"\t")
          print("Iteration :",i,"f1: ",f1," f2: ",f2,"\t")
          a = a1
          a1 = b1
          b1 =  a + (1-ro)*(b-a)