CODEWITHSUNDEEP
algorithmmath
mitcc
mitcc

Reputation: 343

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

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

Upvotes: 8

Views: 1162

Answers (3)

user515430
user515430

Reputation: 3361

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.

Upvotes: 8

Salix alba
Salix alba

Reputation: 7824

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.

Upvotes: 5

Nikunj Banka
Nikunj Banka

Reputation: 11375

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)

Upvotes: 13

Related Questions