Was ist der schnellste Weg, um den Wert von π zu erhalten?

  • Ich suche den schnellsten Weg, um den Wert von π als persönliche Herausforderung zu erhalten. Genauer gesagt verwende ich Methoden, bei denen nicht #define Konstanten wie M_PI verwendet werden oder die Zahl hartcodiert wird.

    Das folgende Programm testet die verschiedenen Möglichkeiten, von denen ich weiß. Die Inline-Montageversion ist theoretisch die schnellste Option, obwohl sie eindeutig nicht portabel ist. Ich habe es als Grundlage zum Vergleich mit den anderen Versionen hinzugefügt. In meinen Tests mit eingebauten Ins ist die 4 * atan(1) -Version auf GCC 4.2 am schnellsten, da sie die atan(1) automatisch in eine Konstante faltet. Ist -fno-builtin angegeben, ist die Version atan2(0, -1) die schnellste.

    Hier ist das Haupttestprogramm (pitimes.c):

    #include <math.h>
    #include <stdio.h>
    #include <time.h>
    
    #define ITERS 10000000
    #define TESTWITH(x) {                                                       \
        diff = 0.0;                                                             \
        time1 = clock();                                                        \
        for (i = 0; i < ITERS; ++i)                                             \
            diff += (x) - M_PI;                                                 \
        time2 = clock();                                                        \
        printf("%s\t=> %e, time => %f\n", #x, diff, diffclock(time2, time1));   \
    }
    
    static inline double
    diffclock(clock_t time1, clock_t time0)
    {
        return (double) (time1 - time0) / CLOCKS_PER_SEC;
    }
    
    int
    main()
    {
        int i;
        clock_t time1, time2;
        double diff;
    
        /* Warmup. The atan2 case catches GCC's atan folding (which would
         * optimise the ``4 * atan(1) - M_PI'' to a no-op), if -fno-builtin
         * is not used. */
        TESTWITH(4 * atan(1))
        TESTWITH(4 * atan2(1, 1))
    
    #if defined(__GNUC__) && (defined(__i386__) || defined(__amd64__))
        extern double fldpi();
        TESTWITH(fldpi())
    #endif
    
        /* Actual tests start here. */
        TESTWITH(atan2(0, -1))
        TESTWITH(acos(-1))
        TESTWITH(2 * asin(1))
        TESTWITH(4 * atan2(1, 1))
        TESTWITH(4 * atan(1))
    
        return 0;
    }
     

    Und das Inline-Assembly-Zeug (fldpi.c)), das nur für x86- und x64-Systeme funktioniert:

    double
    fldpi()
    {
        double pi;
        asm("fldpi" : "=t" (pi));
        return pi;
    }
     

    Und ein Build-Skript, das alle meine Konfigurationen aufbaut testing (build.sh):

    #!/bin/sh
    gcc -O3 -Wall -c           -m32 -o fldpi-32.o fldpi.c
    gcc -O3 -Wall -c           -m64 -o fldpi-64.o fldpi.c
    
    gcc -O3 -Wall -ffast-math  -m32 -o pitimes1-32 pitimes.c fldpi-32.o
    gcc -O3 -Wall              -m32 -o pitimes2-32 pitimes.c fldpi-32.o -lm
    gcc -O3 -Wall -fno-builtin -m32 -o pitimes3-32 pitimes.c fldpi-32.o -lm
    gcc -O3 -Wall -ffast-math  -m64 -o pitimes1-64 pitimes.c fldpi-64.o -lm
    gcc -O3 -Wall              -m64 -o pitimes2-64 pitimes.c fldpi-64.o -lm
    gcc -O3 -Wall -fno-builtin -m64 -o pitimes3-64 pitimes.c fldpi-64.o -lm
     

    Abgesehen vom Testen zwischen verschiedenen Compiler-Flags (ich habe 32- Bit gegen 64-Bit auch, weil die Optimierungen unterschiedlich sind), ich habe auch versucht, die Reihenfolge der Tests umzuschalten. Aber die atan2(0, -1) -Version kommt immer noch an der Spitze.

    15 May 2018
    Chris Jester-Young
23 answers
  • Die Monte-Carlo-Methode wendet, wie erwähnt, einige großartige Konzepte an, ist es aber Klar, nicht der Schnellste, nicht auf lange Sicht, nicht in vernünftigem Maße. Es hängt auch davon ab, nach welcher Art von Genauigkeit Sie suchen. Der schnellste π, den ich kenne, ist der, dessen Ziffern hart codiert sind. Schauen Sie sich Pi und Pi [PDF] , es gibt viele Formeln.

    Hier ist eine Methode, die schnell konvergiert - etwa 14 Ziffern pro Iteration. PiFast , die derzeit schnellste Anwendung, verwendet diese Formel mit der FFT . Ich schreibe einfach die Formel, da der Code unkompliziert ist. Diese Formel wurde fast von Ramanujan gefunden und von Chudnovsky entdeckt . Es ist tatsächlich, wie er mehrere Milliarden Ziffern der Zahl berechnet hat - es ist also keine Methode, die ignoriert wird. Die Formel wird schnell überlaufen, und da wir die Fakultäten teilen, wäre es vorteilhaft, solche Berechnungen zu verzögern, um die Terme zu entfernen.

    Was ist der schnellste Weg, um den Wert von π zu erhalten?

    Was ist der schnellste Weg, um den Wert von π zu erhalten?

    wo,

    Was ist der schnellste Weg, um den Wert von π zu erhalten?

    unten ist der Brent-Salamin-Algorithmus strong> a und b sind "nahe genug", dann wird (a + b) ² / 4t eine Annäherung von π sein. Ich bin nicht sicher, was "nah genug" bedeutet, aber aus meinen Tests erhielt eine Iteration 2 Ziffern, zwei bekamen 7 und drei hatten 15.

    14 May 2018
    q-l-pnlucaroni
  • Ich mag dieses Programm wirklich, weil es sich π annähert, indem es seinen eigenen Bereich betrachtet.

    IOCCC 1988: westley.c

    #define _ -F<00||--F-OO--;
    int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO()
    {
                _-_-_-_
           _-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_-_-_-_-_
      _-_-_-_-_-_-_-_-_-_-_-_-_-_
     _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
     _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
     _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
     _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
      _-_-_-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_-_-_-_-_
            _-_-_-_-_-_-_-_
                _-_-_-_
    }
     
    03 September 2018
    JBDouble05Pat
  • Hier eine allgemeine Beschreibung einer Methode zur Berechnung von Pi, die ich in der High School gelernt habe.

    Ich teile das nur, weil ich denke, dass es einfach genug ist, dass jeder es kann Denken Sie daran, auf unbestimmte Zeit. Außerdem lernen Sie das Konzept der "Monte-Carlo" -Methoden kennen. Hierbei handelt es sich um statistische Methoden, um zu Antworten zu gelangen, die durch zufällige Prozesse nicht sofort als ableitbar erscheinen.

    Zeichnen Sie ein Quadrat und schreiben Sie einen Quadranten (ein Viertel eines Halbkreises) in dieses Quadrat (einen Quadranten mit einem Radius gleich der Seite des Quadrats, damit er möglichst viel Quadrat ausfüllt)

    Jetzt werfen Sie einen Pfeil auf das Quadrat und notieren Sie, wo er landet. Wählen Sie also einen beliebigen Punkt innerhalb des Quadrats. Natürlich landete es innerhalb des Platzes, aber ist es innerhalb des Halbkreises? Notieren Sie sich diese Tatsache.

    Wiederholen Sie diesen Vorgang mehrmals - und Sie werden feststellen, dass die Anzahl der Punkte innerhalb des Halbkreises im Verhältnis zur Gesamtzahl der geworfenen Anzahl steht Verhältnis x.

    Da die Fläche des Quadrats r mal r ist, können Sie daraus schließen, dass die Fläche des Halbkreises x mal r mal r beträgt (d. h. x mal r kariert). Daher gibt x mal 4 dir pi.

    Dies ist keine schnelle Methode. Aber es ist ein schönes Beispiel für eine Monte-Carlo-Methode. Und wenn Sie sich umsehen, stellen Sie möglicherweise fest, dass viele Probleme, die sich außerhalb Ihrer Fähigkeiten im Umgang mit dem Computer ergeben, durch solche Methoden gelöst werden können.

    26 May 2012
    Peter Mortensen
  • Im Interesse der Vollständigkeit wird eine C ++ - Vorlagenversion, die für einen optimierten Build berechnet wird, PI zur Kompilierzeit berechnen und in einen einzigen Wert einbetten.

     #include <iostream>
    
    template<int I>
    struct sign
    {
        enum {value = (I % 2) == 0 ? 1 : -1};
    };
    
    template<int I, int J>
    struct pi_calc
    {
        inline static double value ()
        {
            return (pi_calc<I-1, J>::value () + pi_calc<I-1, J+1>::value ()) / 2.0;
        }
    };
    
    template<int J>
    struct pi_calc<0, J>
    {
        inline static double value ()
        {
            return (sign<J>::value * 4.0) / (2.0 * J + 1.0) + pi_calc<0, J-1>::value ();
        }
    };
    
    
    template<>
    struct pi_calc<0, 0>
    {
        inline static double value ()
        {
            return 4.0;
        }
    };
    
    template<int I>
    struct pi
    {
        inline static double value ()
        {
            return pi_calc<I, I>::value ();
        }
    };
    
    int main ()
    {
        std::cout.precision (12);
    
        const double pi_value = pi<10>::value ();
    
        std::cout << "pi ~ " << pi_value << std::endl;
    
        return 0;
    }
     

    Hinweis für I & gt; 10, optimierte Builds können langsam sein, ebenso für nicht optimierte Läufe. Ich glaube, dass es für 12 Iterationen etwa 80.000 Aufrufe von value () gibt (ohne Memoisierung).

    02 January 2017
    jon-hanson
  • Es gibt tatsächlich ein ganzes Buch, das schnelle -Methoden für die Berechnung von \ pi gewidmet ist: 'Pi and the AGM' von Jonathan und Peter Borwein ( verfügbar bei Amazon ).

    Ich habe die AGM und die dazugehörigen Algorithmen ziemlich viel studiert: Es ist ziemlich interessant (wenn auch manchmal nicht trivial).

    Beachten Sie, dass zur Implementierung der meisten modernen Algorithmen \ pi Sie benötigen eine multipräzise Arithmetikbibliothek ( GMP ist eine gute Wahl, obwohl ich sie seit einiger Zeit nicht mehr verwendet habe.)

    Die Zeitkomplexität der besten Algorithmen ist in O (M (n) log (n)), wobei M (n) die Zeitkomplexität für die Multiplikation von ist zwei n-Bit-Ganzzahlen (M (n) = O (n log (n) log (log (n)))) unter Verwendung von FFT-basierten Algorithmen, die normalerweise erforderlich sind, wenn Digits von \ pi berechnet werden, und ein solcher Algorithmus wird in implementiert GMP).

    < Beachten Sie, dass, obwohl die Mathematik hinter den Algorithmen nicht trivial ist, die Algorithmen selbst normalerweise ein paar Zeilen Pseudo-Code sind und ihre Implementierung normalerweise sehr unkompliziert ist (wenn Sie sich nicht dafür entscheiden, Ihre eigene multipräzise Arithmetik zu schreiben :-) ).

    06 January 2012
    vdbuilderDHL
  • Die folgenden Antworten , wie Sie dies auf dem schnellsten Weg tun können - mit dem geringsten Rechenaufwand . Selbst wenn Ihnen die Antwort nicht gefällt, müssen Sie zugeben, dass es tatsächlich der schnellste Weg ist, den Wert von PI zu erhalten.

    The < strong> SCHNELLSTE Methode , um den Wert von Pi zu erhalten:

    1. wähle deine bevorzugte Programmiersprache
    2. Laden Sie die Math-Bibliothek
    3. und stellen Sie fest, dass Pi dort bereits definiert ist !! bereit, es zu verwenden.

    falls Sie keine Math-Bibliothek zur Hand haben.

    der ZWEITE SCHNELLSTE Weg (universellere Lösung) ist:

    Nachschlagen von Pi im Internet, z hier:

    http://www.eveandersson.com/pi/digits / 1000000 (1 Million Ziffern. Wie lautet Ihre Gleitkomma-Genauigkeit?)

    oder hier:

    http://3.1415926535897932384626433832795028841971693993751052094944592.com/ >

    http://en.wikipedia.org/wiki/Pi

    Es ist sehr schnell, die gewünschten Ziffern für die von Ihnen gewünschte Präzisionsarithmetik zu finden. Durch das Festlegen einer Konstante können Sie sicherstellen, dass Sie keine wertvolle CPU-Zeit verschwenden.

    Dies ist nicht nur eine teils humorvolle Antwort, aber in der Realität würde, wenn jemand vorgehen und den Wert von Pi in einer realen Anwendung berechnen würde ... das wäre eine ziemlich große Verschwendung von CPU-Zeit es? Zumindest sehe ich keine wirkliche Anwendung für den Versuch, dies neu zu berechnen.

    Sehr geehrter Moderator: Bitte beachten Sie, dass das OP gefragt hat: "Fastest Way" / strong >, um den Wert von PI zu erhalten "

    26 May 2012
    Peter Mortensen
  • Mit der BBP-Formel können Sie die n-te Stelle berechnen - in der Basis 2 (oder 16) - ohne sich vorher mit den vorherigen n-1 Ziffern zu beschäftigen:)

    29 August 2008
    Tyler
  • Anstatt pi als Konstante zu definieren, verwende ich immer acos(-1).

    26 May 2012
    Peter Mortensen
  • Ich bin gerade auf dieses gestoßen, das der Vollständigkeit halber hier sein sollte:

    PI in Piet berechnen

    Es hat die ziemlich nette Eigenschaft, dass die Genauigkeit verbessert werden kann, um das Programm zu vergrößern.

    Hier gibt es einige Einblicke in die Sprache selbst

    19 January 2009
    Chris Jester-Young