import numpy as np
import math as mt

H = 1e-15

def Norma(_x : np.array) -> float:
    return mt.sqrt(_x[0] ** 2 + _x[1] ** 2)

def Grad(_f, _x : np.array) -> np.array:
    return ((_f((_x[0] + H, _x[1])) - _f((_x[0], _x[1]))) / H, (_f((_x[0], _x[1] + H)) - _f((_x[0], _x[1]))) / H)

def FindMinimum(_f, _x : np.array, _s : np.array, _lamb0 = 0.0):
    h = 0
    lamb = _lamb0
    delt = 1e-8
    if _f(_x + _lamb0 * _s) > _f(_x + (_lamb0 + delt) * _s):
        lamb = _lamb0 + delt
        h = delt
    elif _f(_x + _lamb0 * _s) < _f(_x + (_lamb0 + delt) * _s):
        lamb = _lamb0 + delt
        h = -delt
    else:
        print ("Govno kakoe-to")
        exit
    while True:
        h *= 2
        lamb += h
        if _f(_x + (lamb - h) * _s) <= _f(_x + lamb * _s):
            return np.array([min(_lamb0, lamb), max(_lamb0, lamb)])


def DichotomyMethod(_f, _interval, _x, _s, eps = 1e-7):
    _a = _interval[0]
    _b = _interval[1]
    _x1 = (_a + _b - 0.5 * eps) / 2
    _x2 = (_a + _b + 0.5 * eps) / 2
    while abs(_b - _a) > eps:
        if _f(_x + _x1 * _s) <= _f(_x + _x2 * _s):
            _b = _x2
        else:
            _a = _x1
        _x1 = (_a + _b - 0.5 * eps) / 2
        _x2 = (_a + _b + 0.5 * eps) / 2
    return 0.5 * (_x1 + _x2)


def FindMinLambd(_f, _x0, _s):
    return DichotomyMethod(_f, FindMinimum(_f, _x0, _s), _x0, _s)


def Method(_f, _x0 : np.array, eps = 1e-3):

    k = 0
    x_curr = np.array(_x0)
    while True:
        if k % 3 == 0:
            _s = -1 * np.array(Grad(_f, x_curr))
        lambd = FindMinLambd(_f, x_curr, _s)
        x_next = x_curr + lambd * _s
        w = (Norma(Grad(_f, x_next))) ** 2 / (Norma(Grad(_f, x_curr))) ** 2
        _s = -1 * np.array(Grad(_f, x_next)) + w * _s
        print (x_curr, Norma(_s))
        x_curr = x_next
        k += 1
        if Norma(_s) <= eps:
            print ("MCG answer: ({:5e}; {:5e})".format(x_curr[0], x_curr[1]))
            break
    print()



#Method(fp.F3, x0, 1e-07)