Quel est le meilleur moyen pour obtenir la valeur de π?

voix
275

Je cherche le meilleur moyen d'obtenir la valeur de π, comme un défi personnel. Plus précisément, j'utilise des moyens qui ne comportent pas en utilisant des #defineconstantes comme M_PI, ou coder en dur le numéro.

Le programme teste ci - dessous les différentes façons que je connais. La version de montage en ligne est, en théorie, l'option la plus rapide, mais pas clairement portable. Je l' ai inclus comme référence pour comparer par rapport aux autres versions. Dans mes tests, avec built-ins, la 4 * atan(1)version est plus rapide sur GCC 4.2, car il se replie automatiquement la atan(1)dans une constante. Avec -fno-builtinspécifié, la atan2(0, -1)version est plus rapide.

Voici le programme de test principal ( 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;
}

Et les trucs de montage en ligne ( fldpi.c) qui ne fonctionne que pour les systèmes x86 et x64:

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

Et un script de construction qui construit toutes les configurations que je 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

En plus des tests entre les différents drapeaux du compilateur (je l' ai comparé 32 bits contre 64 bits aussi, parce que les différents Optimisations sont), je l' ai aussi essayé de commutation de l'ordre des essais autour. Mais encore, la atan2(0, -1)version est toujours en tête à chaque fois.

Créé 01/08/2008 à 06:21
source utilisateur
Dans d'autres langues...                            


23 réponses

voix
180

La méthode de Monte Carlo , tel que mentionné, applique quelques grands concepts , mais il est, clairement, pas le plus rapide, et non pas par un long shot, non pas par toute mesure raisonnable. En outre, tout dépend de quel genre de précision que vous recherchez. Le plus rapide π que je connaisse est celui avec les chiffres codés en dur. En regardant Pi et Pi [PDF] , il y a beaucoup de formules.

Voici une méthode qui converge rapidement - environ 14 chiffres par itération. PiFast , l'application la plus rapide actuelle, utilise cette formule avec la FFT . Je vais juste écrire la formule, puisque le code est simple. Cette formule a été presque trouvé par Ramanujan et découvert par Chudnovsky . Il est en fait la façon dont il a calculé plusieurs milliards de chiffres du numéro - il est donc pas une méthode pour ne pas tenir compte. La formule débordera rapidement et, puisque nous divisons factorielles, il serait alors avantageux de retarder ces calculs pour supprimer des termes.

entrez la description d'image ici

entrez la description d'image ici

où,

entrez la description d'image ici

Ci - dessous l' algorithme Brent-Salamin . Wikipedia mentionne que , quand a et b sont "assez proche" , puis (a + b) ² / 4t sera une approximation de π. Je ne suis pas sûr de ce que « assez proche » signifie, de mes tests, une itération a obtenu 2 chiffres, deux ont obtenu 7, et trois avaient 15, bien sûr , c'est avec double, il aurait une erreur en fonction de sa représentation et le vrai calcul pourrait être plus précis.

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)

Enfin, que diriez-vous au golf pi (800 chiffres)? 160 caractères!

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);}
Créé 02/08/2008 à 19:22
source utilisateur

voix
96

Je aime vraiment ce programme, qui se rapproche de pi en regardant son propre :-)

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()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}
Créé 02/09/2008 à 14:28
source utilisateur

voix
72

Voici une description générale d'une technique de calcul pi que j'ai appris au lycée.

Je partage seulement cela parce que je pense qu'il est assez simple que tout le monde peut le rappeler, indéfiniment, plus il vous enseigne le concept de méthodes « Monte-Carlo » - qui sont des méthodes statistiques d'arriver à des réponses qui ne semblent pas immédiatement être déduisent par des processus aléatoires.

Dessiner un carré, et inscrire un quadrant (un quart d'un demi-cercle) à l'intérieur de ce carré (un quart de cercle avec un rayon égal au côté du carré, de sorte qu'il remplisse autant de place que possible)

Maintenant lancer une fléchette sur la place, et enregistrer où il atterrit - qui est, choisir un point aléatoire partout à l'intérieur du carré. Bien sûr, il a atterri à l'intérieur de la place, mais est-ce à l'intérieur du demi-cercle? Enregistrez ce fait.

Répétez ce processus plusieurs fois - et vous constaterez qu'il ya un rapport entre le nombre de points à l'intérieur du demi-cercle par rapport au nombre total jeté, appelez ce ratio x.

Étant donné que la superficie de la place est r fois r, vous pouvez en déduire que la zone du demi-cercle est x fois r fois r (qui est, x fois r au carré). Par conséquent x fois 4 vous donnera pi.

Ce n'est pas une méthode rapide à utiliser. Mais il est un bel exemple d'une méthode de Monte Carlo. Et si vous regardez autour, vous pouvez constater que de nombreux problèmes autrement en dehors de vos compétences informatiques peuvent être résolus par ces méthodes.

Créé 01/08/2008 à 14:37
source utilisateur

voix
51

Dans l'intérêt de l'exhaustivité, une version de modèle C ++, qui, pour une construction optimisée calculera PI au moment de la compilation et sera inline à une valeur unique.

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

Note pour I> 10, optimisé construit peut être lent, même pour des courses non optimisées. Pour 12 itérations Je crois qu'il ya autour 80k appels à la valeur () (en l'absence de mémoïsation).

Créé 22/12/2009 à 16:40
source utilisateur

voix
40

Il y a en fait un livre entier dédié (entre autres) à rapide des méthodes pour le calcul de \ pi: « Pi et l'assemblée générale annuelle », par Jonathan et Peter Borwein ( disponible sur Amazon ).

J'ai étudié l'assemblée générale annuelle et les algorithmes associés un peu: il est très intéressant (bien que parfois non trivial).

Notez que pour mettre en œuvre la plupart des algorithmes modernes pour calculer \ pi, vous aurez besoin d' une bibliothèque d' arithmétique Multiprécision ( GMP est un très bon choix, mais il a été un moment que je l' utilisais).

Le temps complexité des meilleurs algorithmes est en O (M (n) log (n)), où M (n) est le temps de la complexité de la multiplication de deux nombres entiers n bits (M (n) = O (n log (n) log (log (n))) en utilisant des algorithmes à base de FFT, qui sont habituellement nécessaires pour le calcul de chiffres \ pi, et un tel algorithme est mis en oeuvre dans GMP).

Notez que même si les mathématiques derrière les algorithmes pourraient ne pas être trivial, les algorithmes eux-mêmes sont généralement quelques lignes de pseudo-code, et leur mise en œuvre est généralement très simple (si vous avez choisi de ne pas écrire votre propre arithmétique :-) Multiprécision).

Créé 24/08/2008 à 18:14
source utilisateur

voix
36

Les réponses suivantes précisément comment faire cela dans le plus rapide possible - avec le moindre effort de calcul . Même si vous ne voulez pas la réponse, il faut admettre qu'il est en effet le meilleur moyen de faire la valeur de PI.

La FASTEST façon d'obtenir la valeur de Pi est:

  1. choisissez votre langage de programmation favori
  2. charger la bibliothèque mathématique de ce
  3. et constater que Pi y est déjà défini !! prêt à l'utiliser ..

Si vous ne disposez pas d'une bibliothèque mathématique à portée de main ..

le deuxième meilleur moyen (plus de solution universelle) est:

regarder Pi sur Internet, par exemple ici:

http://www.eveandersson.com/pi/digits/1000000 (1 million de chiffres .. quel est votre précision en virgule flottante?)

ou ici:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

ou ici:

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

Il est vraiment rapide pour trouver les chiffres dont vous avez besoin pour quelque arithmétique précision que vous souhaitez utiliser, et en définissant une constante, vous pouvez vous assurer que vous ne perdez pas de temps CPU précieux.

Non seulement est-ce une réponse humoristique en partie, mais en réalité, si quelqu'un serait aller de l'avant et de calculer la valeur de Pi dans une application réelle .. ce serait une perte assez importante de temps CPU, ne serait-il? Je ne vois pas une application réelle au moins pour essayer de re-calculer cela.

Cher Modérateur: S'il vous plaît noter que l'OP a demandé: « meilleur moyen d'obtenir la valeur de PI »

Créé 28/10/2011 à 02:02
source utilisateur

voix
25

La formule BBP permet de calculer le n - ième chiffre - dans la base 2 (ou 16) - sans avoir à se préoccuper de même les n-1 derniers chiffres première :)

Créé 29/08/2008 à 10:22
source utilisateur

voix
21

Au lieu de définir pi comme une constante, je l' utilise toujours acos(-1).

Créé 08/03/2009 à 04:02
source utilisateur

voix
20

Si cet article est vrai, alors l' algorithme qui Bellard a créé pourrait être l' un des plus rapide disponible. Il a créé pi à 2,7 BILLIONS chiffres à l' aide d' un PC DESKTOP!

... et il a publié son travail ici

Un bon travail Bellard, Vous êtes un pionnier!

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

Créé 06/01/2010 à 13:41
source utilisateur

voix
20

Juste suis tombé sur ce qui devrait être ici pour être complet:

calculer PI dans Piet

Il a la propriété plutôt agréable que la précision peut être améliorée rendant le programme plus.

Ici « est un aperçu de la langue elle - même

Créé 12/01/2009 à 19:46
source utilisateur

voix
19

C'est une méthode « classique », très facile à mettre en œuvre. Cette mise en œuvre, en python (pas si vite la langue) il le fait:

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)

Vous trouverez plus d' informations ici .

Quoi qu'il en soit le meilleur moyen d'obtenir un précis-much-as-you-want valeur de pi en python est:

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

voici le morceau de source pour la méthode gmpy pi, je ne pense pas que le code est autant utile que le commentaire dans ce cas:

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: J'ai eu un problème avec couper et coller et indentation, de toute façon vous pouvez trouver la source ici .

Créé 02/10/2008 à 22:27
source utilisateur

voix
17

Si par le plus rapide que vous voulez dire le plus rapide de taper le code, voici la golfscript solution:

;''6666,-2%{2+.2/@*\/10.3??2*+}*`1000<~\;
Créé 06/08/2008 à 23:54
source utilisateur

voix
15

Utiliser la formule 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.

Mis en œuvre dans le schéma, par exemple:

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

Créé 05/02/2011 à 06:26
source utilisateur

voix
15

Avec double:

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

Ce sera précis jusqu'à 14 décimales, assez pour remplir un double (l'inexactitude est probablement parce que le reste des décimales dans les tangentes d'arc sont tronqués).

Aussi Seth, il est 3,14159265358979323846 3 , pas 64.

Créé 28/02/2010 à 04:52
source utilisateur

voix
15

Si vous êtes prêt à utiliser une approximation, 355 / 113est bon pour 6 chiffres décimaux, et a l'avantage d'être utilisable avec des expressions entières. Ce n'est pas aussi important ces jours -ci , comme « flottant co-processeur mathématique point » a cessé d'avoir un sens, mais il était très important une fois.

Créé 17/09/2009 à 17:30
source utilisateur

voix
15

Pi est exactement 3! [Prof. Frink (Simpsons)]

Blague, mais voici un en C # (.NET Framework requis).

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;
        }
    }
}
Créé 26/02/2009 à 20:22
source utilisateur

voix
15

Calculer PI à la compilation avec D.

(Recopie de 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))) );
Créé 17/09/2008 à 18:49
source utilisateur

voix
13

Cette version (en Delphi) est rien de spécial, mais il est au moins plus rapide que la version Nick Hodge a posté sur son blog :). Sur ma machine, il faut environ 16 secondes pour faire un milliard d' itérations, ce qui donne une valeur de 3,14159265 25879 (la partie précise est en gras).

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.
Créé 12/01/2009 à 19:24
source utilisateur

voix
12

Si vous voulez calculer une approximation de la valeur de π (pour une raison quelconque), vous devriez essayer un algorithme d'extraction binaire. De Bellard l'amélioration de BBP donne PI fait en O (N ^ 2).


Si vous voulez obtenir une approximation de la valeur de π pour effectuer des calculs, alors:

PI = 3.141592654

Certes, c'est seulement une approximation, et pas tout à fait exact. Il est hors d'un peu plus de ,00000000004102. (quatre-dix milliardièmes, environ 4 / 10000000000 ).


Si vous voulez faire des mathématiques avec π, alors vous procurer un crayon et du papier ou un paquet d'algèbre informatique et utiliser la valeur exacte de π, π.

Si vous voulez vraiment une formule, celle-ci est amusant:

π = - i ln (-1)

Créé 22/12/2009 à 22:13
source utilisateur

voix
12

De retour dans les vieux jours, avec de petites tailles de mots et d'opérations à virgule flottante lentes ou inexistantes, nous avons utilisé pour faire des choses comme ceci:

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

Pour les applications qui ne nécessitent pas beaucoup de précision (jeux vidéo, par exemple), ce qui est très rapide et est assez précis.

Créé 20/02/2009 à 22:21
source utilisateur

voix
11

La méthode de Brent a affiché ci-dessus par Chris est très bon; Brent est généralement un géant dans le domaine de l'arithmétique à précision arbitraire.

Si tout ce que vous voulez est le chiffre Nième, la célèbre formule BBP est utile dans l' hexagone

Créé 04/08/2009 à 22:39
source utilisateur

voix
1

Calcul de π de la zone de cercle :-)

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

Créé 03/06/2017 à 17:13
source utilisateur

voix
0

Une meilleure approche

Pour obtenir la sortie des constantes standard comme pi ou les concepts, il faut d' abord aller avec les méthodes disponibles builtins la langue que vous utilisez. Il retourne la valeur de la façon la plus rapide et la meilleure manière aussi. J'utilise python pour obtenir le meilleur moyen pour obtenir la valeur pi

  • variable pi de la bibliothèque de mathématiques . Bibliothèque mathématique stocker la pi variable constante.

math_pi.py

import math
print math.pi

Exécutez le script avec le temps utilitaire de linux /usr/bin/time -v python math_pi.py

Sortie:

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
  • Utilisez arc cos méthode de calcul

acos_pi.py

import math
print math.acos(-1)

Exécutez le script avec le temps utilitaire de linux /usr/bin/time -v python acos_pi.py

Sortie:

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

Exécutez le script avec le temps utilitaire de linux /usr/bin/time -v python bbp_pi.py

Sortie:

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

Donc, la meilleure façon est d'utiliser builtins méthode fournie par la cause de la langue qu'ils sont les plus rapides et mieux pour obtenir la sortie. En utilisation python Math.PI.

Créé 18/06/2018 à 10:07
source utilisateur

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