Contents






1. The State Of Pi Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .               1

2. How Random Is  ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
     2.1 Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
     2.2 Is Pi normal? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
     2.3 So is Pi not normal? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
     2.4 The 163 phenomenon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
     2.5 Other statistical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
     2.6 The Intuitionists and   . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
     2.7Representation of continued fractions . . . . . . . . . . . . . . . . 32

3. Shortcuts To   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
     3.1 Obscurer approaches to   . . . . . . . . . . . . . . . . . . . . . . . . . . 35
     3.2 Small is beautiful . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
     3.3 Squeezing Pi through a sieve . . . . . . . . . . . . . . . . . . . . . . . . 38
     3.4 Pi and chance (Monte Carlo methods) . . . . . . . . . . . . . . . . 39
     3.5 Memorabilia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
     3.6 Bit for bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
     3.7Refinements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
     3.8 The Pi room in Paris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4. Approximations For Pi And Continued Fractions . . . . 51
     4.1 Rational approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
     4.2 Other approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
     4.3 Youthful approximations . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
     4.4 On continued fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5. Arcus Tangens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
     5.1 John Machin's arctan formula . . . . . . . . . . . . . . . . . . . . . . 69
     5.2 Other arctan formulae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2



X        Contents

6. Spigot Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
      6.1 The spigot algorithm in detail . . . . . . . . . . . . . . . . . . . . . . 7 8
      6.2 Sequence of operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
      6.3 A faster variant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
      6.4 Spigot algorithm for e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

7. Gauss And   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
      7.1 The Pi AGM formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
      7.2 The Gauss AGM algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 90
      7.3 Sch¨onhage variant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
      7.4 History of a formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

8. Ramanujan And   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
      8.1 Ramanujan's series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
      8.2 Ramanujan's unusual biography . . . . . . . . . . . . . . . . . . . . . 105
      8.3 Impulses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

9. The Borweins And   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

10. The BBP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
      10.1 Binary modulo exponentiation . . . . . . . . . . . . . . . . . . . . . . 120
      10.2 A C program on the BBP series . . . . . . . . . . . . . . . . . . . . . 123
      10.3 Refinements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

11. Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
      11.1 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
      11.2 Karatsuba multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
      11.3 FFT multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
      11.4 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
      11.5 Square root. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
      11.6 nth root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
      11.7Series calculation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

12. Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
      12.1 A Pi quiz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
      12.2 Let numbers speak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
      12.3 A proof that   = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
      12.4 The big change . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
      12.5 Almost but not quite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
      12.6 Why always more? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158



                                                                                    Contents          XI

      12.7 Pi and hyperspheres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
      12.8 Vi ete × Wallis = Osler . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
      12.9 Squaring the circle with holes . . . . . . . . . . . . . . . . . . . . . . . 162
      12.10An (in)finite funnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

13. The History Of   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
      13.1 Antiquity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
      13.2 Polygons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 0
      13.3 Infinite expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
      13.4 High-performance algorithms . . . . . . . . . . . . . . . . . . . . . . . 198
      13.5 The hunt for single Pi digits . . . . . . . . . . . . . . . . . . . . . . . . . 203
      Table: History of Pi in the pre-computer era . . . . . . . . . . . . . . . 205
      Table: History of Pi in the computer era . . . . . . . . . . . . . . . . . . 206
      Table: History of digit extraction records . . . . . . . . . . . . . . . . . 207

14. Historical Notes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
      14.1 The earliest squaring the circle in history? . . . . . . . . . . . . 209
      14.2 A Pi law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
      14.3 The Bieberbach story . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

15. The Future: Pi Calculations On The Internet . . . . . . . . 215
      15.1 The binsplit algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
      15.2 The Pi project on the Internet . . . . . . . . . . . . . . . . . . . . . . . 219

16.   Formula Collection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

17. Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
      17.1 Selected constants to 100 places (base 10) . . . . . . . . . . . . 239
      17.2 Digits 0 to 2, 500 of Pi (base 10) . . . . . . . . . . . . . . . . . . . . . 240
      17.3 Digits 2,501 to 5,000 of Pi (base 10) . . . . . . . . . . . . . . . . . . 241
      17.4 Digits 0 to 2,500 of Pi (base 16) . . . . . . . . . . . . . . . . . . . . . 242
      17.5 Digits 2,501 to 5,000 of Pi (base 16) . . . . . . . . . . . . . . . . . . 243
      17.6 Continued fraction elements 0 to 1,000 of Pi . . . . . . . . . . . 244
      17.7 Continued fraction elements 1,001 to 2,000 of Pi . . . . . . . 245

A. Documentation For The hfloat Library . . . . . . . . . . . . . . . 247
      A.1 What hfloat is (good for) . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
      A.2 Compiling the library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
      A.3 Functions of the hfloat library . . . . . . . . . . . . . . . . . . . . . . . 248
      A.4 Using hfloats in your own code . . . . . . . . . . . . . . . . . . . . . . 250



XII       Contents

       A.5 Computations with extreme precision . . . . . . . . . . . . . . . . 250
       A.6 Precision and radix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
       A.7 Compiling & running the Pi-example-code . . . . . . . . . . . . 253
       A.8 Structure of hfloat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
       A.9 Organisation of the files . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
       A.10 Distribution policy & no warranty . . . . . . . . . . . . . . . . . . 255

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265