使用sqrt()查找log2()

Question

这是我在某个网站上看到的一个访谈问题.

有人提到答案涉及形成log2()的重复,如下所示:

double log2(double x )
{
if ( x<=2 ) return 1;
 if ( IsSqureNum(x) )
   return log2(sqrt(x) ) * 2;
 return log2( sqrt(x) ) * 2 + 1; // Why the plus one here.
}

至于复发,显然+1是错误的.而且,基本情况也是错误的.有谁知道更好的答案？log()和log10()实际上是如何在C中实现的.

Answer 1

也许我已经找到了面试官正在寻找的确切答案.就我而言,我会说在面试压力下得出这个有点困难.这个想法是,你想要找到log2(13),你可以知道它介于3到4之间.还有3 = log2(8) and 4 = log2(16),

从对数的属性,我们知道 log( sqrt( (8*16) ) = (log(8) + log(16))/2 = (3+4)/2 = 3.5

现在,sqrt(8*16) = 11.3137和log2(11.3137) = 3.5.因为11.3137<13,我们知道我们想要的log2(13)将介于3.5和4之间,我们继续找到它.很容易注意到它有一个二进制搜索解决方案,当我们的值收敛到log2()我们希望找到的值时,我们迭代到一个点.代码如下:

double Log2(double val)
{
    int lox,hix;
    double rval, lval;
    hix = 0;
    while((1<<hix)<val)
        hix++;
    lox =hix-1;
    lval = (1<<lox) ;
    rval = (1<<hix);
    double lo=lox,hi=hix;
   // cout<<lox<<" "<<hix<<endl;
    //cout<<lval<<" "<<rval;
    while( fabs(lval-val)>1e-7)
    {
        double mid = (lo+hi)/2;
        double midValue = sqrt(lval*rval);

        if ( midValue > val)
        {
             hi = mid;
             rval = midValue;
        }
        else{
            lo=mid;
            lval = midValue;
        }
    }
    return lo;

}