Problem set 3: 2_Quiz_Inverse_Function

目次

---

• Inverse Functionとは
• 実装
  • 逆算法
  • ２分探査

Inverse Functionとは

---

まずは、関数の定義から見てみる。

あるy = f(x)に対して、xを求めるようなf'(y)のことである。
ex) f(x) = x ** 2 f'(x) = sqrt(y)

こんな関数を実装していく。

実装

---

逆算方

f(x)を0から順番に計算していき、yに近似するまでループする。

def Inverse(f ,delta=1/285.):
    """
  Given a function y = f(x) that is monotonically increasing function on
  no-negative numbers, return the function x = f_1(y) that is an approximate inverse
  """
    def _f(y):
        x = 0
        while f(x) < y:
            x = x + delta
        
        return x if (f(x) - y < y - f(x-delta)) else x-delta
        
    return _f

この場合、検索のポインタｘがdeltaずつしか増加しないため、yの数を大きくすると検索回数が増大する。

２分探査

逆算出は単純に０から順に検索していたので、検索に時間を要した。 そのため、目的の値(x)を挟む２つの値から2分探査を用いて検索することで時間短縮をすることが可能。

def Inverse_quick(f, delta=1/285):
    def _f(y):
        lo, hi = find_bounds(f, y)
        return binary_search(lo, hi, f, y, delta)
    return _f

def find_bounds(f, y):
    x = 1
    while f(x) <= y:
        x *= 2
    return (0, 1) if x == 1 else (x/2, x)

def binary_search(lo, hi, f, y, delta):
    while lo < hi:
        mid = (lo + hi) / 2
        if y > f(mid):
            lo = mid + delta
        elif y < f(mid):
            hi = mid - delta
        else:
            return mid
    return lo if (y - f(lo) < f(hi) - y) else hi

def square(x): return x * x

sqrt = Inverse_quick(square)

print(sqrt(100))