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

stimmen
275

Ich bin auf der Suche nach dem schnellsten Weg , um den Wert von π, als eine persönliche Herausforderung zu erhalten. Genauer gesagt, verwende ich Möglichkeiten , die nicht mit einbeziehen #defineKonstanten wie M_PIoder Hartcodierung die Zahl in.

Das folgende Programm prüft die verschiedenen Möglichkeiten , die ich kenne. Die Inline - Assembler - Version ist in der Theorie, die schnellste Option, obwohl eindeutig nicht tragbar. Ich habe es als Grundlage enthalten gegenüber den anderen Versionen zu vergleichen. In meinen Tests mit Einbauten, die 4 * atan(1)die Version schnellsten auf GCC 4.2, weil es die Auto-Falten atan(1)in eine Konstante. Mit -fno-builtinangegeben, das atan2(0, -1)ist Version 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 die Inline - Montage Material ( fldpi.c) , die nur für x86 und x64 - Systemen funktioniert:

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

Und ein Build - Skript , das alle Konfigurationen baut 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 von der Prüfung zwischen verschiedenen Compiler - Flags (ich habe im Vergleich 32-Bit gegen 64-Bit zu, da die Optimierungen verschieden sind), ich habe auch versucht , die Reihenfolge der Tests Schalt um. Aber noch, die atan2(0, -1)kommt Version noch jedes Mal an der Spitze.

Veröffentlicht am 01/08/2008 um 06:21
quelle vom benutzer
In anderen Sprachen...                            


23 antworten

stimmen
180

Die Monte - Carlo - Methode , wie bereits erwähnt, gilt einige großen Konzepte , aber es ist klar, nicht die schnellste, nicht durch eine Totale, nicht durch eine vernünftige Maßnahme. Außerdem ist es hängt alles davon ab , welche Art von Genauigkeit , die Sie suchen. Der schnellste π ich kenne , ist das mit den Ziffern hart codiert. Mit Blick auf Pi und Pi [PDF] , gibt es eine Menge von Formeln.

Hier ist eine Methode , die schnell konvergiert - etwa 14 Stellen pro Iteration. PiFast , die aktuelle schnellste Anwendung, verwendet diese Formel mit der FFT . Ich schreibe nur die Formel, da der Code einfach. Diese Formel wurde fast durch gefunden Ramanujan und entdeckt von Chudnovsky . Es ist tatsächlich , wie er mehrere Milliarden Ziffern der Zahl berechnet - so ist es kein Verfahren außer Acht zu lassen ist. Die Formel wird überlaufen und schnell, da wir factorials sich teilen, ist es von Vorteil wäre , dann solche Berechnungen zu verzögern Bedingungen zu entfernen.

Geben Sie hier image description

Geben Sie hier image description

woher,

Geben Sie hier image description

Unten ist der Brent-Salamin Algorithmus . Wikipedia erwähnt , dass , wenn ein und b sind "nahe genug" , dann (a + b) ² / 4t wird eine Annäherung an π sein. Ich bin mir nicht sicher , was bedeutet „nahe genug“, aber aus meinen Tests, eine Iteration bekam 2 - stellig, zwei bekam 7 und drei 15 hatten natürlich dies mit Doppel, so dass es möglicherweise einen Fehler auf seiner Darstellung auf Basis hat und die wahre 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)

Schließlich, wie etwa einige pi Golf (800 Stellen)? 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);}
Beantwortet am 02/08/2008 um 19:22
quelle vom benutzer

stimmen
96

Ich mag dieses Programm, das durch einen Blick auf seinen eigenen Bereich pi annähert :-)

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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}
Beantwortet am 02/09/2008 um 14:28
quelle vom benutzer

stimmen
72

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

Ich dies nur teilen, weil ich denke, es ist einfach genug, dass jemand daran erinnern kann, auf unbestimmte Zeit, und es lehrt Sie das Konzept der „Monte-Carlo“ Methoden - die auf Antworten des Ankommens statistischen Methoden, die sein nicht sofort erscheinen ableitbar durch Zufallsprozesse.

Zeichnen ein Quadrat und einschreiben einen Quadranten (ein Viertel von einem Halbkreis) innerhalb dieses Quadrats (einen Quadranten mit einem Radius gleich der Seite des Quadrats, so füllt es, so viel von dem Platz wie möglich)

Jetzt einen Pfeil auf dem Platz werfen, und notieren Sie, wo er landet - das heißt, einen zufälligen Punkt irgendwo innerhalb des Quadrats wählen. Natürlich ist es im Quadrat gelandet, aber ist es im Innern des Halbkreises? Notieren Sie sich diese Tatsache.

Wiederholen Sie diesen Vorgang mehrmals - und Sie werden feststellen, es gibt ein Verhältnis der Anzahl von Punkten innerhalb des Halbkreises im Vergleich zu der Gesamtzahl geworfen, nennen das Verhältnis x.

Da die Fläche des Platzes r mal r ist, kann man ableiten, dass die Fläche des Halbkreises ist x-mal r mal r (das heißt, x-mal r squared). Daher x mal 4 werden Sie pi geben.

Dies ist keine schnelle Methode zu verwenden. Aber es ist ein schönes Beispiel für ein Verfahren Monte Carlo. Und wenn man sich umschaut, können Sie feststellen, dass viele Probleme sonst außerhalb Rechenfähigkeiten können durch solche Verfahren gelöst werden.

Beantwortet am 01/08/2008 um 14:37
quelle vom benutzer

stimmen
51

Im Interesse der Vollständigkeit, eine C ++ Template-Version, die für eine optimierte Build wird PI bei der Kompilierung berechnen und auf einen einzelnen Wert inline wird.

#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> 10 baut optimiert für nicht-optimierte läuft langsam, ebenfalls sein. Für 12 Wiederholungen glaube ich, gibt es rund 80k Anrufe an Wert () (in Abwesenheit von Memoisation).

Beantwortet am 22/12/2009 um 16:40
quelle vom benutzer

stimmen
40

Es gibt tatsächlich ein ganzes Buch gewidmet (unter anderem) auf schnelle Methoden zur Berechnung von \ pi: ‚Pi und die AGM‘ von Jonathan und Peter Borwein ( auf Amazon ).

Ich studierte an der Hauptversammlung und die damit verbundene Algorithmen ziemlich viel: es ist sehr interessant (wenn auch manchmal nicht-trivial).

Beachten Sie, dass die meisten modernen Algorithmen zu implementieren \ pi zu berechnen, benötigen Sie eine mehrfach arithmetische Bibliothek ( GMP ist eine ziemlich gute Wahl, obwohl es schon eine Weile her, seit ich verwendet es zuletzt).

Die Zeitkomplexität der besten Algorithmen ist in O (M (n) log (n)), wobei M (n) ist die Zeit-Komplexität für die Multiplikation zweier n-Bit-Integer (M (n) = O (n log (n) log (log (n))) unter Verwendung von FFT-Algorithmen basieren, die in der Regel benötigt werden, wenn Ziffern \ pi Berechnung und ein solcher Algorithmus wird in GMP implementiert).

Beachten Sie, dass, obwohl die Mathematik hinter den Algorithmen nicht trivial sein könnte, die Algorithmen selbst sind in der Regel ein paar Zeilen von Pseudo-Code, und deren Umsetzung ist in der Regel sehr einfach (wenn Sie nicht wählen Sie Ihre eigene Arithmetik :-) mehrfach schreiben).

Beantwortet am 24/08/2008 um 18:14
quelle vom benutzer

stimmen
36

Die folgenden Antworten genau , wie dies in der schnellstmöglichen Weise zu tun - mit dem geringsten Rechenaufwand . Auch wenn Sie die Antwort nicht mögen, müssen Sie zugeben , dass es tatsächlich der schnellste Weg zu bekommen , den Wert von PI.

Der schnellste Weg , um den Wert von Pi zu erhalten ist:

  1. wählen Sie Ihre bevorzugte Programmiersprache
  2. laden Sie es Mathe-Bibliothek
  3. und feststellen, dass Pi bereits dort definiert !! bereit, es zu benutzen ..

für den Fall, Sie haben keine Mathe-Bibliothek zur Hand ..

die zweitschnellste Weg (universellere Lösung) ist:

aufblicken Pi im Internet, zB hier:

http://www.eveandersson.com/pi/digits/1000000 (1 Million Stellen .. was ist Ihr Gleitkommagenauigkeit?)

oder hier:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

oder hier:

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

Es ist wirklich schnell, um die Ziffern finden Sie müssen für was auch immer Arithmetik Sie möchten, verwenden, und durch eine konstante definieren, können Sie sicherstellen, dass Sie keine wertvolle CPU-Zeit vergeuden Sie.

Dies ist nicht nur eine teilweise humorvolle Antwort, aber in Wirklichkeit, wenn jemand würde voran gehen und berechnet den Wert von Pi in einer realen Anwendung .., dass eine ziemlich große Verschwendung von CPU-Zeit wäre, wäre es nicht? Wenigstens sehe ich keine wirkliche Anwendung zu versuchen, diese neu zu berechnen.

Lieber Moderator: Bitte beachten Sie, dass die OP fragte: „schnellster Weg , um den Wert von PI zu erhalten“

Beantwortet am 28/10/2011 um 02:02
quelle vom benutzer

stimmen
25

Die BBP Formel ermöglicht die n - te Ziffer zu berechnen , - in der Basis 2 (oder 16) - , ohne dass auch bei den vorhergehenden n-1 Stellen stören ersten :)

Beantwortet am 29/08/2008 um 10:22
quelle vom benutzer

stimmen
21

Stattdessen pi als eine Konstante zu definieren, verwende ich immer acos(-1).

Beantwortet am 08/03/2009 um 04:02
quelle vom benutzer

stimmen
20

Wenn dieser Artikel wahr ist, dann ist der Algorithmus, der Bellard erstellt hat , könnte eine der schnellsten zur Verfügung. Er hat pi auf 2,7 Billionen Ziffern erstellt einen Desktop - PC!

... und er hat seine veröffentlichte Arbeit hier

Gute Arbeit Bellard, Sie sind ein Pionier!

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

Beantwortet am 06/01/2010 um 13:41
quelle vom benutzer

stimmen
20

Gerade kam in dieser eine, die der Vollständigkeit halber hier sein sollte:

berechnet PI in Piet

Es hat die ziemlich nett Eigenschaft, dass die Präzision machen das Programm größer verbessert werden kann.

Hier sind einige Einblicke in die Sprache selbst

Beantwortet am 12/01/2009 um 19:46
quelle vom benutzer

stimmen
19

Dies ist eine „klassische“ Methode, sehr einfach zu implementieren. Diese Implementierung in Python (nicht so schnell Sprache) tut es:

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)

Sie können mehr Informationen finden Sie hier .

Wie auch immer der schnellste Weg, um einen präzisen wie-viel-as-you-want Wert von Pi zu erhalten in Python ist:

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

hier ist das Stück Quelle für die gmpy pi Methode, glaube ich nicht, der Code so viel nützlich als Kommentar in diesem Fall:

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

EDIT: Ich hatte einige Probleme mit Ausschneiden und Einfügen und identation, trotzdem können Sie die Quelle finden hier .

Beantwortet am 02/10/2008 um 22:27
quelle vom benutzer

stimmen
17

Wenn Sie mit dem schnellsten meinen Sie am schnellsten in den Code eingeben, hier ist die golfscript Lösung:

;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;
Beantwortet am 06/08/2008 um 23:54
quelle vom benutzer

stimmen
15

Verwenden Sie die Machin artige 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.

Implementiert in Schema, zum Beispiel:

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

Beantwortet am 05/02/2011 um 06:26
quelle vom benutzer

stimmen
15

Mit Doppel:

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

Dies genau ist bis zu 14 Dezimalstellen, genug, um eine Doppel zu füllen (die Ungenauigkeit ist wahrscheinlich, weil der Rest der Dezimalstellen in den Bogen Tangenten sind abgeschnitten).

Auch Seth, es ist 3,14159265358979323846 3 , nicht mehr als 64.

Beantwortet am 28/02/2010 um 04:52
quelle vom benutzer

stimmen
15

Wenn Sie bereit sind , eine Annäherung zu verwenden, 355 / 113ist gut für 6 Dezimalstellen und hat den zusätzlichen Vorteil , mit ganzzahligen Ausdrücken verwendbar ist. Das ist nicht so wichtig , in diesen Tagen, als „Floating - Point - mathematischen Co-Prozessor“ nicht mehr einen Sinn hat, aber es war ziemlich einmal wichtig.

Beantwortet am 17/09/2009 um 17:30
quelle vom benutzer

stimmen
15

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

Witz, aber hier ist ein 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;
        }
    }
}
Beantwortet am 26/02/2009 um 20:22
quelle vom benutzer

stimmen
15

Berechnen PI zur Compile-Zeit 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))) );
Beantwortet am 17/09/2008 um 18:49
quelle vom benutzer

stimmen
13

Diese Version (in Delphi) ist nichts Besonderes, aber es ist zumindest schneller als die Version Nick Hodge auf seinem Blog gepostet :). Auf meinem Rechner es etwa 16 Sekunden dauert , eine Milliarde Iterationen zu tun, einen Wert zu geben 3,14159265 (ist der genaue Teil fett gedruckt) 25879.

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.
Beantwortet am 12/01/2009 um 19:24
quelle vom benutzer

stimmen
12

Wenn Sie möchten berechnen eine Annäherung an den Wert von π (aus irgendeinem Grund), sollten Sie einen binären Extraktionsalgorithmus versuchen. Bellard die Verbesserung der BBP gibt tut PI in O (N ^ 2).


Wenn Sie möchten , erhalten eine Annäherung an den Wert von π Berechnungen zu tun, dann:

PI = 3.141592654

Zugegeben, das ist nur eine Annäherung, und nicht ganz korrekt. Es ist ein wenig mehr als ,00000000004102 ab. (vier von zehn Milliardstel, etwa 4 / 10000000000 ).


Wenn Sie wollen , Mathe mit π, dann holen Sie sich einen Bleistift und Papier oder ein Computer - Algebra - Paket, und π der genaue Wert verwenden, π.

Wenn Sie wirklich eine Formel, dann ist dies ein Spaß:

π = - i ln (-1)

Beantwortet am 22/12/2009 um 22:13
quelle vom benutzer

stimmen
12

Zurück in den alten Tagen, mit kleinen Wortgrößen und langsam oder gar nicht vorhanden Gleitkommaoperationen, haben wir Sachen wie dies zu tun:

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

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

Beantwortet am 20/02/2009 um 22:21
quelle vom benutzer

stimmen
11

Brent-Verfahren geschrieben oben von Chris ist sehr gut; Brent ist in der Regel ein Riese im Bereich beliebiger Genauigkeit Arithmetik.

Wenn alles , was Sie die N - te Ziffer wollen, die berühmte BBP Formel ist in hex nützlich

Beantwortet am 04/08/2009 um 22:39
quelle vom benutzer

stimmen
1

Die Berechnung π aus 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>

Beantwortet am 03/06/2017 um 17:13
quelle vom benutzer

stimmen
0

besserer Ansatz

Um die Ausgabe von Standard - Konstanten wie zu bekommen pi oder die Standardkonzepte, sollten wir zunächst mit den builtins Methoden zur Verfügung , die Sprache gehen , die Sie verwenden. Es wird wieder Wert auf dem schnellsten Weg und beste Art und Weise auch. Ich verwende Python den schnellsten Weg , um den Wert pi zu erhalten

  • pi Variable der Mathematik - Bibliothek . Math Bibliothek speichert die Variable PI als konstant.

math_pi.py

import math
print math.pi

Führen Sie das Skript mit der Zeit Nutzen von Linux /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 arc cos Methode math

acos_pi.py

import math
print math.acos(-1)

Führen Sie das Skript mit der Zeit Nutzen von Linux /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 der Zeit Nutzen von Linux /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

So ist bester Weg, Methode, mit der Sprache Ursache feststellen zu können builtins sie sind die am schnellsten und am besten die Ausgabe zu erhalten. In Python Verwendung math.pi

Beantwortet am 18/06/2018 um 10:07
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more