给定exp()函数,如何实现ln()函数？

Question

我在CS求职面试时遇到了这个问题.我不知道它,更不用说实现代码......

我能得到一些提示吗？

PS exp()是函数y = e ^ x和ln()是y = ln(x)

Answer 1

您可以通过二进制搜索答案找到日志时间的值.这是可能的,因为log X是单调递增的函数.

_{(由WolframAlpha提供)}.

例如,如果我们必须计算的对数值(假设它是X)大于1,则以answer = X的假设开始.提高功率e ^ answer并检查该值是否大于或小于现在,根据您获得的值是否大于或小于X,您可以优化您的限制.当您达到答案的合适范围内时,搜索将停止.

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;
            }
        }
    }

同样,如果X的值小于1,那么你可以将这种情况减少到我们已经考虑过的情况,即.当X大于1时.例如,如果X = 0.04,那么

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

Answer 2

如果X为正,则可以使用牛顿方法找到对数.

X_ {0} = 0

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

收敛速度非常快.

Answer 3

调整此答案以使X在[0,e]范围内缩放.我们所知道的一些事情ln(x),ln(x)仅定义为0 <x,ln(1)=0结果可以是从-infinity到+ infinity的任何数字.ln(x^a) = a * ln(x)尤其是ln(x^(-1)) = - ln(x),ln(X/e) = ln(X)-ln(e)这样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;
        }
    }
}

如果你看一下库中数学函数的实际实现.他们做了很多预缩小工作来缩小输入范围,可能比这里做的更具侵略性.