使用sqrt（）查找log2（）

這是我在某網站上看到的一個採訪問題。使用sqrt（）查找log2（）

有人提到，答案涉及形成的log 2復發（）如下：

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.實際執行

來源

2011-04-18 Shamim Hafiz

該問題的+1。我只用100作爲輸入，然後返回30.方法不完整。 – 2011-04-18 09:53:49

維基百科上有一個算法http://en.wikipedia.org/wiki/Binary_logarithm – 2011-04-19 06:44:57

也許我找到了面試官正在尋找的確切答案。從我的角度來看，我認爲在面試壓力下獲得這一點很難。想法是，假設你想找到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之間，我們繼續找到它。很容易注意到，這有一個二進制搜索解決方案，當我們的值收斂到我們希望找到的值時，我們迭代到一個點。代碼如下：

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-16 06:56:54

-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-21 06:40:35 Michael

我認爲你錯過了一些角落的情況下，4我得到1.5，顯然應該是2. – 2011-04-21 07:06:11

這是什麼廢話！ – Spandan 2013-08-10 08:23:05

使用sqrt（）查找log2（）

回答

相關問題