Carmack's Trick

John Carmack ist ein bekannter Videospielprogrammierer und Mitbegründer von id Software, dem Unternehmen, das für die Entwicklung von Spielen wie Doom, Quake und Wolfenstein 3D bekannt ist.

Carmack ist bekannt für seine technische Expertise und hat eine wichtige Rolle bei der Entwicklung von 3D-Engines für Videospiele gespielt.

Die schnelle Berechnung der inversen Quadratwurzel war für die 3D-Engines von Carmack sehr wichtig, da sie dazu beitrug, die Leistung zu verbessern. ~~Carmack entdeckte diesen Algorithmus während seiner Arbeit an der Spiele-Engine für Quake III Arena und integrierte ihn in den Code~~.

💡

In Lex Fridmans Podcast antwortete Carmack auf die Frage, wie man auf einen solchen Algorithmus kommt, dass er nicht für den entsprechenden Snippet verantwortlich ist und dass er nicht weiß, wie jeder darauf kommt.

Dieser Algorithmus wurde später als "Carmack's Trick" bekannt und ist seitdem in vielen Anwendungen weit verbreitet, die eine schnelle Berechnung der inversen Quadratwurzel erfordern.

Es ist interessant zu sehen, wie eine technische Lösung, die für ein Videospiel entwickelt wurde, auch in anderen Bereichen weit verbreitet ist. Carmack's Trick zeigt, wie bedeutend Innovationen in der Videospielbranche auch für andere Bereiche relevant sein können.

Der Algorithmus ermöglicht eine schnellere Berechnung der inversen Quadratwurzel einer Gleitkommazahl. Im Vergleich zur Standardfunktion 1/sqrt() ist diese Methode um ein Vielfaches schneller und genau genug für viele Anwendungen.

Die Funktion arbeitet wie folgt:

Der Parameter num wird mit 0,5 multipliziert und in x2 gespeichert.
Der Wert von num wird in y gespeichert.
Die Bitdarstellung von y wird in die Variable i konvertiert, die vom Typ long ist.
Die magische Zahl wird von i subtrahiert, nachdem die Hälfte von i bitweise verschoben wurde. Das Ergebnis wird wieder in i gespeichert.
Die Bitdarstellung von i wird in die Variable y konvertiert, die vom Typ float ist.
Eine Schleife wird für iterations-mal ausgeführt, wobei y iterativ verbessert wird, um eine genauere Schätzung für die inverse Quadratwurzel zu erhalten.

float fast_rsqrt(float, short)

/*
* Casts the pointer of num to long and substracts the
* bit shifted num argument from a constant value. The
* results is a rough estimate of the inverse square
* root. Further accuracy is achieved through the
* Newton-Raphson method.
* 
* @params
* float num: 
*   Value from which the inverse 
*   square root is to be calculated
* short iterations:
*   The more iterations, the higher 
*   the precision.
*/
float fast_rsqrt(float num, short iterations) {
    long i;
    float x2, y;
    const float threehalfs = 1.5f;

    x2 = num * 0.5f;
    y = num;
    i = *(long*)&y;
    i = 0x5f3759df - (i >> 1);
    y = *(float*)&i;

    for (short i = 0; i < iterations; i++) {
        y = y * (threehalfs - (x2 * y * y));
    }        

    return y;
}

Die fast_rsqrt Funktion nimmt zwei Parameter: num, das die Zahl ist, für die die inverse Quadratwurzel berechnet werden soll, und iterations, die Anzahl der Iterationen, die durchgeführt werden sollen. Je höher die Anzahl der Iterationen, desto genauer wird das Ergebnis sein.

Die Implementierung der Funktion basiert auf einer "magic number" (0x5f3759df). Diese Zahl wird dazu verwendet, die Bitdarstellung des float-Parameters num zu manipulieren und eine erste Schätzung für die inverse Quadratwurzel zu erhalten. Die weitere Verbesserung erfolgt dann durch das Ausführen mehrerer Iterationen, um das Ergebnis zu verfeinern.

void save(std::string &filename, std::stringstream &data) {
    std::ofstream file;
    std::string s(data.str());

    std::replace(s.begin(), s.end(), '.', ',');
    file.open(filename, std::ios::out | std::ios::trunc);
    file << s << std::endl;
    file.close();
}

int main() {
    std::stringstream stream;
    float number = 0xffffffffffffffff;
    const short iterations = 3; 
    float duration;
    float rsqrt;

    LARGE_INTEGER frequency;       
    LARGE_INTEGER t1, t2;           

    QueryPerformanceFrequency(&frequency);

    stream << "value; ";

    for (short i = 1; i <= iterations; i++) {
        stream << "result fast_rsqrt(" 
            << i 
            << (i == 1 ? " iteration); " : " iterations); ")
            << "duration fast_rsqrt(" 
            << i 
            << (i == 1 ? " iteration); " : " iterations); ");
    }

    stream << "result 1 / sqrt; duration 1 /sqrt" << std::endl;

    for (short i = 1; i <= 50; i++) {
        number /= i;
        std::cout << std::endl 
            << std::endl 
            << "   value: " 
            << number 
            << std::endl 
            << "========================" 
            << std::endl;

        if (number == 0) {
            continue;
        }

        stream << number << "; ";

        for (short j = 1; j <= iterations; j++) {
            QueryPerformanceCounter(&t1);
            rsqrt = fast_rsqrt(number, j);
            Sleep(2);
            QueryPerformanceCounter(&t2);
            duration = (t2.QuadPart - t1.QuadPart - 2) * 1000.0 / frequency.QuadPart;

            std::cout << " fast_rsqrt (" 
                << j 
                << (j == 1 ? " iteration)  :\t" : " iterations) :\t")
                << rsqrt << "\texecuted in "
                << duration
                << " ms" 
                << std::endl;

            stream << rsqrt << "; " << duration << "; ";
        }

        QueryPerformanceCounter(&t1);
        rsqrt = 1 / sqrt(number);
        Sleep(2);
        QueryPerformanceCounter(&t2);
        duration = (t2.QuadPart - t1.QuadPart - 2) * 1000.0 / frequency.QuadPart;

        std::cout << " 1 / sqrt                  :\t"
            << rsqrt
            << "\texecuted in "
            << duration
            << " ms"
            << std::endl << std::endl
            << "------------------------------------------------------------------------------------"
            << std::endl;

        stream << rsqrt << "; " << duration << std::endl;
    }

    for (;;) {
        std::string input;

        std::cout << std::endl 
            << std::endl 
            << "---" 
            << std::endl 
            << "Do you want to export results to CSV? (y/n): ";
        std::cin >> input;

        if (input.compare("y") == 0 || input.compare("Y") == 0) {
            input.clear();

            std::string filename("rsqrt-test.csv");
         
            std::cout << std::endl 
                << "Filename (" 
                << filename 
                << "): ";
            std::cin >> input;

            if (!input.empty()) {
                filename = input;
            }

            save(filename, stream);
            break;
        } else if (input.compare("n") == 0 || input.compare("N") == 0) {
            break;
        }

        std::cerr << "\n\n" 
            << input 
            << ":\tI didn't get that. Can you repeat, please?\n\n";
    }

    return EXIT_SUCCESS;
}

Die Funktion fast_rsqrt wird im oberen Code Abschnitt mit verschiedenen Werten für iterations aufgerufen, um zu zeigen, wie sich die Genauigkeit und Ausführungszeit ändern. Schließlich wird die Standardfunktion 1/sqrt() aufgerufen, um das Ergebnis zu vergleichen.

Carmack's Trick kann für Anwendungen nützlich sein, bei denen eine schnelle Berechnung der inversen Quadratwurzel erforderlich ist, beispielsweise in der Physiksimulation, bei der Grafikberechnung und in der Signalverarbeitung. Es ist jedoch zu beachten, dass diese Methode aufgrund der verwendeten Bitmanipulation nicht für alle Anwendungen geeignet ist. Es ist wichtig, dass der Code vor dem Einsatz sorgfältig getestet und validiert wird, um sicherzustellen, dass er für die spezifische Anwendung geeignet ist.