Ermitteln von log2() mit sqrt()

Question

Dies ist eine Frage, die ich auf einer Website gesehen habe.

Es wurde erwähnt, dass die Antwort darin besteht, eine Rekursion von log2() wie folgt zu bilden:

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

Was die Wiederholung anbelangt, so ist die +1 eindeutig falsch. Auch der Basisfall ist fehlerhaft. Weiß jemand eine bessere Antwort? Wie ist log() und log10() eigentlich in C implementiert.

Answer 1

Vielleicht habe ich genau die Antworten gefunden, nach denen die Interviewer gesucht haben. Ich für meinen Teil würde sagen, dass es ein bisschen schwierig ist, dies unter dem Druck eines Vorstellungsgesprächs abzuleiten. Die Idee ist, sagen wir mal, Sie wollen herausfinden log2(13) können Sie wissen, dass sie zwischen 3 bis 4 . Auch 3 = log2(8) and 4 = log2(16) ,

Aus den Eigenschaften des Logarithmus wissen wir, dass log( sqrt( (8*16) ) = (log(8) + log(16))/2 = (3+4)/2 = 3.5

Jetzt, sqrt(8*16) = 11.3137 y log2(11.3137) = 3.5 . Desde 11.3137<13 wissen wir, dass der von uns gewünschte log2(13) zwischen 3,5 und 4 und wir fahren fort, diese zu lokalisieren. Es ist leicht zu erkennen, dass es sich um eine binäre Suchlösung handelt, und wir iterieren bis zu einem Punkt, an dem unser Wert zu dem Wert konvergiert, dessen log2() die wir finden wollen. Der Code ist unten angegeben:

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;

}

Answer 2

Es ist lange her, dass ich reines C geschrieben habe, also hier ist es in C++ (ich denke, der einzige Unterschied ist die Ausgabefunktion, also sollten Sie in der Lage sein, ihr zu folgen):

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

Die Funktion "mylog2" führt einige einfache Log-Tricks aus, um eine Zahl zwischen 1 und 2 zu erhalten, und ruft dann log2_aux mit dieser Zahl auf.

Der log2_aux folgt mehr oder weniger dem Algorithmus, den Scorpi0 oben verlinkt hat. Bei jedem Schritt erhält man 1 Bit des Ergebnisses. Wenn Sie genug Bits haben, stoppen Sie.

Wenn Sie ein Exemplar der Feynman Lectures on Physics, Nummer 23, ergattern können, finden Sie zu Beginn eine großartige Erklärung der Logs und mehr oder weniger, wie man diese Umwandlung vornimmt. Weitaus besser als der Wikipedia-Artikel.