Digits of pi

The digits of π shown here can be obtained in less than a second from Mathematica on a typical current computer using N[Pi, 7000]. Historically, the number of decimal digits of π that have been computed is roughly as follows: 2000 BC (Babylonians, Egyptians): 2 digits; 200 BC (Archimedes): 5 digits; 1430 AD: 14 digits; 1610: 35 digits; 1706: 100 digits; 1844: 200 digits; 1855: 500 digits; 1949 (ENIAC computer): 2037 digits; 1961: 100,000 digits (IBM 7090); 1973: 1 million; 1983: 16 million; 1989: 1 billion; 1997: 50 billion; 1999: 206 billion. In the first 200 billion digits, the frequencies of 0 through 9 differ from 20 billion by

{30841, -85289, 136978, 69393, -78309, -82947, -118485, -32406, 291044, -130820}

An early approximation to π was

4 Sum[(-1)^^{k}/(2k+1), {k, 0, m}]

30 digits were obtained with

2 Apply[Times, 2/Rest[NestList[Sqrt[2 + #]&, 0, m]]]

An efficient way to compute π to n digits of precision is

(#[[2]]^^{2}/#[[3]])& [NestWhile[ Apply[Function[{a, b, c, d}, {(a + b)/2, Sqrt[a b], c - d (a - b)^^{2}, 2 d}], #]&, {1, 1/Sqrt[N[2, n]], 1/4, 1/4}, #[[1]]!=#[[2]]&]]

This requires about Log[2, n] steps, or a total of roughly n Log[n]^^{2} operations (see page 1134).