What is the fastest means to get the value of π?

I'm seeking the fastest means to get the value of π, as an individual obstacle. Extra especially, I'm making use of manner ins which do not entail making use of #define constants like M_PI, or hard-coding the number in.

The program listed below examinations the numerous means I recognize of. The inline setting up variation is, theoretically, the fastest alternative, though plainly not mobile. I've included it as a standard to contrast versus the various other variations. In my examinations, with built-ins, the 4 * atan(1) variation is fastest on GCC 4.2, due to the fact that it auto-folds the atan(1) right into a constant. With -fno-builtin defined, the atan2(0, -1) variation is fastest.

Below's the major screening program (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 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();

    /* Actual tests start here. */
    TESTWITH(atan2(0, -1))
    TESTWITH(2 * asin(1))
    TESTWITH(4 * atan2(1, 1))
    TESTWITH(4 * atan(1))

    return 0;

And also the inline setting up things (fldpi.c) that will just benefit x86 and also x64 systems:

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

And also a construct manuscript that constructs all the arrangements I'm examining (build.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

In addition to screening in between numerous compiler flags (I've contrasted 32-bit versus 64-bit also, due to the fact that the optimizations are various), I've additionally attempted switching over the order of the examinations around. Yet still, the atan2(0, -1) variation still prevails every single time.

2019-05-06 23:38:38
Source Share
Answers: 3

If by fastest you suggest fastest to key in the code, below is the golfscript remedy:

2019-05-16 23:59:43

The Monte Carlo method, as stated, uses some wonderful principles yet it is, plainly, not the fastest, not by a slim chance, not by any kind of practical action. Additionally, all of it relies on what sort of precision you are seeking. The fastest π I recognize of is the one with the figures tough coded. Considering Pi and also Pi[PDF], there are a great deal of solutions.

Below is a method that merges promptly-- concerning 14 figures per model. PiFast, the existing fastest application, utilizes this formula with the FFT. I'll simply write the formula, given that the code is uncomplicated. This formula was virtually located by Ramanujan and discovered by Chudnovsky. It is in fact just how he computed numerous billion figures of the number-- so it isn't a method to negligence. The formula will certainly overflow promptly and also, given that we are separating factorials, it would certainly be useful after that to postpone such estimations to remove terms.


Below is the Brent–Salamin algorithm. Wikipedia states that when a and also b are "close adequate" after that (a+b) ²/ 4t will certainly be an estimate of π. I'm not exactly sure what "close sufficient" suggests, yet from my examinations, one model obtained 2 figures, 2 obtained 7, and also 3 had 15, certainly this is with increases, so it could have a mistake based upon its depiction and also the real estimation can be extra exact.

let pi_2 iters =
    let rec loop_ a b t p i =
        if i = 0 then a,b,t,p
            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)
    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)

Lastly, just how concerning some pi golf (800 figures)? 160 personalities!

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);}
2019-05-09 08:06:17

Here's a basic summary of a strategy for computing pi that I found out in senior high school.

I just share this due to the fact that I assume it is straightforward sufficient that any person can remember it, forever, plus it educates you the principle of "Monte - Carlo" approaches - - which are analytical approaches of getting to solutions that do not quickly seem deducible via arbitrary procedures.

Attract a square, and also etch a quadrant (one quarter of a semi - circle) inside that square (a quadrant with distance equivalent to the side of the square, so it loads as much of the square as feasible)

Now toss a dart at the square, and also document where it lands - - that is, pick an arbitrary factor anywhere inside the square. Certainly, it landed inside the square, yet is it inside the semi - circle? Videotape this reality.

Repeat this process sometimes - - and also you will certainly locate there is a proportion of the variety of factors inside the semi - circle versus the complete number tossed, call this proportion x.

Given that the location of the square is r times r, you can reason that the location of the semi circle is x times r times r (that is, x times r made even). Therefore x times 4 will certainly offer you pi.

This is not a fast method to make use of. Yet it's a wonderful instance of a Monte Carlo method. And also if you check out, you might locate that several troubles or else outside your computational abilities can be addressed by such approaches.

2019-05-08 20:29:27