I'm looking for the fastest way to obtain the value of π, as a personal challenge. More specifically, I'm using ways that don't involve using `#define`

constants like `M_PI`

, or hard-coding the number in.

The program below tests the various ways I know of. The inline assembly version is, in theory, the fastest option, though clearly not portable. I've included it as a baseline to compare against the other versions. In my tests, with built-ins, the `4 * atan(1)`

version is fastest on GCC 4.2, because it auto-folds the `atan(1)`

into a constant. With `-fno-builtin`

specified, the `atan2(0, -1)`

version is fastest.

Here's the main testing 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
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;
}
```

And the inline assembly stuff (`fldpi.c`

) that will only work for x86 and x64 systems:

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

And a build script that builds all the configurations I'm testing (`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
```

Apart from testing between various compiler flags (I've compared 32-bit against 64-bit too because the optimizations are different), I've also tried switching the order of the tests around. But still, the `atan2(0, -1)`

version still comes out on top every time.

The Monte Carlo method, as mentioned, applies some great concepts but it is, clearly, not the fastest, not by a long shot, not by any reasonable measure. Also, it all depends on what kind of accuracy you are looking for. The fastest π I know of is the one with the digits hard coded. Looking at Pi and Pi[PDF], there are a lot of formulae.

Here is a method that converges quickly — about 14 digits per iteration. PiFast, the current fastest application, uses this formula with the FFT. I'll just write the formula, since the code is straightforward. This formula was almost found by Ramanujan and discovered by Chudnovsky. It is actually how he calculated several billion digits of the number — so it isn't a method to disregard. The formula will overflow quickly and, since we are dividing factorials, it would be advantageous then to delay such calculations to remove terms.

where,

Below is the Brent–Salamin algorithm. Wikipedia mentions that when

aandbare "close enough" then(a + b)² / 4twill be an approximation of π. I'm not sure what "close enough" means, but from my tests, one iteration got 2 digits, two got 7, and three had 15, of course this is with doubles, so it might have an error based on its representation and thetruecalculation could be more accurate.Lastly, how about some pi golf (800 digits)? 160 characters!

I really like this program, because it approximates π by looking at its own area.

IOCCC 1988 : westley.c

Here's a general description of a technique for calculating pi that I learnt in high school.

I only share this because I think it is simple enough that anyone can remember it, indefinitely, plus it teaches you the concept of "Monte-Carlo" methods -- which are statistical methods of arriving at answers that don't immediately appear to be deducible through random processes.

Draw a square, and inscribe a quadrant (one quarter of a semi-circle) inside that square (a quadrant with radius equal to the side of the square, so it fills as much of the square as possible)

Now throw a dart at the square, and record where it lands -- that is, choose a random point anywhere inside the square. Of course, it landed inside the square, but is it inside the semi-circle? Record this fact.

Repeat this process many times -- and you will find there is a ratio of the number of points inside the semi-circle versus the total number thrown, call this ratio x.

Since the area of the square is r times r, you can deduce that the area of the semi circle is x times r times r (that is, x times r squared). Hence x times 4 will give you pi.

This is not a quick method to use. But it's a nice example of a Monte Carlo method. And if you look around, you may find that many problems otherwise outside your computational skills can be solved by such methods.

In the interests of completeness, a C++ template version, which, for an optimised build, will compute an approximation of PI at compile time, and will inline to a single value.

Note for I > 10, optimised builds can be slow, likewise for non-optimised runs. For 12 iterations I believe there are around 80k calls to value() (in the absence of memoisation).

There's actually a whole book dedicated (amongst other things) to

fastmethods for the computation of \pi: 'Pi and the AGM', by Jonathan and Peter Borwein (available on Amazon).I studied the AGM and related algorithms quite a bit: it's quite interesting (though sometimes non-trivial).

Note that to implement most modern algorithms to compute \pi, you will need a multiprecision arithmetic library (GMP is quite a good choice, though it's been a while since I last used it).

The time-complexity of the best algorithms is in O(M(n)log(n)), where M(n) is the time-complexity for the multiplication of two n-bit integers (M(n)=O(n log(n) log(log(n))) using FFT-based algorithms, which are usually needed when computing digits of \pi, and such an algorithm is implemented in GMP).

Note that even though the mathematics behind the algorithms might not be trivial, the algorithms themselves are usually a few lines of pseudo-code, and their implementation is usually very straightforward (if you chose not to write your own multiprecision arithmetic :-) ).

The following answers

precisely how to do this in the fastest possible way -- with the least computing effort. Even if you don't like the answer, you have to admit that it is indeed the fastest way to get the value of PI.The

FASTESTway to get the value of Pi is:1) chose your favourite programming language 2) load its Math library 3) and find that Pi is already defined there -- ready for use!

In case you don't have a Math library at hand..

The

SECOND FASTESTway (more universal solution) is:look up Pi on the Internet, e.g. here:

http://www.eveandersson.com/pi/digits/1000000 (1 million digits .. what's your floating point precision? )

or here:

http://3.141592653589793238462643383279502884197169399375105820974944592.com/

or here:

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

It's really fast to find the digits you need for whatever precision arithmetic you would like to use, and by defining a constant, you can make sure that you don't waste precious CPU time.

Not only is this a partly humorous answer, but in reality, if anybody would go ahead and compute the value of Pi in a real application .. that would be a pretty big waste of CPU time, wouldn't it? At least I don't see a real application for trying to re-compute this.

Dear Moderator: please note that the OP asked: "Fastest Way to get the value of PI"

The BBP formula allows you to compute the nth digit - in base 2 (or 16) - without having to even bother with the previous n-1 digits first :)

Instead of defining pi as a constant, I always use

`acos(-1)`

.Just came across this one that should be here for completeness:

calculate PI in Piet

It has the rather nice property that the precision can be improved making the program bigger.

Here's some insight into the language itself

If this article is true, then the algorithm that Bellard has created could be one of the speediest available. He has created pi to 2.7 TRILLION digits using a DESKTOP PC!

...and he has published his work here

Good work Bellard, You are a pioneer!

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

This is a "classic" method, very easy to implement. This implementation, in python (not so fast language) does it:

You can find more information here.

Anyway the fastest way to get a precise as-much-as-you-want value of pi in python is:

here is the piece of source for the gmpy pi method, I don't think the code is as much useful as the comment in this case:

EDIT:I had some problem with cut and paste and identation, anyway you can find the source here.If by fastest you mean fastest to type in the code, here's the golfscript solution:

Use the Machin-like formula

Implemented in Scheme, for instance:

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

If you are willing to use an approximation,

`355 / 113`

is good for 6 decimal digits, and has the added advantage of being usable with integer expressions. That's not as important these days, as "floating point math co-processor" ceased to have any meaning, but it was quite important once.With doubles:

This will be accurate up to 14 decimal places, enough to fill a double (the inaccuracy is probably because the rest of the decimals in the arc tangents are truncated).

Also Seth, it's 3.14159265358979323846

3, not 64.## Calculate PI at compile-time with D.

( Copied from DSource.org )

Pi is exactly 3! [Prof. Frink (Simpsons)]

Joke, but here's one in C# (.NET-Framework required).

This version (in Delphi) is nothing special, but it is at least faster than the version Nick Hodge posted on his blog :). On my machine, it takes about 16 seconds to do a billion iterations, giving a value of

3.1415926525879 (the accurate part is in bold).Back in the old days, with small word sizes and slow or non-existent floating-point operations, we used to do stuff like this:

For applications that don't require a lot of precision (video games, for example), this is very fast and is accurate enough.

If you want to

computean approximation of the value of π (for some reason), you should try a binary extraction algorithm. Bellard's improvement of BBP gives does PI in O(N^2).If you want to

obtainan approximation of the value of π to do calculations, then:Granted, that's only an approximation, and not entirely accurate. It's off by a little more than 0.00000000004102. (four ten-trillionths, about

^{4}/_{10,000,000,000}).If you want to do

mathwith π, then get yourself a pencil and paper or a computer algebra package, and use π's exact value, π.If you really want a formula, this one is fun:

## π = -

iln(-1)Brent's method posted above by Chris is very good; Brent generally is a giant in the field of arbitrary-precision arithmetic.

If all you want is the Nth digit, the famous BBP formula is useful in hex

Calculating π from circle area :-)

## Better Approach

To get the output of standard constants like

pior the standard concepts, we should first go with the builtins methods available the language that you are using. It will return value in the fastest way and best way also. I am using python to get the fastest way to get the value pipi variable of the math library. Math library store the variable pi as constant.math_pi.py

Run the script with time utility of linux

`/usr/bin/time -v python math_pi.py`

Output:

Use arc cos method of mathacos_pi.py

Run the script with time utility of linux

`/usr/bin/time -v python acos_pi.py`

Output:

use BBP formulabbp_pi.py

Run the script with time utility of linux

`/usr/bin/time -v python bbp_pi.py`

Output:

So best way is to use builtins method provided by the language cause they are the fastest and best to get the output. In python use math.pi