Care este cel mai rapid mod de a obține valoarea lui π?

voturi
275

Caut cel mai rapid mod de a obține valoarea π, ca o provocare personală. Mai precis, eu sunt , folosind metode care nu implică utilizarea de #defineconstante cum ar fi M_PI, sau hard-codare numărul în.

Programul de mai jos testează diferitele moduri pe care le cunosc de. Versiunea de asamblare inline este, în teorie, cea mai rapidă opțiune, deși în mod clar nu portabil. L - am inclus ca o linie de referinta pentru a compara comparație cu celelalte versiuni. În testele mele, cu built-in-uri, The 4 * atan(1)versiune este cel mai rapid pe GCC 4.2, deoarece auto-pliază atan(1)într - o constantă. Cu -fno-builtinspecificată, atan2(0, -1)versiunea este cea mai rapidă.

Iată programul principal de testare ( 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;
}

Și chestii de asamblare în linie ( fldpi.c) , care va funcționa numai pentru sistemele x86 și x64:

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

Și un script construi care construiește toate configurațiile Testez ( 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

În afară de testarea între diferite steaguri compilator (l - am comparat pe 32 de biți față de 64-biți prea, pentru că optimizările sunt diferite), am încercat , de asemenea , trecerea de ordinea testelor din jur. Dar , totuși, atan2(0, -1)versiunea încă iese pe partea de sus de fiecare dată.

Întrebat 01/08/2008 la 06:21
sursa de către utilizator
În alte limbi...                            


23 răspunsuri

voturi
180

Metoda Monte Carlo , după cum sa menționat, se aplică unele concepte mari , dar este, în mod clar, nu cel mai rapid, nu printr - o lovitură de lungă, nu prin nici o măsură rezonabilă. De asemenea, totul depinde de ce fel de precizie pe care il cautati. Cel mai rapid tt eu știu este cea cu cifre greu codificate. Privind la Pi și Pi [PDF] , există o mulțime de formule.

Aici este o metodă care converge rapid - aproximativ 14 cifre pentru fiecare repetare. PiFast , cel mai rapid aplicația curentă, folosește această formulă cu FFT . Voi scrie doar cu formula, deoarece codul este simplu. Această formulă a fost aproape găsit de Ramanujan și descoperit de Chudnovsky . De fapt , este modul în care el a calculat mai multe miliarde de cifre ale numărului - deci nu este o metodă de a ignora. Formula va revărsa rapid și, din moment ce suntem divizarea factorialele, ar fi avantajos atunci să întârzie astfel de calcule pentru a elimina termeni.

introduceți descrierea imaginii aici

introduceți descrierea imaginii aici

Unde,

introduceți descrierea imaginii aici

Mai jos este algoritmul Brent-Salamin . Wikipedia menționează că , atunci când a și b sunt „suficient de aproape“ , atunci (a + b) ² / 4t va fi o aproximare a π. Nu sunt sigur ce „suficient de aproape“ înseamnă, dar din testele mele, o repetare a primit 2 cifre, doi s- au 7, iar trei au avut 15, desigur , acest lucru este cu dublu, așa că ar fi o eroare bazată pe reprezentarea sa și adevăratul calcul ar putea fi mai exacte.

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)

În cele din urmă, cum despre unele pi golf (800 cifre)? 160 de caractere!

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);}
Publicat 02/08/2008 la 19:22
sursa de către utilizator

voturi
96

Îmi place foarte mult acest program, care se apropie pi de privirea de la propria sa zonă :-)

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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}
Publicat 02/09/2008 la 14:28
sursa de către utilizator

voturi
72

Iată o descriere generală a unei tehnici de calcul pi pe care am învățat în liceu.

Eu împărtășesc numai acest lucru, deoarece cred că este destul de simplu ca oricine poate aminti, pe termen nelimitat, plus te învață conceptul de „Monte-Carlo“ metode - care sunt metode statistice de a ajunge la răspunsuri care nu apar imediat să fie prin procese aleatoare deductibile.

Desena un pătrat, și un cadran sapă (un sfert de semi-cerc) în interiorul acelui pătrat (un cadran cu rază egală cu latura pătratului, astfel încât să umple cât de pătrat posibil)

Acum, arunca o săgeată la pătrat, și în cazul în care terenurile înregistrează - adică, pentru a alege un punct aleatoriu oriunde în interiorul pătrat. Desigur, ea a aterizat în interiorul pătrat, dar este în interiorul semi-cerc? Înregistrați acest fapt.

Se repetă acest proces de mai multe ori - și veți găsi acolo este un raport de numărul de puncte în interiorul semicercului în raport cu numărul total de aruncat, numesc acest raport de x.

Deoarece aria pătratului este de ori r r, puteți deduce că zona cercului semi este de x ori r ori r (adică, x ori r pătrat). Prin urmare x 4 ori va da pi.

Aceasta nu este o metodă rapidă de a utiliza. Dar este un frumos exemplu al unei metode Monte Carlo. Și dacă te uiți în jur, puteți constata că multe probleme în caz contrar în afara abilitățile de calcul pot fi rezolvate prin astfel de metode.

Publicat 01/08/2008 la 14:37
sursa de către utilizator

voturi
51

În interesul completitudinii, o versiune C ++ șablon, care, pentru o construcție optimizată va calcula PI la momentul compilarii si va inline o singură valoare.

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

Notă pentru I> 10, optimizat construiește poate fi lent, de asemenea, pentru tiraje neoptimizate. Pentru 12 iterații cred că sunt în jur de 80K apelurile la valoarea () (în absența memoisation).

Publicat 22/12/2009 la 16:40
sursa de către utilizator

voturi
40

Există de fapt o carte întreagă dedicată (printre altele) pentru a rapid metode de calcul al \ pi: „Pi și AGA“, de Jonathan și Peter Borwein ( disponibil pe Amazon ).

Am studiat AGA și algoritmi conexe destul de un pic: este destul de interesant (deși, uneori, non-trivială).

Rețineți că , pentru a pune în aplicare cele mai moderne algoritmi pentru a calcula \ pi, veți avea nevoie de o bibliotecă aritmetică multiprecision ( GMP este o alegere destul de bun, deși a trecut ceva timp de când am folosit -o ultima dată).

Termenul Complexitatea mai buni algoritmi este O (M (n) log (n)), unde M (n) este timp complexitatea pentru înmulțirea a două numere întregi n biți (M (n) = O (n log (n) log (log (n))) folosind algoritmi FFT pe bază, care sunt necesare în mod obișnuit atunci când se calculează cifrele de \ pi, iar un astfel de algoritm este implementat în GMP).

Rețineți că, deși matematica din spatele algoritmii s-ar putea să nu fie triviale, algoritmii înșiși sunt, de obicei câteva linii de pseudo-cod, iar punerea în aplicare a acestora este de obicei foarte simplu (dacă ați ales să nu scrie opinia ta aritmetică multiprecision :-)).

Publicat 24/08/2008 la 18:14
sursa de către utilizator

voturi
36

Următoarele răspunsuri exact cum se face acest lucru în cel mai rapid mod posibil - cu cel mai mic efort de calcul . Chiar dacă nu - ți place răspunsul, trebuie să recunosc că este într - adevăr cel mai rapid mod de a obține valoarea PI.

Mai rapid mod de a obține valoarea lui Pi este:

  1. a ales limbajul de programare preferat
  2. încărca biblioteca lui l Math
  3. și pentru a găsi că Pi este definit deja acolo !! gata să-l folosească ..

în cazul în care nu aveți o bibliotecă matematica la îndemână ..

cea mai rapida modalitate (soluție mai universală) este:

căuta Pi pe internet, de exemplu aici:

http://www.eveandersson.com/pi/digits/1000000 (1 milion de cifre .. ceea ce este punctul de precizie plutitoare ta?)

sau aici:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

sau aici:

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

Este foarte rapid pentru a găsi cifre care aveți nevoie pentru orice aritmetică de precizie pe care doriți să o utilizați și prin definirea o constantă, puteți să vă asigurați că nu pierdeți timp prețios CPU.

Nu numai ca este un răspuns parțial plin de umor, dar în realitate, dacă cineva ar merge mai departe și calcula valoarea lui Pi într-o aplicație reală .. care ar fi destul de mare pierdere de timp CPU, nu-i așa? Cel puțin eu nu văd o cerere reală pentru încercarea de a re-calcula acest lucru.

Dragă Moderator: Vă rugăm să rețineți că PO DCA a întrebat: „Cel mai rapid mod de a obține valoarea PI“

Publicat 28/10/2011 la 02:02
sursa de către utilizator

voturi
25

Formula BBP vă permite să calculeze cifra nth - în baza 2 (sau 16) - fără a fi nevoie să deranjeze chiar și cu anterioare n-1 cifre primul :)

Publicat 29/08/2008 la 10:22
sursa de către utilizator

voturi
21

In loc de a defini pi ca o constantă, eu folosesc întotdeauna acos(-1).

Publicat 08/03/2009 la 04:02
sursa de către utilizator

voturi
20

În cazul în care acest articol este adevărat, atunci algoritmul care Bellard a creat ar putea fi una dintre cele mai rapide disponibile. El a creat pi la 2,7 trilioane de cifre folosind un PC DESKTOP!

... și el a publicat său de lucru aici

Bună treabă Bellard, esti un pionier!

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

Publicat 06/01/2010 la 13:41
sursa de către utilizator

voturi
20

Tocmai am dat peste aceasta, care ar trebui să fie aici pentru completare:

calcula PI în Piet

Ea are proprietatea destul de frumos, că precizia poate fi îmbunătățită ceea ce face programul mai mare.

Aici e unele introspecție în limba în sine

Publicat 12/01/2009 la 19:46
sursa de către utilizator

voturi
19

Aceasta este o metoda „clasica“, foarte ușor de implementat. Această punere în aplicare, în Python (limba nu atât de repede) o face:

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)

Puteți găsi mai multe informații aici .

Oricum cel mai rapid mod de a obține o precizie cât de mult--as-you-vreau valoarea lui pi în Python este:

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

aici este piesa de sursă pentru metoda pi gmpy, nu cred că acest cod este la fel de mult ca și util comentariu în acest caz:

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: Am avut unele probleme cu cut și paste și identation, oricum puteți găsi sursa aici .

Publicat 02/10/2008 la 22:27
sursa de către utilizator

voturi
17

Dacă prin cel mai rapid te referi cel mai rapid să tastați în codul, aici e golfscript soluția:

;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;
Publicat 06/08/2008 la 23:54
sursa de către utilizator

voturi
15

Utilizați formula Machin-like

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.

Pus în aplicare în schema, de exemplu:

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

Publicat 05/02/2011 la 06:26
sursa de către utilizator

voturi
15

Cu dublu:

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

Acest lucru va fi corecte până la 14 zecimale, suficient pentru a umple un dublu (inexactitatea este, probabil, pentru că restul de zecimale în tangentele arc sunt trunchiate).

De asemenea , Seth, e 3.14159265358979323846 3 , nu 64.

Publicat 28/02/2010 la 04:52
sursa de către utilizator

voturi
15

Dacă sunteți dispus să utilizați o aproximare, 355 / 113este bun pentru 6 cifre zecimale, și are avantajul de a fi ușor de utilizat cu expresii întregi. Nu e la fel de important în aceste zile, ca „plutitoare punct de matematica co-procesor“ a încetat să mai aibă nici un sens, dar a fost destul de important o dată.

Publicat 17/09/2009 la 17:30
sursa de către utilizator

voturi
15

Pi este exact 3! [Prof. Frink (Simpsons)]

Glumă, dar aici e una în C # (.NET Framework-necesar).

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;
        }
    }
}
Publicat 26/02/2009 la 20:22
sursa de către utilizator

voturi
15

Se calculează PI la compilare-timp cu D.

(Copiat din 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))) );
Publicat 17/09/2008 la 18:49
sursa de către utilizator

voturi
13

Această versiune (în Delphi) este nimic special, dar este cel puțin mai rapid decât versiunea Nick Hodge a postat pe blogul său :). Pe masina mea, este nevoie de aproximativ 16 secunde pentru a face un miliard de iterații, oferind o valoare de 3.14159265 25879 (partea exactă este în caractere aldine).

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.
Publicat 12/01/2009 la 19:24
sursa de către utilizator

voturi
12

Dacă doriți să calcula o aproximare a valorii π (pentru un motiv sau altul), ar trebui să încercați un algoritm de extracție binar. Bellard lui îmbunătățirea BBP dă face PI în O (N ^ 2).


Dacă doriți să obțină o aproximare a valorii π de a face calcule, atunci:

PI = 3.141592654

Desigur, asta e doar o aproximare, și nu în întregime corecte. Este oprit de un pic mai mult decât 0.00000000004102. (patru zece-trillionths, aproximativ 4 / 10000000000 ).


Dacă vrei să faci matematica cu π, apoi du - te un creion și hârtie sau un pachet de algebră calculator, și de a folosi valoarea exactă a lui π, π.

Dacă doriți cu adevărat o formulă, aceasta este distractiv:

π = - i ln (-1)

Publicat 22/12/2009 la 22:13
sursa de către utilizator

voturi
12

Înapoi în zilele vechi, cu dimensiuni de cuvinte mici și operațiuni lente sau inexistente în virgulă mobilă, am folosit pentru a face chestii de genul:

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

Pentru aplicații care nu necesită o mulțime de precizie (jocuri video, de exemplu), acest lucru este foarte rapid și este suficient de precisă.

Publicat 20/02/2009 la 22:21
sursa de către utilizator

voturi
11

Metoda lui Brent postat mai sus de Chris este foarte bun; Brent, în general, este un gigant în domeniul aritmetice arbitrare-precizie.

Dacă tot ce vrei este cifra N - lea, celebra formula BBP este util în hex

Publicat 04/08/2009 la 22:39
sursa de către utilizator

voturi
1

Calcularea π din zona de cerc :-)

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

Publicat 03/06/2017 la 17:13
sursa de către utilizator

voturi
0

O mai bună abordare

Pentru a obține producția de constantelor standard , cum ar fi pi sau conceptele standard, ar trebui să meargă mai întâi cu metodele disponibile comenzi interne limba pe care îl utilizați. Acesta va reveni valoare în cel mai rapid mod și cel mai bun mod de asemenea. Sunt folosind Python pentru a obține cel mai rapid mod de a obține pi valoare

  • pi variabilă a bibliotecii matematică . Biblioteca Math stoca pi variabilă constantă.

math_pi.py

import math
print math.pi

Rulați scriptul cu utilitate timp de Linux /usr/bin/time -v python math_pi.py

ieşire:

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
  • Utilizați arc cos metoda de matematica

acos_pi.py

import math
print math.acos(-1)

Rulați scriptul cu utilitate timp de Linux /usr/bin/time -v python acos_pi.py

ieşire:

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))

Rulați scriptul cu utilitate timp de Linux /usr/bin/time -v python bbp_pi.py

ieşire:

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

Deci, cel mai bun mod este de a utiliza metoda comenzilor interne furnizate de cauza limbă pe care sunt cele mai rapide și cele mai bune pentru a obține de ieșire. În piton utilizare math.pi

Publicat 18/06/2018 la 10:07
sursa de către utilizator

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