Domanda

Sto cercando il modo più veloce per ottenere il valore di π, come sfida personale.Più specificamente, sto utilizzando modi che non implicano l'utilizzo #define costanti come M_PI, o codificando il numero in.

Il programma seguente testa i vari modi che conosco.La versione con assemblaggio in linea è, in teoria, l'opzione più veloce, anche se chiaramente non portatile.L'ho incluso come base per il confronto con le altre versioni.Nei miei test, con i built-in, il 4 * atan(1) è più veloce su GCC 4.2, perché ripiega automaticamente il file atan(1) in una costante.Con -fno-builtin specificato, il atan2(0, -1) la versione è più veloce.

Ecco il programma di test principale (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;
}

E le cose sull'assemblaggio in linea (fldpi.c) che funzionerà solo per i sistemi x86 e x64:

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

E uno script di build che crea tutte le configurazioni che sto testando (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

Oltre a testare tra vari flag del compilatore (ho confrontato anche 32 bit con 64 bit perché le ottimizzazioni sono diverse), ho anche provato a cambiare l'ordine dei test.Ma ancora, il atan2(0, -1) la versione risulta sempre migliore ogni volta.

È stato utile?

Soluzione

IL Metodo Montecarlo, come accennato, applica alcuni ottimi concetti ma, chiaramente, non è il più veloce, né di gran lunga né in alcun modo ragionevole.Inoltre, tutto dipende dal tipo di precisione che stai cercando.Il π più veloce che conosco è quello con le cifre codificate.Guardando Pi E Pi[PDF], ci sono molte formule.

Ecco un metodo che converge rapidamente: circa 14 cifre per iterazione. PiFast, l'applicazione attualmente più veloce, utilizza questa formula con la FFT.Scriverò semplicemente la formula, poiché il codice è semplice.Questa formula è stata quasi trovata da Ramanujan e scoperto da Chudnovsky.In realtà è così che ha calcolato diversi miliardi di cifre del numero, quindi non è un metodo da ignorare.La formula trabocca rapidamente e, poiché stiamo dividendo fattoriali, sarebbe vantaggioso ritardare tali calcoli per rimuovere i termini.

enter image description here

enter image description here

Dove,

enter image description here

Di seguito è riportato il Algoritmo di Brent-Salamina.Wikipedia lo menziona quando UN E B sono "abbastanza vicini" allora (a + b)² / 4t sarà un'approssimazione di π.Non sono sicuro di cosa significhi "abbastanza vicino", ma dai miei test, un'iterazione ha ottenuto 2 cifre, due hanno ottenuto 7 e tre hanno ottenuto 15, ovviamente questo è con i doppi, quindi potrebbe contenere un errore in base alla sua rappresentazione e IL VERO il calcolo potrebbe essere più accurato.

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)

Infine, che ne dici di un po' di pi golf (800 cifre)?160 caratteri!

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

Altri suggerimenti

Mi piace molto questo programma perché approssima π guardando la sua stessa area.

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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}

Ecco una descrizione generale di una tecnica per calcolare il pi greco che ho imparato al liceo.

Lo condivido solo perché penso che sia abbastanza semplice perché chiunque possa ricordarlo, indefinitamente, inoltre insegna il concetto dei metodi "Monte-Carlo" - che sono metodi statistici per arrivare a risposte che non sembrano immediatamente essere deducibile attraverso processi casuali.

Disegna un quadrato e inscrivi un quadrante (un quarto di semicerchio) all'interno di quel quadrato (un quadrante con raggio uguale al lato del quadrato, in modo da riempirne la maggior parte possibile)

Ora lancia una freccetta nel quadrato e registra dove si ferma, ovvero scegli un punto casuale ovunque all'interno del quadrato.Naturalmente è atterrato all'interno del quadrato, ma è all'interno del semicerchio?Registra questo fatto.

Ripeti questo processo molte volte e scoprirai che esiste un rapporto tra il numero di punti all'interno del semicerchio e il numero totale lanciato, chiama questo rapporto x.

Poiché l'area del quadrato è r per r, puoi dedurre che l'area del semicerchio è x per r per r (cioè x per r al quadrato).Quindi x per 4 ti darà pi greco.

Questo non è un metodo rapido da usare.Ma è un bell'esempio di metodo Monte Carlo.E se ti guardi intorno, potresti scoprire che molti problemi altrimenti al di fuori delle tue capacità computazionali possono essere risolti con tali metodi.

Nell'interesse della completezza, una versione del modello C++ che, per una compilazione ottimizzata, calcolerà un'approssimazione di PI in fase di compilazione e si inlineerà a un singolo valore.

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

Nota per I > 10, le build ottimizzate possono essere lente, allo stesso modo per le esecuzioni non ottimizzate.Per 12 iterazioni credo che ci siano circa 80.000 chiamate a value() (in assenza di memorizzazione).

In realtà c'è un intero libro dedicato (tra le altre cose) a veloce metodi per il calcolo di \pi:"Pi e l'Assemblea generale", di Jonathan e Peter Borwein (disponibile su Amazon).

Ho studiato parecchio l'AGM e i relativi algoritmi:è piuttosto interessante (anche se a volte non banale).

Tieni presente che per implementare gli algoritmi più moderni per calcolare \pi, avrai bisogno di una libreria aritmetica multiprecisione (GMP è una buona scelta, anche se è passato un po' di tempo dall'ultima volta che l'ho usata).

La complessità temporale dei migliori algoritmi è in O(M(n)log(n)), dove M(n) è la complessità temporale per la moltiplicazione di due interi a n bit (M(n)=O(n log(n) log(log(n))) utilizzando algoritmi basati su FFT, che di solito sono necessari quando si calcolano le cifre di \pi, e tale algoritmo è implementato in GMP).

Si noti che anche se la matematica dietro gli algoritmi potrebbe non essere banale, gli algoritmi stessi sono solitamente poche righe di pseudo-codice e la loro implementazione è solitamente molto semplice (se si sceglie di non scrivere la propria aritmetica multiprecisione :-)).

Le seguenti risposte esattamente come farlo nel modo più veloce possibile, con il minimo sforzo di elaborazione.Anche se la risposta non ti piace, devi ammettere che in effetti è il modo più veloce per ottenere il valore del PI.

IL PIÙ VELOCE il modo per ottenere il valore di Pi è:

1) Scegli il tuo linguaggio di programmazione preferito 2) Carica la sua libreria matematica 3) e scopri che PI è già definito lì - pronto per l'uso!

Nel caso in cui non hai una libreria di matematica a portata di mano..

IL SECONDO PIÙ VELOCE modo (soluzione più universale) è:

cerca Pi su Internet, ad es.Qui:

http://www.eveandersson.com/pi/digits/1000000 (1 milione di cifre..qual è la tua precisione in virgola mobile?)

o qui:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

o qui:

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

È davvero veloce trovare le cifre di cui hai bisogno per qualunque aritmetica di precisione desideri utilizzare e, definendo una costante, puoi assicurarti di non sprecare tempo prezioso della CPU.

Non solo questa è una risposta in parte divertente, ma in realtà, se qualcuno andasse avanti e calcolasse il valore di Pi in un'applicazione reale...sarebbe un grosso spreco di tempo della CPU, non è vero?Almeno non vedo una vera applicazione per provare a ricalcolarlo.

Caro moderatore:si prega di notare che l'OP ha chiesto:"Il modo più veloce per ottenere il valore di PI"

IL Formula BBP ti permette di calcolare l'ennesima cifra - in base 2 (o 16) - senza doverti preoccupare prima delle n-1 cifre precedenti :)

Invece di definire pi greco come costante, utilizzo sempre acos(-1).

Mi sono appena imbattuto in questo che dovrebbe essere qui per completezza:

calcolare il PI in Piet

Ha la proprietà piuttosto interessante che la precisione può essere migliorata rendendo il programma più grande.

Quici sono alcuni spunti sulla lingua stessa

Se Questo articolo è vero, allora il algoritmo che Bellard ha creato potrebbe essere uno dei più rapidi disponibili.Ha creato pi greco fino a 2,7 trilioni di cifre utilizzando un PC DESKTOP!

...e ha pubblicato il suo lavoro qui

Buon lavoro Bellard, sei un pioniere!

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

Questo è un metodo “classico”, molto semplice da implementare.Questa implementazione, in Python (linguaggio non così veloce) fa:

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)

Puoi trovare maggiori informazioni Qui.

Ad ogni modo, il modo più veloce per ottenere un valore preciso di pi greco in Python è:

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

ecco il codice sorgente per il metodo gmpy pi, non penso che il codice sia tanto utile quanto il commento in questo caso:

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

MODIFICARE: Ho avuto qualche problema con il copia e incolla e l'identificazione, comunque puoi trovare la fonte Qui.

Se per più veloce intendi il più veloce per digitare il codice, ecco il golfscript soluzione:

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

Usa la formula di Machin

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.

Implementato nello schema, ad esempio:

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

Se sei disposto ad usare un'approssimazione, 355 / 113 va bene per 6 cifre decimali e ha l'ulteriore vantaggio di essere utilizzabile con espressioni intere.Non è così importante al giorno d'oggi, poiché "coprocessore matematico in virgola mobile" ha smesso di avere alcun significato, ma una volta era piuttosto importante.

Con i doppi:

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

Questo sarà accurato fino a 14 cifre decimali, sufficienti a riempire un doppio (l'imprecisione è probabilmente dovuta al fatto che il resto dei decimali nell'arco tangente sono troncati).

Anche Seth, è 3.141592653589793238463, non 64.

Calcola PI in fase di compilazione con D.

(Copiato da 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 greco è esattamente 3![Il prof.Frink (Simpson)]

Scherzo, ma eccone uno in C# (è richiesto .NET Framework).

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

Questa versione (in Delphi) non è niente di speciale, ma è almeno più veloce di la versione che Nick Hodge ha pubblicato sul suo blog :).Sulla mia macchina, ci vogliono circa 16 secondi per fare un miliardo di iterazioni, dando un valore di 3.1415926525879 (la parte precisa è in grassetto).

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.

Ai vecchi tempi, con parole di piccole dimensioni e operazioni in virgola mobile lente o inesistenti, facevamo cose come queste:

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

Per le applicazioni che non richiedono molta precisione (ad esempio i videogiochi), è molto veloce e sufficientemente preciso.

Se lo desidera calcolare un'approssimazione del valore di π (per qualche motivo), dovresti provare un algoritmo di estrazione binaria. Quella di Bellard miglioramento di BBP dà PI in O(N^2).


Se lo desidera ottenere un'approssimazione del valore di π per fare i calcoli, quindi:

PI = 3.141592654

Certo, è solo un'approssimazione e non del tutto accurata.È fuori di poco più di 0,00000000004102.(quattro decimillesimi, circa 4/10,000,000,000).


Se vuoi farlo matematica con π, quindi procurati carta e matita o un pacchetto di algebra per computer e utilizza il valore esatto di π, π.

Se vuoi davvero una formula, questa è divertente:

π = -io ln(-1)

Il metodo di Brent pubblicato sopra da Chris è molto buono;Brent in generale è un gigante nel campo dell'aritmetica a precisione arbitraria.

Se tutto quello che vuoi è l'ennesima cifra, la famosaFormula BBPè utile in esadecimale

Calcolo di π dall'area del cerchio :-)

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

Approccio migliore

Per ottenere l'output di costanti standard come pi o i concetti standard, dovremmo prima utilizzare i metodi integrati disponibili nel linguaggio che stai utilizzando.Restituirà valore nel modo più veloce e migliore.Sto usando Python per ottenere il modo più veloce per ottenere il valore pi

  • variabile pi della libreria matematica.La libreria matematica memorizza la variabile pi come costante.

matematica_pi.py

import math
print math.pi

Esegui lo script con l'utilità time di Linux /usr/bin/time -v python math_pi.py

Produzione:

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
  • Utilizzare il metodo matematico dell'arco cos

acos_pi.py

import math
print math.acos(-1)

Esegui lo script con l'utilità time di Linux /usr/bin/time -v python acos_pi.py

Produzione:

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

Esegui lo script con l'utilità time di Linux /usr/bin/time -v python bbp_pi.py

Produzione:

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

Quindi il modo migliore è utilizzare il metodo integrato fornito dal linguaggio perché sono i più veloci e migliori per ottenere l'output.In Python usa math.pi

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top