A C++ programming exercise: Calculate the first 4000 digits of PI in one second! (C++)

In these days, to me the hardest part of C++ practice is finding good and interesting programming practice problems. I learn the theoretical background of C++ programming day by day from various books, but it is not enough, I have to practice the things that I learn. Learning to program without programming is something like learning to drive without driving or learning to swim without swimming. Likely if you want to learn swim, you can’t avoid to hop into the water. And in the same way, if you want to be a good driver, you have to drive day and night.

And actually I don’t want to avoid the practice. The only problem, that the “write a simple movie Database in C++” and the similar common exercises are not very interesting after a while. Write a Matrix class, a Vector class, write a simple windowing system, write everything, what you wrote at least four or five times in the past – it is boring as hell. But once I loved the math and that’s why I find the calculation of the PI is at least a bit interesting. I made the decision that I would develop a small C++ object-oriented program that would be able to calculate the first 4000 digits of PI in one second.

I remembered that the problem was not very hard, but I didn’t make very much researches at the start of this project. Once I wrote a PI calculator in Turbo Pascal (and once I found a small and elegant Visual Basic program in the internet that calculated thousand digits of PI and wrote them into a TextBox), so I knew enough about to problem:

  1. It is easy to store the digits of long numbers in char arrays (in BCD format) and the implementation of the addition/multiplication/subtraction/division operators for char arrays is not very hard. Likely it is the easiest way to work with very long numbers.
  2. If you have the elementary operations for long numbers, you can use the Taylor series expansion of arctan(x) and the well-known Machin’s formula to calculate Pi. Of course there are better formulas, but the Machin’s formula is pretty simple and it is good enough if you want to get just few thousands digits of PI. (A small note: Machin-like formulas are not bad at all, the 2002 record was calculated with a Machin-like formula.)

I didn’t make more researches, I just started to code on my own in C++, because it seemed like a good programming exercise. And I gotta tell, it is. The Operation PI is a one day mission. I coded two classes, one to handle the container of the digits, and an other to handle the floating point arithmetic. The whole project is about 750 lines of code. The following UML class diagram shows the structure of the program:

The lessons I learned from the project:

  1. The implicit copy constructor uses the copy constructor of each data members of the class, so when the class contains only auto data members and the copy constructor of the types (and classes) of the data members are defined in the right way , then the implicit copy constructor will work very well.
  2. Sad, but the parameter of the implicit copy constructor is always non-constant. It means, if you want to construct new objects from the data of const objects, then it is not possible via the implicit copy constructor, you have to define your own copy constructor in that case. Remember, the conversion from T to const T is a trivial conversion and the conversion from const T to T is impossible without casting (without a const_cast). So, if the parameter of the copy constructor is const, then it will works both on const and non-const objects, if the parameter is non-const, then it will works only on non-const objects. (Note: if there is a non-static const or reference data member in the class, then the compiler can’t generate an implicit copy constructor and an implicit assignment operator.)
  3. I wanted to use the implicit copy constructor and the implicit assignment operator in the class BigNumber because of 1.), but I didn’t use it because of the 2.).
  4. The calculation of the PI is very, very simple and the most part of my code is not necessary to solve the original problem (or in other words, these parts are completely irrelevant). But remember, it is just an exercise, the more efforts I do, the more lessons I learn. For example, the BigNumber& operator*(const BigNumber&, const BigNumber&) is useless if we want to calculate the PI, because the complexity of the digit-by-digit multiplication algorithm is O(n^2) so it is too slow to calculate the PI in one second. It works, it is interesting and it is irrelevant. To calculate the PI, all we need is the DigitContainer and the following four operators: multiplying DigitContainers by integers, dividing DigitContainers by integers, addition of two DigitContainers and subtraction of two DigitContainers. Here is a Visual Basic implementation and it is a minimal implementation, it uses just these four functions to calculate ArcTan(x) and PI. My approach is minimal too, but my implementation is not minimal at all.
  5. The trick is, that the Machin’s formula doesn’t require to multiply a char array to an other char array (a BigNumber to an other BigNumber) and it doesn’t require the division of two char arrays. If you can multiply a short int to a BigNumber and if you can divide a BigNumber by a short int, then you can calculate the first 4000 digits with the Machin’s formula. (You have to calculate the sum of the first ~750 terms of ArcTan(1/5) and the sum of the first ~250 terms of (1/239), and yes, these terms contain only such integers, that are smaller than ~1500.
  6. Why the first 4000 digits? “1 page of A4 paper can contain approximately 4200 characters (12 points 6 lines per inch).” However, I’m not sure that this information is accurate.
  7. The last digits are not accurate, so my program calculates the first 4100 digits. It won’t be very hard to derive an upper bound to the error: think about, the program always takes just the first 4100 digits of the terms, so the error of each terms is smaller than 10^-4100. We can use the following formula: Error < [#number of terms] * 10^-precision + Lagrange remainder < ([#number of terms] + 1) * 10^-precision. It means, that log Error < log([#number of terms] + 1) - precision, in other words, if we used one million terms by the calculations, then the last 7 digits are always wrong. The result of the program is always a lower bound, but if we add ([#number of terms] + 1) * 10^-precision to the result, then we get an upper bound and we can select the good digits by comparing upper and lower bounds. However, this project is not about the precision, it is about practicing C++.
  8. On a one year old PC, the program calculates the first 4000 digits of PI in one second. And the program isn’t very optimized. It is an average implementation: It uses accumulator variables and objects, simple char arrays, linear algorithms. (Notice, that the four operator in 4.) are linear. The complexity of the program is O(n * log n), where log n is because of the number of the terms of the Machin’s formula.) But at least my implementation is not a stupid implementation. It doesn’t use dynamic containers like vectors and linked lists, it doesn’t use quadratic algorithms, it doesn’t create new objects and doesn’t allocate new memory after each division and addition. (A studpid implementation is much-much slower, I know it, because my first implementations were pretty stupid.) An average implementation is enough for me now. However, the optimized implementations are amazing. Check this: it is about 1000 times faster than my program, because it uses better and more sophisticated algorithms and low-level optimization (ASM and SSE and etc.).

As usual, here are the source codes of my whole one-day Pi project. Written in pure OOP C++, compiled on Linux with GNU G++ 4.4.5. Use it, try it, enjoy it. And yes, the project is full of ninja comments:).

Advertisements

About vrichard86

I'm Richard and I'm an enthusiastic coder. I want to be better and I think a professional journal is a great self improvement tool. Welcome to my blog, to my hq, to my home on the web!
This entry was posted in C++ and tagged , , , , . Bookmark the permalink.