sidef-scripts/Math/function_inverse_binary_search.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 29 July 2018
# https://github.com/trizen

# Compute the inverse of any function, using the binary search algorithm.

# See also:
#   https://en.wikipedia.org/wiki/Binary_search_algorithm

func binary_inverse (n, f, min=0, max=n, prec=192) {

    local Number!PREC = prec.numify

    (min, max) = (max, min) if (min > max)

    loop {
        var m = (min+max)/2
        var c = (f(m) <~> n)

        if (c < 0) {
            min = m
        }
        elsif (c > 0) {
            max = m
        }
        else {
            return m
        }
    }
}

say binary_inverse(  2, {|x| x.exp })     # solution to x for: exp(x) =   2
say binary_inverse( 43, {|x| x**2  })     # solution to x for:    x^2 =  43
say binary_inverse(-43, {|x| x**3  })     # solution to x for:    x^3 = -43

# Find the value of x such that Li(x) = 100
say binary_inverse(100, {|x| Li(x) }, min: 1, max: 1e6, prec: 200)    #=> 488.87190985280753190605086392033334827378018556409