Поиск log2 () с использованием sqrt () - PullRequest
Новая
       5

Поиск log2 () с использованием sqrt ()

4 голосов
/ 18 апреля 2011

Это вопрос интервью, который я видел на каком-то сайте.

Было отмечено, что ответ включает формирование повторения 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.

Ответы [ 2 ]

10 голосов
/ 16 мая 2011

Возможно, я нашел точные ответы, которые искали интервьюеры.Со своей стороны, я бы сказал, что это немного сложно получить под давлением интервью.Идея в том, что, скажем, вы хотите найти 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;

}
0 голосов
/ 21 апреля 2011

Прошло много времени с тех пор, как я написал чистый 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, начинается с отличного объяснения журналов и более или менее того, как выполнить это преобразование. Значительно превосходит статью в Википедии.

...