Quel est le moyen le plus rapide pour obtenir la valeur de π ?

Question

Les Solutions sont les bienvenus dans toutes les langues. :-) Je suis à la recherche de la façon la plus rapide pour obtenir la valeur de π, comme un défi personnel. Plus précisément, je suis en utilisant des moyens qui n'impliquent pas l'aide d' #defined des constantes comme M_PI, ou de coder en dur le nombre.

Le programme de tests ci-dessous les différentes façons que je connais. La ligne la version de l'assembly est, en théorie, l'option la plus rapide, bien que manifestement pas portable; je l'ai inclus comme une base de référence pour comparer les autres versions contre. Dans mes tests, avec built-ins, l' 4 * atan(1) version est plus rapide sur GCC 4.2, parce que l'auto-plis de l' atan(1) dans une constante. Avec -fno-builtin spécifié, l' atan2(0, -1) version est la plus rapide.

Voici le principal programme de tests (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 la ligne d'assemblage des trucs (fldpi.c), en notant qu'il 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 s'appuie toutes les configurations, je suis mise à l'essai (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 dehors de tests entre les différents drapeaux du compilateur (j'ai comparé 32 bits, contre 64 bits aussi, parce que les optimisations sont différents), j'ai aussi essayé en changeant l'ordre des tests autour de. L' atan2(0, -1) version vient toujours top de tous les temps.

Answer 1

La méthode de Monte Carlo, comme mentionné, s'applique à certains grands concepts, mais c'est clairement pas le plus rapide-et pas par un long shot, pas du tout raisonnable utilité. Aussi, tout dépend de ce genre de précision que vous recherchez. La manière la plus rapide pi je sais de est 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 (~14digits par itération). Le courant plus rapide de l'application, PiFast, utilise cette formule avec la FFT. Je vais juste écrire la formule, étant donné que le code est simple. Cette formule a été presque trouvé par Ramanujan et découvert par Chudnovsky. C'est en fait la façon dont il a calculé plusieurs milliards de chiffres du numéro de série --donc ce n'est pas une méthode de mépris. La formule débordera rapidement car nous sommes en divisant les factorielles, il serait avantageux alors pour retarder un tel calcul pour supprimer des termes.

où,

Ci-dessous le Brent–Salamin algorithme. Wikipédia mentionne que si a et b sont "assez proche", alors (a+b)^2/4t sera une approximation de pi. Je ne suis pas sûr de ce que 'assez près, mais de mes tests, une itération ai 2digits, deux sur 7, et trois avaient 15, bien sûr, c'est avec des doubles, donc il pourrait avoir d'erreur sur la base de sa représentation et de la 'vraie' calcul pourrait être plus précise.

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, comment parler de quelques pi de golf (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);}

Answer 2

J’aime vraiment ce programme, qui se rapproche de pi en regardant sa propre zone  :-)

IOCCC 1998 : westley.c

Answer 3

Voici une description générale de la méthode de calcul de pi que j'ai appris à l'école secondaire.

Je ne partage ce parce que je pense qu'il est assez simple pour que n'importe qui peut le retenir, indéfiniment, plus il vous enseigne le concept de "Monte-Carlo", qui sont des méthodes statistiques d'arriver à des réponses qui ne s'affiche pas immédiatement à ressort par le biais de processus aléatoires.

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

Maintenant lancer une fléchette au carré, et où il atterrit, -- c'est choisir un point au hasard n'importe où à l'intérieur de la place. Bien sûr, il a atterri à l'intérieur de la place, mais est-il à l'intérieur du demi-cercle? Enregistrer ce fait.

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

Depuis l'aire du carré est de r les temps de r, vous pouvez en déduire que l'aire du demi-cercle est x fois r fois r (x fois r au carré). Donc x fois 4 vous donnera pi.

Ce n'est pas une méthode rapide à utiliser. Mais c'est un bel exemple d'une méthode de Monte Carlo. Et si vous regardez autour, vous pouvez trouver de nombreux problèmes autrement à l'extérieur de votre calcul de compétences peut être résolu par de telles méthodes.

Answer 4

Dans un souci d’exhaustivité, une version de modèle de C++, qui, dans une version optimisée, va calculer PI au moment de la compilation et sera en ligne à une seule valeur.

Note pour I > 10, optimisé construit peut être lent, que peuvent pistes non optimisée. Je pense que pour 12 itérations il y a environ 80k appels à value() (sans memoization).

Answer 5

Il y a en fait tout un livre dédié (entre autres choses) de rapide des méthodes pour le calcul de \pi: Pi et de l'AGA, par Jonathan et Pierre Borwein (disponible sur Amazon).

J'ai étudié à l'AGA et liées à des algorithmes un peu: c'est assez intéressant (bien que parfois non-trivial).

Notez que pour mettre en œuvre le plus moderne des algorithmes pour calculer \pi, vous aurez besoin d'un multiprecision arithmétique de la bibliothèque (BPF est un très bon choix, même s'il a été un moment depuis que j'ai utilisé la dernière fois).

Le temps de la complexité du meilleur algorithme est en O(M(n)log(n)), où M(n) est le temps de la complexité de la multiplication de deux à n bits entiers (M(n)=O(n log(n) log(log(n))) en utilisant la FFT à base d'algorithmes, qui sont généralement nécessaires pour le calcul des chiffres d' \pi, et un tel algorithme est mis en œuvre dans BPF).

Notez que, même si les mathématiques derrière les algorithmes pourrait ne pas être négligeable, les algorithmes eux-mêmes sont généralement de 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 multiprecision arithmétique :-) ).