Click here for a pdf version of this page.
Is it possible to compute directly the nth digit of p without computing all its first n digits ? At first sight, the problem seems of the same complexity. Recently [1], a formula which permits to find directly the nth bit of p with very little memory and in quasilinear time was exhibited. In other words, the question has a positive answer in base 2.
1 Computing the nth bit of p 
In [1], David Bailey, Peter Borwein and Simon Plouffe give the following formula
 (1) 
and use that to compute the nth bit of p without computing all its first n bits. More precisely, their method permits to obtain the nth bit of p in time O(nlog^{3}n) and space O(log(n)).
For convenience, we call the kth bit of a number the kth bit of its fractional part.
We make use of the notation

The N+nth bit of a real number a is obtained by computing the nth bit of the fractional part of 2^{N}a.Proof : This property is obvious since the binary expansion of a



Thus from a sufficiently accurate value of {2^{N} a}, this result permits to know the first term of its binary expansion. We illustrate this simple idea on p. One has


We are thus lead to compute a sufficiently accurate value of the fractional part {2^{N}p} of 2^{N} p. Formula (1) entails that {2^{N}p} is the fractional part of the series




The computation of 2^{n} modulo m is obtained thanks to a binary powering method, using only O(log(n)) operations modulo m. It consists in writing n in base 2


Finally, formula (1) permits to obtain bits of p between position N+1 and N+K by computing the K first bits of the number



Other formulas of this type have been found for p. The fastest known is due to Fabrice Bellard and is approximately 43% faster than (1) to compute the nth bit of p :

2 Computing of the nth bit of other constants 
In [1], David Bailey, Peter Borwein and Simon Plouffe give similar kind of series to compute directy the nth bit of the constants log(2), p^{2} and log^{2}(2). Later [2], D. J. Broadhurst found other similar series for a wider class of constants, like z(3), z(5), the Catalan constant C, p^{3}, p^{4}, log^{3}(2), log^{4}(2), log^{5}(2). More recently, Gery Huvent [4] found other formula of this kind.
Here are a sample of those formulas :



As for the Catalan constant G = å_{k ³ 0} (1)^{k}/(2k+1)^{2}, we have the concise form, shown in [4]

The direct computation of the nth bit of the classical constants e, Ö2 and g with a similar complexity remains an open problem.
3 Computing the nth decimal digit 
Unhappily, no formula of the same kind to compute decimal digits of p have been found yet (or more generally, in any base that is not a power of two). In other words, no series of the form

The first progress in this direction is due to Simon Plouffe in 1997, who found an algorithm with time O(n^{3} log^{3}n) and very little memory to compute the nth digit of p (see the Plouffe page for a description of the method). Unhappily, the complexity is so high that his technique does not reasonably permit to reach decimal digits at position n higher than several thousands.
The Simon Plouffe method has been improved by Fabrice Bellard with a O(n^{2}) algorithm (complexity in terms of elementary operations on numbers of size O(logn)). The Fabrice Bellard page describes the corresponding algorithm, and a C program is also available. The millionth decimal digit can be reached with that technique. Nethertheless, even using parallelization, the complexity remains too high to give a practical alternative to techniques in quasilinear time which computes all the decimal digits.
Recently, Xavier Gourdon found a better algorithm for the nth decimal digit computation of p, that runs in time O(n^{2}loglogn/log^{2} n) in terms of elementary operations. The improvement is nearly a factor log^{2} n compared to Fabrice Bellard algorithm. The corresponding algorithm is described in an unpublished paper [3] that can be dowloaded here in pdf format.
Timings comparisons have been made between this program and the program of Fabrice Bellard.
Index of  pidec time  F. Bellard 
decimal digit  program time  
5,000  0.96 sec  4.85 sec 
10,000  3.13 sec  18.10 sec 
20,000  10.34 sec  68.29 sec 
40,000  35.96 sec  259.8 sec 
100,000  185.1 sec  1520 sec 
200,000  628.7 sec  5703 sec 
500,000  3525 sec  34730 sec 
1,000,000  15869 sec  not ran 
2,000,000  42316 sec  not ran 
4,000,000  168191 sec  not ran 
 (2) 


The problem is thus essentially reduced to computing powers and sum of binomial coefficients modulo small numbers. Details are fulfilled in [3].
On the one hand, we have an algorithm to compute directly the nth decimal digit of p in nearly quadratic time and using very little memory; on the other hand, computing all the first n digits of p is possible in quasilinear time and with memory O(n). It is natural to ask if it were possible to find intermediate algorithms, that use a limited amount of memory O(m) (for example memory O(Ön)) and obtain an intermediate cost between linear and quadratic. In fact, the question has a positive answer by the use of formula () together with the socalled binary splitting technique on numbers of size O(m). More precisely, it is possible to obtain an algorithm which uses O(m) memory with running time

Details of this algorithm will added soon in [3].
Colin Percival PiHex project : this project currently holds the world record for the bit computation of p with the forty trillionth bit (10 trillionth hexit) of pi using Bellard's formula.
Fabrice Bellard page on the nth digit computation of p.
Simon Plouffe page on the nth decimal digit computation of p.
numbers, constants and computation