Given the exp() function, how to implement the ln() function?

Question

I came cross this question when I was in a CS job interview. I have no idea about it, let alone implement the code……

Could I get some tips?

P.S. exp() is the function y = e^x and ln() is y = ln(x)

Answer 1

You can find the value in log time by binary searching the answer. This is possible because log X is a monotonically increasing function.

_{(courtesy of WolframAlpha)}.

For example, if the value whose logarithm we have to calculate (assume it to be X) is greater than 1, then start with an assumption of answer = X. Raise the power e^answer and check if the value is greater than or smaller than X. Now based on whether the value you get is greater than or lesser than X, you can refine your limits. The search stops when you have reached within suitable ranges of your answer.

double log(double X){
        double lo = 1;
        double hi = X;

        while(true){
            double mid = (lo+hi)/2;
            double val = power(e, mid);
            if(val > X){
                hi = mid;
            }
            if(val < X){
                lo = mid;
            }
            if(abs(val-X) < error){
                return mid;
            }
        }
    }

Similarly, if the value of X is smaller than 1, then you can reduce this case to the case we have already considered, ie. when X is greater than 1. For example if X = 0.04, then

log 0.04 = log (4/100) = (log 4) - (log 100)

Answer 2

If X is positive, then the logarithm can be found using Newton's method.

X_{0} = 0

X_{n+1} = X_{n} - (exp(X_{n}) - X) / (exp(X_{n})

Very fast convergence.

Answer 3

Adapting this answer to get X scaled in the range [0,e]. A few things we know about ln(x), ln(x) is only defined for 0 < x, ln(1)=0, the results can be any number from -infinity to +infinity. ln(x^a) = a * ln(x) in particular ln(x^(-1)) = - ln(x), ln(X/e) = ln(X)-ln(e) so ln(X) = ln(X/e) + 1.

double E = exp(1);
double ln(double X) {
    if(X<0) return NaN;
    // use recursion to get approx range
    if(X<1) {
       return - ln( 1 / X );
    }
    if(X>E) {
       return ln(X/E) + 1;
    }
    // X is now between 1 and e
    // Y is between 0 and 1

    double lo = 0;
    double hi = 1;

    while(true){
        double mid = (lo+hi)/2;
        double val = exp(mid);
        if(val > X){
            hi = mid;
        }
        if(val < X){
            lo = mid;
        }
        if(abs(val-X) < error){
            return mid;
        }
    }
}

If you look at the actual implementations of mathematical functions in the libraries. They do quite a lot of prescaling work to narrow the ranges of input, probably more aggressive than is done here.