Frage

Als persönliche Herausforderung suche ich nach dem schnellsten Weg, den Wert von π zu ermitteln.Genauer gesagt verwende ich Methoden, die keine Verwendung beinhalten #define Konstanten wie M_PI, oder die Nummer fest codieren.

Das folgende Programm testet die verschiedenen mir bekannten Möglichkeiten.Die Inline-Assembly-Version ist theoretisch die schnellste Option, allerdings eindeutig nicht portierbar.Ich habe es als Basis zum Vergleich mit den anderen Versionen eingefügt.In meinen Tests mit integrierten Funktionen war das 4 * atan(1) Die Version ist unter GCC 4.2 am schnellsten, da sie automatisch gefaltet wird atan(1) in eine Konstante.Mit -fno-builtin angegeben, die atan2(0, -1) Version ist am schnellsten.

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 Konfigurationen erstellt, die ich teste (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 auch 32-Bit mit 64-Bit verglichen, weil die Optimierungen unterschiedlich sind), habe ich auch versucht, die Reihenfolge der Tests zu ändern.Aber trotzdem, die atan2(0, -1) Die Version hat immer noch jedes Mal die Nase vorn.

War es hilfreich?

Lösung

Der Monte-Carlo-Methode, wie bereits erwähnt, wendet einige großartige Konzepte an, ist aber eindeutig nicht das schnellste, bei weitem nicht und in keiner vernünftigen Hinsicht.Außerdem hängt alles davon ab, welche Art von Genauigkeit Sie suchen.Das schnellste π, das ich kenne, ist das mit den fest codierten Ziffern.Anschauen Pi Und Pi[PDF], es gibt viele Formeln.

Hier ist eine Methode, die schnell konvergiert – etwa 14 Stellen pro Iteration. PiFast, die derzeit schnellste Anwendung, verwendet diese Formel mit der FFT.Ich schreibe einfach die Formel, da der Code einfach ist.Diese Formel wurde fast von gefunden Ramanujan und von Chudnovsky entdeckt.Auf diese Weise hat er tatsächlich mehrere Milliarden Stellen der Zahl berechnet – es ist also keine Methode, die man außer Acht lassen sollte.Die Formel wird schnell überlaufen, und da wir Fakultäten dividieren, wäre es von Vorteil, solche Berechnungen dann zu verzögern, um Terme zu entfernen.

enter image description here

enter image description here

Wo,

enter image description here

Unten ist die Brent-Salamin-Algorithmus.Wikipedia erwähnt das wann A Und B sind dann „nahe genug“. (a + b)² / 4t wird eine Näherung von π sein.Ich bin mir nicht sicher, was „nahe genug“ bedeutet, aber aus meinen Tests geht hervor, dass eine Iteration zwei Ziffern hatte, zwei eine 7 und drei eine 15, natürlich handelt es sich dabei um Doppelstellen, daher kann es aufgrund der Darstellung und der Darstellung zu einem Fehler kommen Die WAHR Berechnung könnte genauer sein.

let pi_2 iters =
    let rec loop_ a b t p i =
        if i = 0 then a,b,t,p
        else
            let a_n = (a +. b) /. 2.0 
            and b_n = sqrt (a*.b)
            and p_n = 2.0 *. p in
            let t_n = t -. (p *. (a -. a_n) *. (a -. a_n)) in
            loop_ a_n b_n t_n p_n (i - 1)
    in 
    let a,b,t,p = loop_ (1.0) (1.0 /. (sqrt 2.0)) (1.0/.4.0) (1.0) iters in
    (a +. b) *. (a +. b) /. (4.0 *. t)

Wie wäre es zum Schluss mit etwas Pi-Golf (800 Ziffern)?160 Zeichen!

int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}

Andere Tipps

Ich mag dieses Programm wirklich, weil es π annähert, indem es seine eigene Fläche 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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}

Hier ist eine allgemeine Beschreibung einer Technik zur Berechnung von Pi, die ich in der High School gelernt habe.

Ich teile dies nur, weil ich denke, dass es so einfach ist, dass sich jeder auf unbestimmte Zeit daran erinnern kann, und außerdem lehrt es Sie das Konzept der „Monte-Carlo“-Methoden – das sind statistische Methoden, um zu Antworten zu gelangen, die nicht sofort so erscheinen durch zufällige Prozesse ableitbar.

Zeichnen Sie ein Quadrat und schreiben Sie einen Quadranten (ein Viertel eines Halbkreises) in dieses Quadrat ein (einen Quadranten mit einem Radius, der der Seite des Quadrats entspricht, damit er so viel wie möglich vom Quadrat ausfüllt).

Werfen Sie nun einen Pfeil auf das Quadrat und notieren Sie, wo er landet. Wählen Sie also einen zufälligen Punkt irgendwo innerhalb des Quadrats.Natürlich ist es innerhalb des Quadrats gelandet, aber befindet es sich innerhalb des Halbkreises?Notieren Sie diese Tatsache.

Wiederholen Sie diesen Vorgang viele Male – und Sie werden feststellen, dass es ein Verhältnis zwischen der Anzahl der Punkte innerhalb des Halbkreises und der Gesamtzahl der geworfenen Punkte gibt. Nennen Sie dieses Verhältnis x.

Da die Fläche des Quadrats r mal r beträgt, können Sie ableiten, dass die Fläche des Halbkreises x mal r mal r beträgt (d. h. x mal r im Quadrat).Daher ergibt x mal 4 Pi.

Dies ist keine schnelle Methode.Aber es ist ein schönes Beispiel für eine Monte-Carlo-Methode.Und wenn Sie sich umschauen, werden Sie vielleicht feststellen, dass viele Probleme, die sonst außerhalb Ihrer Rechenkenntnisse liegen, mit solchen Methoden gelöst werden können.

Der Vollständigkeit halber eine C++-Vorlagenversion, die für einen optimierten Build eine Annäherung an PI zur Kompilierungszeit berechnet und in einen einzelnen Wert einfügt.

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

Beachten Sie, dass bei I > 10 optimierte Builds langsam sein können, ebenso bei nicht optimierten Läufen.Für 12 Iterationen gibt es meines Erachtens etwa 80.000 Aufrufe von value() (ohne Memoisierung).

Es gibt tatsächlich ein ganzes Buch, das (unter anderem) diesem Thema gewidmet ist schnell Methoden zur Berechnung von \pi:„Pi and the AGM“, von Jonathan und Peter Borwein (erhältlich bei Amazon).

Ich habe mich eingehend mit der Hauptversammlung und den zugehörigen Algorithmen befasst:Es ist ziemlich interessant (wenn auch manchmal nicht trivial).

Beachten Sie, dass Sie zur Implementierung der meisten modernen Algorithmen zur Berechnung von \pi eine Bibliothek für Multipräzisionsarithmetik benötigen (GMP ist eine ziemlich gute Wahl, obwohl es schon eine Weile her ist, seit ich es das letzte Mal benutzt habe.

Die Zeitkomplexität der besten Algorithmen liegt in O(M(n)log(n)), wobei M(n) die Zeitkomplexität für die Multiplikation zweier n-Bit-Ganzzahlen ist (M(n)=O(n). log(n) log(log(n))) unter Verwendung von FFT-basierten Algorithmen, die normalerweise bei der Berechnung von Ziffern von \pi benötigt werden, und ein solcher Algorithmus ist in GMP implementiert).

Beachten Sie, dass die Mathematik hinter den Algorithmen zwar nicht trivial ist, die Algorithmen selbst jedoch normalerweise aus ein paar Zeilen Pseudocode bestehen und ihre Implementierung normalerweise sehr einfach ist (wenn Sie sich dafür entschieden haben, keine eigene Multipräzisionsarithmetik zu schreiben :-) ).

Die folgenden Antworten genau, wie man das am schnellsten und mit dem geringsten Rechenaufwand macht.Auch wenn Ihnen die Antwort nicht gefällt, müssen Sie zugeben, dass dies tatsächlich der schnellste Weg ist, den Wert von PI zu ermitteln.

Der SCHNELLSTE Der Weg, den Wert von Pi zu ermitteln, ist:

1) Wählen Sie Ihre bevorzugte Programmiersprache 2) Laden Sie die Mathematikbibliothek 3) und stellen Sie fest, dass PI bereits dort definiert ist - bereit für die Verwendung!

Falls Sie keine Mathematikbibliothek zur Hand haben.

Der ZWEITSCHNELLSTER Weg (universellere Lösung) ist:

Suchen Sie im Internet nach Pi, z.Hier:

http://www.eveandersson.com/pi/digits/1000000 (1 Million Ziffern ..Wie hoch ist Ihre Gleitkommagenauigkeit?)

oder hier:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

oder hier:

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

Es geht wirklich schnell, die Ziffern zu finden, die Sie für die Präzisionsarithmetik benötigen, die Sie verwenden möchten, und durch die Definition einer Konstante können Sie sicherstellen, dass Sie keine wertvolle CPU-Zeit verschwenden.

Dies ist nicht nur eine teilweise humorvolle Antwort, sondern in Wirklichkeit, wenn jemand den Wert von Pi in einer realen Anwendung berechnen würde ...Das wäre eine ziemlich große Verschwendung von CPU-Zeit, nicht wahr?Zumindest sehe ich keine wirkliche Anwendung für den Versuch, dies neu zu berechnen.

Lieber Moderator:Bitte beachten Sie, dass das OP gefragt hat:„Der schnellste Weg, den Wert von PI zu nutzen“

Der BBP-Formel ermöglicht es Ihnen, die n-te Ziffer zu berechnen – in Basis 2 (oder 16) – ohne sich zuerst mit den vorherigen n-1 Ziffern herumschlagen zu müssen :)

Anstatt Pi als Konstante zu definieren, verwende ich immer acos(-1).

Bin gerade auf Folgendes gestoßen, das der Vollständigkeit halber hier sein sollte:

Berechnen Sie PI in Piet

Es hat die nette Eigenschaft, dass die Präzision verbessert werden kann, indem das Programm größer wird.

HierGibt einen Einblick in die Sprache selbst

Wenn Dieser Artikel ist wahr, dann die Algorithmus, dass Bellard erstellt hat, könnte einer der schnellsten sein, die es gibt.Er hat Pi mit einem Desktop-PC auf 2,7 Billionen Stellen berechnet!

...und er hat seine veröffentlicht arbeite hier

Gute Arbeit, Bellard, Sie sind ein Pionier!

http://www.theregister.co.uk/2010/01/06/very_long_pi/

Dies ist eine „klassische“ Methode, die sehr einfach zu implementieren ist.Diese Implementierung in Python (nicht so schnelle Sprache) macht Folgendes:

from math import pi
from time import time


precision = 10**6 # higher value -> higher precision
                  # lower  value -> higher speed

t = time()

calc = 0
for k in xrange(0, precision):
    calc += ((-1)**k) / (2*k+1.)
calc *= 4. # this is just a little optimization

t = time()-t

print "Calculated: %.40f" % calc
print "Costant pi: %.40f" % pi
print "Difference: %.40f" % abs(calc-pi)
print "Time elapsed: %s" % repr(t)

Weitere Informationen finden Sie hier Hier.

Wie auch immer, der schnellste Weg, um in Python einen genauen Wert von Pi zu erhalten, so viel Sie wollen, ist:

from gmpy import pi
print pi(3000) # the rule is the same as 
               # the precision on the previous code

Hier ist der Quellcode für die gmpy-pi-Methode. Ich glaube nicht, dass der Code in diesem Fall so nützlich ist wie der Kommentar:

static char doc_pi[]="\
pi(n): returns pi with n bits of precision in an mpf object\n\
";

/* This function was originally from netlib, package bmp, by
 * Richard P. Brent. Paulo Cesar Pereira de Andrade converted
 * it to C and used it in his LISP interpreter.
 *
 * Original comments:
 * 
 *   sets mp pi = 3.14159... to the available precision.
 *   uses the gauss-legendre algorithm.
 *   this method requires time o(ln(t)m(t)), so it is slower
 *   than mppi if m(t) = o(t**2), but would be faster for
 *   large t if a faster multiplication algorithm were used
 *   (see comments in mpmul).
 *   for a description of the method, see - multiple-precision
 *   zero-finding and the complexity of elementary function
 *   evaluation (by r. p. brent), in analytic computational
 *   complexity (edited by j. f. traub), academic press, 1976, 151-176.
 *   rounding options not implemented, no guard digits used.
*/
static PyObject *
Pygmpy_pi(PyObject *self, PyObject *args)
{
    PympfObject *pi;
    int precision;
    mpf_t r_i2, r_i3, r_i4;
    mpf_t ix;

    ONE_ARG("pi", "i", &precision);
    if(!(pi = Pympf_new(precision))) {
        return NULL;
    }

    mpf_set_si(pi->f, 1);

    mpf_init(ix);
    mpf_set_ui(ix, 1);

    mpf_init2(r_i2, precision);

    mpf_init2(r_i3, precision);
    mpf_set_d(r_i3, 0.25);

    mpf_init2(r_i4, precision);
    mpf_set_d(r_i4, 0.5);
    mpf_sqrt(r_i4, r_i4);

    for (;;) {
        mpf_set(r_i2, pi->f);
        mpf_add(pi->f, pi->f, r_i4);
        mpf_div_ui(pi->f, pi->f, 2);
        mpf_mul(r_i4, r_i2, r_i4);
        mpf_sub(r_i2, pi->f, r_i2);
        mpf_mul(r_i2, r_i2, r_i2);
        mpf_mul(r_i2, r_i2, ix);
        mpf_sub(r_i3, r_i3, r_i2);
        mpf_sqrt(r_i4, r_i4);
        mpf_mul_ui(ix, ix, 2);
        /* Check for convergence */
        if (!(mpf_cmp_si(r_i2, 0) && 
              mpf_get_prec(r_i2) >= (unsigned)precision)) {
            mpf_mul(pi->f, pi->f, r_i4);
            mpf_div(pi->f, pi->f, r_i3);
            break;
        }
    }

    mpf_clear(ix);
    mpf_clear(r_i2);
    mpf_clear(r_i3);
    mpf_clear(r_i4);

    return (PyObject*)pi;
}

BEARBEITEN: Ich hatte ein Problem mit dem Ausschneiden, Einfügen und Identifizieren. Sie können die Quelle trotzdem finden Hier.

Wenn Sie mit „schnellst“ meinen, dass Sie den Code am schnellsten eingeben können, finden Sie hier den Code Golfscript Lösung:

;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;

Verwenden Sie die maschinenähnliche Formel

176 * arctan (1/57) + 28 * arctan (1/239) - 48 * arctan (1/682) + 96 * arctan(1/12943) 

[; \left( 176 \arctan \frac{1}{57} + 28 \arctan \frac{1}{239} - 48 \arctan \frac{1}{682} + 96 \arctan \frac{1}{12943}\right) ;], for you TeX the World people.

Im Schema implementiert, zum Beispiel:

(+ (- (+ (* 176 (atan (/ 1 57))) (* 28 (atan (/ 1 239)))) (* 48 (atan (/ 1 682)))) (* 96 (atan (/ 1 12943))))

Wenn Sie bereit sind, eine Näherung zu verwenden, 355 / 113 eignet sich für 6 Dezimalstellen und hat den zusätzlichen Vorteil, dass es mit ganzzahligen Ausdrücken verwendet werden kann.Das ist heutzutage nicht mehr so ​​wichtig, da „Gleitkomma-Mathematik-Coprozessor“ keine Bedeutung mehr hat, aber früher war es ziemlich wichtig.

Mit Doppel:

4.0 * (4.0 * Math.Atan(0.2) - Math.Atan(1.0 / 239.0))

Dies ist bis zu 14 Dezimalstellen genau, was ausreicht, um ein Double zu füllen (die Ungenauigkeit ist wahrscheinlich darauf zurückzuführen, dass die restlichen Dezimalstellen im Arcustangens abgeschnitten sind).

Auch Seth, es ist 3.141592653589793238463, nicht 64.

Berechnen Sie PI zur Kompilierzeit mit D.

(Kopiert von DSource.org )

/** Calculate pi at compile time
 *
 * Compile with dmd -c pi.d
 */
module calcpi;

import meta.math;
import meta.conv;

/** real evaluateSeries!(real x, real metafunction!(real y, int n) term)
 *
 * Evaluate a power series at compile time.
 *
 * Given a metafunction of the form
 *  real term!(real y, int n),
 * which gives the nth term of a convergent series at the point y
 * (where the first term is n==1), and a real number x,
 * this metafunction calculates the infinite sum at the point x
 * by adding terms until the sum doesn't change any more.
 */
template evaluateSeries(real x, alias term, int n=1, real sumsofar=0.0)
{
  static if (n>1 && sumsofar == sumsofar + term!(x, n+1)) {
     const real evaluateSeries = sumsofar;
  } else {
     const real evaluateSeries = evaluateSeries!(x, term, n+1, sumsofar + term!(x, n));
  }
}

/*** Calculate atan(x) at compile time.
 *
 * Uses the Maclaurin formula
 *  atan(z) = z - z^3/3 + Z^5/5 - Z^7/7 + ...
 */
template atan(real z)
{
    const real atan = evaluateSeries!(z, atanTerm);
}

template atanTerm(real x, int n)
{
    const real atanTerm =  (n & 1 ? 1 : -1) * pow!(x, 2*n-1)/(2*n-1);
}

/// Machin's formula for pi
/// pi/4 = 4 atan(1/5) - atan(1/239).
pragma(msg, "PI = " ~ fcvt!(4.0 * (4*atan!(1/5.0) - atan!(1/239.0))) );

Pi ist genau 3![Prof.Frink (Simpsons)]

Scherz, aber hier ist eines in C# (.NET-Framework erforderlich).

using System;
using System.Text;

class Program {
    static void Main(string[] args) {
        int Digits = 100;

        BigNumber x = new BigNumber(Digits);
        BigNumber y = new BigNumber(Digits);
        x.ArcTan(16, 5);
        y.ArcTan(4, 239);
        x.Subtract(y);
        string pi = x.ToString();
        Console.WriteLine(pi);
    }
}

public class BigNumber {
    private UInt32[] number;
    private int size;
    private int maxDigits;

    public BigNumber(int maxDigits) {
        this.maxDigits = maxDigits;
        this.size = (int)Math.Ceiling((float)maxDigits * 0.104) + 2;
        number = new UInt32[size];
    }
    public BigNumber(int maxDigits, UInt32 intPart)
        : this(maxDigits) {
        number[0] = intPart;
        for (int i = 1; i < size; i++) {
            number[i] = 0;
        }
    }
    private void VerifySameSize(BigNumber value) {
        if (Object.ReferenceEquals(this, value))
            throw new Exception("BigNumbers cannot operate on themselves");
        if (value.size != this.size)
            throw new Exception("BigNumbers must have the same size");
    }

    public void Add(BigNumber value) {
        VerifySameSize(value);

        int index = size - 1;
        while (index >= 0 && value.number[index] == 0)
            index--;

        UInt32 carry = 0;
        while (index >= 0) {
            UInt64 result = (UInt64)number[index] +
                            value.number[index] + carry;
            number[index] = (UInt32)result;
            if (result >= 0x100000000U)
                carry = 1;
            else
                carry = 0;
            index--;
        }
    }
    public void Subtract(BigNumber value) {
        VerifySameSize(value);

        int index = size - 1;
        while (index >= 0 && value.number[index] == 0)
            index--;

        UInt32 borrow = 0;
        while (index >= 0) {
            UInt64 result = 0x100000000U + (UInt64)number[index] -
                            value.number[index] - borrow;
            number[index] = (UInt32)result;
            if (result >= 0x100000000U)
                borrow = 0;
            else
                borrow = 1;
            index--;
        }
    }
    public void Multiply(UInt32 value) {
        int index = size - 1;
        while (index >= 0 && number[index] == 0)
            index--;

        UInt32 carry = 0;
        while (index >= 0) {
            UInt64 result = (UInt64)number[index] * value + carry;
            number[index] = (UInt32)result;
            carry = (UInt32)(result >> 32);
            index--;
        }
    }
    public void Divide(UInt32 value) {
        int index = 0;
        while (index < size && number[index] == 0)
            index++;

        UInt32 carry = 0;
        while (index < size) {
            UInt64 result = number[index] + ((UInt64)carry << 32);
            number[index] = (UInt32)(result / (UInt64)value);
            carry = (UInt32)(result % (UInt64)value);
            index++;
        }
    }
    public void Assign(BigNumber value) {
        VerifySameSize(value);
        for (int i = 0; i < size; i++) {
            number[i] = value.number[i];
        }
    }

    public override string ToString() {
        BigNumber temp = new BigNumber(maxDigits);
        temp.Assign(this);

        StringBuilder sb = new StringBuilder();
        sb.Append(temp.number[0]);
        sb.Append(System.Globalization.CultureInfo.CurrentCulture.NumberFormat.CurrencyDecimalSeparator);

        int digitCount = 0;
        while (digitCount < maxDigits) {
            temp.number[0] = 0;
            temp.Multiply(100000);
            sb.AppendFormat("{0:D5}", temp.number[0]);
            digitCount += 5;
        }

        return sb.ToString();
    }
    public bool IsZero() {
        foreach (UInt32 item in number) {
            if (item != 0)
                return false;
        }
        return true;
    }

    public void ArcTan(UInt32 multiplicand, UInt32 reciprocal) {
        BigNumber X = new BigNumber(maxDigits, multiplicand);
        X.Divide(reciprocal);
        reciprocal *= reciprocal;

        this.Assign(X);

        BigNumber term = new BigNumber(maxDigits);
        UInt32 divisor = 1;
        bool subtractTerm = true;
        while (true) {
            X.Divide(reciprocal);
            term.Assign(X);
            divisor += 2;
            term.Divide(divisor);
            if (term.IsZero())
                break;

            if (subtractTerm)
                this.Subtract(term);
            else
                this.Add(term);
            subtractTerm = !subtractTerm;
        }
    }
}

Diese Version (in Delphi) ist nichts Besonderes, aber zumindest schneller als die Version, die Nick Hodge auf seinem Blog gepostet hat :).Auf meinem Rechner dauert die Durchführung einer Milliarde Iterationen etwa 16 Sekunden, was einem Wert von entspricht 3.1415926525879 (der genaue Teil ist fett gedruckt).

program calcpi;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  start, finish: TDateTime;

function CalculatePi(iterations: integer): double;
var
  numerator, denominator, i: integer;
  sum: double;
begin
  {
  PI may be approximated with this formula:
  4 * (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 .......)
  //}
  numerator := 1;
  denominator := 1;
  sum := 0;
  for i := 1 to iterations do begin
    sum := sum + (numerator/denominator);
    denominator := denominator + 2;
    numerator := -numerator;
  end;
  Result := 4 * sum;
end;

begin
  try
    start := Now;
    WriteLn(FloatToStr(CalculatePi(StrToInt(ParamStr(1)))));
    finish := Now;
    WriteLn('Seconds:' + FormatDateTime('hh:mm:ss.zz',finish-start));
  except
    on E:Exception do
      Writeln(E.Classname, ': ', E.Message);
  end;
end.

Früher, mit kleinen Wortgrößen und langsamen oder nicht vorhandenen Gleitkommaoperationen, haben wir Dinge wie diese gemacht:

/* Return approximation of n * PI; n is integer */
#define pi_times(n) (((n) * 22) / 7)

Für Anwendungen, die nicht viel Präzision erfordern (z. B. Videospiele), ist dies sehr schnell und genau genug.

Wenn Sie wollen berechnen eine Annäherung an den Wert von π ist (aus irgendeinem Grund), sollten Sie einen binären Extraktionsalgorithmus ausprobieren. Bellards Verbesserung von BBP gibt PI in O(N^2) an.


Wenn Sie wollen erhalten eine Näherung des Werts von π, um Berechnungen durchzuführen, dann:

PI = 3.141592654

Zugegeben, das ist nur eine Annäherung und nicht ganz korrekt.Es liegt etwas mehr als 0,00000000004102 daneben.(vier Zehn-Billionstel, ungefähr 4/10,000,000,000).


Wenn Sie möchten Mathematik mit π, dann besorgen Sie sich einen Bleistift und Papier oder ein Computeralgebra-Paket und verwenden Sie den genauen Wert von π, π.

Wenn Sie wirklich eine Formel wollen, macht diese Spaß:

π = -ich ln(-1)

Die oben von Chris gepostete Brent-Methode ist sehr gut;Brent ist im Allgemeinen ein Gigant auf dem Gebiet der Arithmetik mit beliebiger Genauigkeit.

Wenn Sie nur die N-te Ziffer wollen, die berühmteBBP-Formelist nützlich in Hex

Berechnung von π aus der Kreisfläche :-)

<input id="range" type="range" min="10" max="960" value="10" step="50" oninput="calcPi()">
<br>
<div id="cont"></div>

<script>
function generateCircle(width) {
    var c = width/2;
    var delta = 1.0;
    var str = "";
    var xCount = 0;
    for (var x=0; x <= width; x++) {
        for (var y = 0; y <= width; y++) {
            var d = Math.sqrt((x-c)*(x-c) + (y-c)*(y-c));
            if (d > (width-1)/2) {
                str += '.';
            }
            else {
                xCount++;
                str += 'o';
            }
            str += "&nbsp;" 
        }
        str += "\n";
    }
    var pi = (xCount * 4) / (width * width);
    return [str, pi];
}

function calcPi() {
    var e = document.getElementById("cont");
    var width = document.getElementById("range").value;
    e.innerHTML = "<h4>Generating circle...</h4>";
    setTimeout(function() {
        var circ = generateCircle(width);
        e.innerHTML  = "<pre>" + "π = " + circ[1].toFixed(2) + "\n" + circ[0] +"</pre>";
    }, 200);
}
calcPi();
</script>

Besserer Ansatz

Um die Ausgabe von Standardkonstanten wie zu erhalten Pi oder die Standardkonzepte, sollten wir zunächst mit den integrierten Methoden arbeiten, die in der von Ihnen verwendeten Sprache verfügbar sind.Es wird den Wert auf die schnellste und beste Weise zurückgeben.Ich verwende Python, um den Wert pi am schnellsten zu ermitteln

  • pi-Variable der Mathematikbibliothek.Die Mathematikbibliothek speichert die Variable pi als Konstante.

math_pi.py

import math
print math.pi

Führen Sie das Skript mit dem Time-Dienstprogramm von Linux aus /usr/bin/time -v python math_pi.py

Ausgabe:

Command being timed: "python math_pi.py"
User time (seconds): 0.01
System time (seconds): 0.01
Percent of CPU this job got: 91%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.03
  • Verwenden Sie die Arc-Cos-Methode der Mathematik

acos_pi.py

import math
print math.acos(-1)

Führen Sie das Skript mit dem Time-Dienstprogramm von Linux aus /usr/bin/time -v python acos_pi.py

Ausgabe:

Command being timed: "python acos_pi.py"
User time (seconds): 0.02
System time (seconds): 0.01
Percent of CPU this job got: 94%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.03

bbp_pi.py

from decimal import Decimal, getcontext
getcontext().prec=100
print sum(1/Decimal(16)**k * 
          (Decimal(4)/(8*k+1) - 
           Decimal(2)/(8*k+4) - 
           Decimal(1)/(8*k+5) -
           Decimal(1)/(8*k+6)) for k in range(100))

Führen Sie das Skript mit dem Time-Dienstprogramm von Linux aus /usr/bin/time -v python bbp_pi.py

Ausgabe:

Command being timed: "python c.py"
User time (seconds): 0.05
System time (seconds): 0.01
Percent of CPU this job got: 98%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.06

Daher ist es am besten, die von der Sprache bereitgestellten integrierten Methoden zu verwenden, da diese am schnellsten und besten sind, um die Ausgabe zu erhalten.Verwenden Sie in Python math.pi

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top