4

これは私がいくつかのサイトで見たインタビューの質問です。

その答えは、次のように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でどのように実装されていますか。

4

2 に答える 2

10

おそらく私はインタビュアーが探していた正確な答えを見つけました。私の側からすると、面接のプレッシャーの下でこれを導き出すのは少し難しいと思います。アイデアは、あなたが見つけたいと言う、あなたはそれが3から4log2(13)の間にあることを知ることができるということです。また、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;

}
于 2011-05-16T06:56:54.850 に答える
-1

私が純粋なCを書いたのは久しぶりなので、ここではC ++です（唯一の違いは出力関数だと思うので、それに従うことができるはずです）：

#include <iostream>
using namespace std;

const static double CUTOFF = 1e-10;

double log2_aux(double x, double power, double twoToTheMinusN, unsigned int accumulator) {
     if (twoToTheMinusN < CUTOFF)
       return accumulator * twoToTheMinusN * 2;
     else {
       int thisBit;
       if (x > power) {
            thisBit = 1;
            x /= power;
       }
       else
            thisBit = 0;
       accumulator = (accumulator << 1) + thisBit;
       return log2_aux(x, sqrt(power), twoToTheMinusN / 2.0, accumulator);
     }
}

double mylog2(double x) {
     if (x < 1)
       return -mylog2(1.0/x);
     else if (x == 1)
       return 0;
     else if (x > 2.0)
       return mylog2(x / 2.0) + 1;
     else
       return log2_aux(x, 2.0, 1.0, 0);
}

int main() {
     cout << "5 " << mylog2(5) << "\n";
     cout << "1.25 " << mylog2(1.25) << "\n";
     return 0;
}

関数'mylog2'は、1から2の間の関連番号を取得するためにいくつかの簡単なログトリックを実行し、その番号でlog2_auxを呼び出します。

log2_auxは、Scorpi0が上記でリンクしたアルゴリズムにほぼ従っています。各ステップで、1ビットの結果が得られます。十分なビットがある場合は、停止します。

コピーを手に入れることができれば、ファインマン物理学の講義、23番は、ログの優れた説明と、多かれ少なかれこの変換を行う方法から始まります。ウィキペディアの記事よりもはるかに優れています。

于 2011-04-21T06:40:35.763 に答える