Click here to Skip to main content
Email Password   helpLost your password?

pi

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 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 ints. 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

Why?

This article is just for fun. I know it's pretty straightforward but I thought people might be interested in seeing it.

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

You must Sign In to use this message board.
 
 
Per page   
 FirstPrevNext
GeneralArticle for review
ssnirgudkar
16:15 21 Dec '09  
Hello Chris,

This is Shailesh. Recently I came across your 'pi' article as I was also interested in the same problem. I did go through your code and faq and implemented my own code. It is very, very similar to yours ( I am not ashamed ). I also wrote one article related to the subject. Would you like to review the article and give your comments ? Only if you permit me, I plan to post the article and the code on opensource.
Please let me know.

regards,
shailesh nirgudkar
GeneralRe: Article for review
ssnirgudkar
16:17 21 Dec '09  
Please let me know your email so that I can send the article.
-shailesh
GeneralEnough with the term "million million"!
prom 1976
1:03 16 May '08  
The term "a million million" is easily quantified by a 2nd-grader as a "trillion"...For christ's sake, we don't say, "a thousand thousand" to describe "a million", unless I am 14 centuries ahead of my time and I didn't know it...

Let me quantify numerics by name:

Number of zeros/U.S. & scientific community
3/thousand
6/million
9/billion
12/trillion
15/quadrillion
18/quintillion
21/sextillion
24/septillion
27/octillion
30/nonillion
33/decillion
36/undecillion
39/duodecillion
42/tredecillion
45/quattuordecillion
48/quindecillion
51/sexdecillion
54/septendecillion
57/octodecillion
60/novemdecillion
63/vigintillion
66/undecillion
303/centillion
etc...

Those who even speak "million million" are simply retarded and do not know how to quantify numbers higher than a million...The same applies for those who say "billion billion", who cannot quantify a quintillion. To salvage any intelligence, at least describe it to the tenth power, instead of thinking that saying the same word twice somehow multiplies it's meaning.

This is what lack of funding does to american education (now a contradiction in terms).
GeneralRe: Enough with the term "million million"!
Chris Hills
4:39 17 May '08  
Wow! I must have really annoyed you by what I wrote. But you're making some assumptions:
  • That I am from the USA.
  • That all the people who read CodeProject are from the USA or the scientific community.

Both assumptions are incorrect. I was concerned that if I wrote "billion" or "trillion" then some readers might be unsure as to whether I was using British or American nomenclature. http://en.wikipedia.org/wiki/Billion[^] says that "Billion may refer to ... one thousand million [or] one million million". So I wrote "million million" to be unambiguous.

Your implication that saying the same word twice does not multiply "it's meaning" is incorrect (and you mean "its meaning", BTW). "Ten million" is well understood, so are "hundred million" and "thousand million", so "million million" is perfectly acceptable.

It is generally considered impolite to impugn the intelligence of people simply because one disagrees with them. I'm sure that this indiscretion was simply because you are new to CodeProject.


GeneralRe: Enough with the term "million million"!
canozurdo
9:37 25 Jun '08  
I agree; in spanish, a billion means "One million of millions" but in english it means different, however, thanks for the advice for writing big numbers.

Bye

GeneralRadians or Degrees?
Thmath1776
11:06 3 May '08  
I am pretty sure it is in Radians, but you may want to say so because the answer comes out to be 45 in degrees. Smile
NewsOptimization to the death
pouyaebad
2:01 9 Mar '08  
I was surfing the 'code project' site, while I see your article about calculating PI number. I liked it so much and since my hobby is optimization I tried to write a C code to calculate it by implementing the algorithm you mentioned.
Although my program is a small one (about 350 SLOC in C) but it took me a week to write it.

My optimizations in the code include:
1- Coding the division function in assembly to get the quotient and remainder with just an instruction.
2- Converting the entire numbers to Hex base in the beginning and doing the whole calculation in Hex (which is much faster), in the end I converted result to Decimal base again.
3- Manipulating process and thread properties a bit to eat the whole CPU power.


By these tricks, I got the following result for calculating PI to the 100,000th digit:
(All ran on P4 2.6 GHz)

1- Original program written by Chris : 239 seconds
2- Optimized program by Todd : 84 seconds (see notes below)
3- My Optimized program : 52 seconds
4- My Optimized program (multi threaded): 36 seconds
5- My Optimized program (multi threaded): 24 seconds

*note: the last experiment ran on a quad core Intel CPU (3GHz) to get the advantages of multi threading feature.

Total calculation time to the 1,000,000th digit is less than 52 minutes on quad core Intel processor.

I am sure with a few changes to this code; it can run faster on 64 bit CPUs (I used 64 bit integers in my calculations)
I am also interested if there could be any further optimizations to algorithms or implementation techniques which make this program run even faster.

BTW, thank you for your state of the art article.

Pouya
GeneralRe: Optimization to the death
pouyaebad
2:09 12 Mar '08  
This is me again. Something surprising happened, I incresed threads number from 3 to 4 and surpisengly I found that even on my P4 machine, performance of the program increased by %14. It is very strange to me. because even by hyperthreading technology, my CPU acts as 2 processors, so there shouldn't be any differences between 3 and 4 threads (each thread is running by the highest priority) but my experiance shows that there is a performance boost ??? why?

Pouya
GeneralRe: Optimization to the death
Brian Wiegand
19:12 9 Feb '09  
wow that's amazing...

too bad the new Intel i7 can do a 32 million in 6 minutes and 40,369 seconds!!!

it's amazing here's the link.

New Super Pi 32M world record with Core i7
GeneralRe: Optimization to the death
hashme33
10:21 4 Nov '09  
Hello! How did you get it to become multithreaded? Did you just parallel multiprecision arithmetic operations? Or there is a better scheme? Thanks.
QuestionWhy is this important?
curiousone
10:31 11 Jun '07  
Will solving it to a billion or trillion decimals help with anything? Will it solve some all-consuming problem?
AnswerRe: Why is this important?
lancere
15:12 25 Aug '07  
<1> pseudo random number generators
<2> predictable encryption schemes
<3> transmission error correction
<4> system/cpu performance testing
<5> geek and programmers toys
and if you have to ask, you don't belong here Wink
AnswerRe: Why is this important?
Crusiatus Black
3:24 3 Nov '08  
It will help us understand the power of math Wink besides, pi helps us calculate important stuff.

* Life would be so much easier if we just had the sourcecode *

QuestionMultilength arit.
diegusaldus
0:05 3 Apr '07  
Hello I'm very interested in some explanation regarding the multilength aritm and what is the flow that led you to this slender piece of code. I'm studying the topic for get rid of floating point numbers as i'm developing a voice rec in a symbiam env.
would you be so kind to address me on the trajectory of your pi calculation.
I'm very fond of mfc and I'have just finished some piece of work.
thanks in advance.
my email is diegoburlando@hotmail.com.

Diego from Italy

Hello!

AnswerRe: Multilength arit.
Chris Hills
11:04 8 Apr '07  
To write some code to do multilength arithmetic you just have to think about how you were taught addition, subtraction, multiplication and division at primary school. So to add two numbers you start at the right, add the units digits, write down the units digit in the answer, take any carry over into the tens column, etc. With a 32-bit OS you don't have to limit yourself to using base 10, you could use base 2**32 = 4294967296. The only problem then is converting your input data from base 10 to base 4294967296, and converting the answers from base 4294967296 back to base 10 if you need to. I compromised and used base 1000000.

You say you're "developing a voice rec in a symbiam env" - are you sure that double length floating point arithmetic isn't good enough?
GeneralIt's not Exact
Zmurf
0:55 8 May '06  
This is not exact because sine cosine an tangeant functions are not exact. They are calculated using series which must run for an infinite peried of time to generate an exact answer. Thus PI is not exect. However, the decimals displayed are axact for a finite number of decimal places until the lack of accuracy on the series kicks in.

Mark Schad
GeneralRe: It's not Exact
Super Lloyd
20:40 24 May '06  
I think you haven't read the article.

Or if you have there is something you don't understand, for exemple: of course it's not exact: no computer could ever give the exact value of PI (except in symbolic form) but the approximation could be as good as desired by taking some time to compute enough series member....
GeneralRe: It's not Exact
Zmurf
3:24 25 May '06  
No matter how long you compute PI using this method, even if you were to do it for an infinite period of time, your answer would not be exact. Graphing the result of each iteration of this method to find PI where the SUM of the iteration was graphed on the y-axis and the iteration number was graphed on the x-axis, you would find there would be a neat little assimtope along PI paralell to y = 0.
GeneralRe: It's not Exact
Super Lloyd
3:54 25 May '06  
Are you a kind of Troll?
Why do you contradict yourself and take it as a proof you are right?

Let me be sure I'm understanding you correctly, I will repeat what I understood you saying:
"The result will never be PI, if you graph the will find it follow a curve which tends asymptotically toward PI"?
Is it what you said?

One of us is very confused here ...

There is one more thing which puzzle me greatly, what do you means by: "No matter how long you compute PI using this method, even if you were to do it for an infinite period of time, your answer would not be exact"
While it is completely wrong, do you know of any method which compute "exact the decimal value" of pi in a finite amount of time?
(if you do: patent it, you will be the greates Mathematician of the 10 next milleniums!)

Because there many methods which compute the decimal value of PI, this is one them, and they all take an infinite amount of time....
The key is: name your error, that gives you the number of iteration.... (the smaller, the more iteration...)

GeneralBailey-Borwein-Plouffe formula (this is amazing)
Don Clugston
0:28 17 Oct '05  


infinity 1 { 4 2 1 1 }
PI = SUM --- { ---- - ---- - ---- - ------ }
n=0 16^n { 8n+1 8n-4 8n+5 8n + 6 }

This amazing formula, discovered in 1995, allows you to calculate (say) the millionth digit of PI without calculating the intermediate ones first.
Only works for hexadecimal. Another consequence is that it allows you to calculate PI without multi-precision arithmetic (although you still need multi-precision if you want results in decimal!)

You should definitely mention it in your 'points of interest'.

For more info, see
http://www.sciencenews.org/pages/sn_arc98/2_28_98/mathland.htm
or look at the original papers:
http://www.cecm.sfu.ca/personal/pborwein/PISTUFF/Apistuff.html

Enjoy!


Generalsimple optimizations
cub4bear
6:32 28 Sep '05  
I liked your PI program so much that I added a few simple optimizations to reduce the compute time by about a factor of 4.

1) Use 9 digits rather than 6 for each int (reduces the total number of operations).

2) Keep track of first non-zero int in each MultiLengthInteger, so as the dividends get smaller and smaller, we aren't traversing a bunch of zeros for the divide, add, subtract, and assign operations.

3) Use one divide and two multiplies (rather than one divide, one modulo, and one multiply) in the divide routine (since divide is more expensive than multiply).

4) Added function .iszero rather than compare against a MultiLengthInteger that has a value of zero.

5) Preallocate the CString when building the final result.


My total time for 100000 digits went from 239 seconds originally down to 83.

The time for a 1-million digit run was 8575 seconds (2 hours, 22 minutes, 55 seconds) -- I didn't do a non-optimized run here, but in theory that would have been about 9 hours 28 minutes.

2.4Mhz Pentium


Cool stuff!!
-Todd
GeneralAnother optimization ?
Mr. Fox
7:19 30 Sep '05  
Perhaps you get better results if you use the following formula:
pi / 4 = 44 * arctan(1 / 57) + 7 * arctan(1 / 239) - 12 * arctan(1 / 682) + 24 * arctan(1 / 12943)
GeneralRe: Another optimization ?
cub4bear
9:31 30 Sep '05  
I tried the 4 series, as you suggested, and it was actually slower. Even though the 4 terms probably each converge more quickly than the two terms [4*arctan(1/5) - arctan(1/239)], having four terms seems to take longer.

Pi @ 100,000 digits:
2 arctan series = 84 seconds
4 arctan series = 97 seconds


Generalmy results
manuelpg
22:41 26 Sep '05  
6 hrs 40 mins on my 1GB AMD Senprom 3200+. I run on release mode and compiled with speed optimizations on. My computer is benchmarked at 7500 MIPS by SiSoft Sandra.
GeneralHow long did it take?
WREY
12:49 19 Sep '05  
How long did it take your computer to do the calculations?

It being the only application running at the time, after 15 solid minutes of running on a dual (2.5 MHz) Pentium processor with 1 Gb of memory, I killed it.

Unsure

William

Fortes in fide et opere!

-- modified at 18:05 Monday 19th September, 2005


Last Updated 19 Sep 2005 | Advertise | Privacy | Terms of Use | Copyright © CodeProject, 1999-2010