13,198,325 members (60,187 online)
alternative version

Stats

232K views
37 bookmarked
Posted 19 Sep 2005

Calculate pi to one million decimal places

, 19 Sep 2005
 Rate this:
A simple program that should take a few hours to run.

Introduction

Pi is one of the most important numbers in mathematics. It is defined as the ratio of a circle's circumference to its diameter, but it crops up in all sorts of places in mathematics. It is an infinitely long non-recurring decimal number.

I'm not going to try to write pi as the Greek letter in this article, because some browsers might show it incorrectly.

Calculating lots of digits of pi

There are many ways to do this. Some methods converge rapidly but are complicated to implement. Some are simple to implement but converge very slowly. I've chosen a method that is fairly simple and converges reasonably fast. It is based on the following formula:

pi / 4 = 4 * tan-1(1 / 5) - tan-1(1 / 239)

This is Machin's formula and is exact.

tan-1() is the <A target=_blank InverseTangent.html? mathworld.wolfram.com ?http:>Inverse Tangent function, and I use the Maclaurin series to calculate it:

tan-1(z) = z - z3 / 3 + z5 / 5 - z7 / 7 + ...

By including sufficiently many terms of this series, we can achieve any desired accuracy. To get 1,000,000 decimal places accuracy for pi, we need about 715,000 terms of the tan-1(1/5) series and about 210,000 terms of the tan-1(1/239) series, but this doesn't have to be worked out in advance, the attached program stops automatically when it determines that the required accuracy has been reached.

Multi-length arithmetic

A 32-bit integer only gives us about 9 significant digits. To get one million decimal places, I've done a simple implementation of the multi-length arithmetic operations that I need, using a big array of `int`s. The multi-length numbers are wrapped up inside the class `CRHMultiLengthInteger`. I've made full use of the operator notation in C++ to make the code look like we're just working with ordinary numbers. For example:

`term5m /= n5 * 2 + 1;`

looks like it's just dividing `term5m` by a number, but it's actually calling `CRHMultiLengthInteger::operator /=()`.

The program

The attached program is a straightforward Win32 Console Application (it started out as the standard "Hello, World!" application with MFC support). You can adjust how many decimal places it calculates by changing `#define NDecimalPlaces (1000100)` to some other number. The answer is written to a file called resultNDecimalPlaces.txt.

Points of Interest

• The algorithm described above has an O(n2) duration. So 10 times as many decimal places will take about 100 times as long. My 7,000 MIPs PC took about 15 hours to calculate the first 1,000,000 decimal places of pi. That works out at about 380 million million instructions in total.
• To get 1,000,000 decimal places, each multi-length number is implemented as an array of 166685 integers, using a base of 1,000,000 so that each integer gives us 6 significant digits. This actually gives us 1,000,104 decimal places, but the last few might be incorrect because of the infinite number of terms of the Maclaurin series that we have to throw away. Comparison with this shows that the last three decimal places are wrong, so we have actually got pi correct to 1,000,101 decimal places.
• The first 1,000,000 decimal places of pi were first calculated in 1973.
• The 19th century English mathematician William Shanks spent over 15 years calculating the first 707 places of pi using Machin's formula. He published his results in 1873. In 1944 it was found that he had made a mistake in the 528th place, and all the following digits were wrong. By changing to `#define NDecimalPlaces (1000)`, you can now achieve in a fraction of a second more than William Shanks failed to achieve in 15 years.

Why?

Getting a computer to calculate lots of digits of pi does have its uses, it can be used to show that the computer, or at least its ALU, is working properly.

Acknowledgments

Thanks very much to:

History

• 6th September 2005 - first submitted.

A list of licenses authors might use can be found here

Share

 Software Developer (Senior) United Kingdom
I've been programming computers since about 1968. I started at school with Algol 60 on an Elliott 803. From there I progressed through the Z80 and other microprocessors to the PC, DOS and Windows, Pascal, C and C++.

My other interests include astronomy and classical music. All of my contributions to Code Project have arisen from programs I've written in these areas.

You may also be interested in...

 Pro Pro

 First Prev Next
 Pi Pictures. Eduardo N Hering29-Aug-11 14:45 Eduardo N Hering 29-Aug-11 14:45
 Article for review ssnirgudkar21-Dec-09 15:15 ssnirgudkar 21-Dec-09 15:15
 Re: Article for review ssnirgudkar21-Dec-09 15:17 ssnirgudkar 21-Dec-09 15:17
 Enough with the term "million million"! prom 197616-May-08 0:03 prom 1976 16-May-08 0:03
 Re: Enough with the term "million million"! Chris Hills17-May-08 3:39 Chris Hills 17-May-08 3:39
 Re: Enough with the term "million million"! canozurdo25-Jun-08 8:37 canozurdo 25-Jun-08 8:37
 Radians or Degrees? Thmath17763-May-08 10:06 Thmath1776 3-May-08 10:06
 Re: Optimization to the death Brian Wiegand9-Feb-09 18:12 Brian Wiegand 9-Feb-09 18:12
 Re: Optimization to the death hashme334-Nov-09 9:21 hashme33 4-Nov-09 9:21
 Hello! How did you get it to become multithreaded? Did you just parallel multiprecision arithmetic operations? Or there is a better scheme? Thanks.
 Why is this important? curiousone11-Jun-07 9:31 curiousone 11-Jun-07 9:31
 Re: Why is this important? lancere25-Aug-07 14:12 lancere 25-Aug-07 14:12
 Re: Why is this important? Crusiatus Black3-Nov-08 2:24 Crusiatus Black 3-Nov-08 2:24
 Re: Why is this important? ron real30-Jul-10 12:30 ron real 30-Jul-10 12:30
 Multilength arit. diegusaldus2-Apr-07 23:05 diegusaldus 2-Apr-07 23:05
 Re: Multilength arit. Chris Hills8-Apr-07 10:04 Chris Hills 8-Apr-07 10:04
 It's not Exact Zmurf7-May-06 23:55 Zmurf 7-May-06 23:55
 Re: It's not Exact Super Lloyd24-May-06 19:40 Super Lloyd 24-May-06 19:40
 Re: It's not Exact Zmurf25-May-06 2:24 Zmurf 25-May-06 2:24
 Re: It's not Exact Super Lloyd25-May-06 2:54 Super Lloyd 25-May-06 2:54
 Bailey-Borwein-Plouffe formula (this is amazing) Don Clugston16-Oct-05 23:28 Don Clugston 16-Oct-05 23:28
 simple optimizations cub4bear28-Sep-05 5:32 cub4bear 28-Sep-05 5:32
 Another optimization ? Mr. Fox30-Sep-05 6:19 Mr. Fox 30-Sep-05 6:19
 Re: Another optimization ? cub4bear30-Sep-05 8:31 cub4bear 30-Sep-05 8:31
 my results manuelpg26-Sep-05 21:41 manuelpg 26-Sep-05 21:41
 How long did it take? WREY19-Sep-05 11:49 WREY 19-Sep-05 11:49
 Re: How long did it take? Chris Maunder19-Sep-05 12:05 Chris Maunder 19-Sep-05 12:05
 Re: How long did it take? WREY19-Sep-05 12:14 WREY 19-Sep-05 12:14
 Re: How long did it take? Chris Hills21-Sep-05 11:56 Chris Hills 21-Sep-05 11:56
 Re: How long did it take? Joe Pizzi28-Sep-05 12:01 Joe Pizzi 28-Sep-05 12:01
 Re: How long did it take? WREY28-Sep-05 14:03 WREY 28-Sep-05 14:03
 Re: How long did it take? Joe Pizzi28-Sep-05 16:25 Joe Pizzi 28-Sep-05 16:25
 Re: How long did it take? WREY28-Sep-05 19:17 WREY 28-Sep-05 19:17
 Re: How long did it take? f230-Sep-05 5:10 f2 30-Sep-05 5:10
 Re: How long did it take? lusheebabe23-Oct-08 20:06 lusheebabe 23-Oct-08 20:06