# goldSrch.py
# https://en.wikipedia.org/wiki/Golden-section_search

"""
  Golden section search to find the maximum of fn on [x1,x3]
  fn: x1 strictly unimodal function on [x1,x3]

This implementation does not reuse function evaluations and assumes the maximum is x2 or x4, and not on the edges at x1 or x3)
"""

import math

EPS = 1e-10
PHI = (math.sqrt(5) + 1) / 2

def goldSrch(fn, x1, x3):
  while abs(x3-x1) > EPS:
    x2 = x3 - (x3-x1)/PHI
    x4 = x1 + (x3-x1)/PHI
    if fn(x2) > fn(x4):  
      # use < to find a minimum
      x3 = x4
    else:
      x1 = x2
  return (x3+x1)/2

fn = lambda x: 1 - ((x-2)**2)
xMax = goldSrch(fn, 1, 5)
print(f"Maximum x: {xMax:.8f}")