As of 14 March, 2024, the record for calculating the most digits of \(\pi\) stands at 105 trillion digits. This is an extreme example of big number arithmetic, which has important applications in cryptography, financial programming, and scientific computing. The challenge of computing with big numbers has fascinated computer scientists for generations, and it remains an area of active research and development.
The fundamental challenge of big number arithmetic is representing numbers beyond the default precision of a computer. Most personal computers today represent data using up to 64 bits. This provides \(2^{64}\) different values, which when devoted to an integer value permits numbers in the range -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 (19 digits). By settling for only non-negative integers, this can be extended into the 20th digit, but going further requires a different way of representing data.
Although 20 digits sounds enormous, it is insufficient to represent a number like \(21!\) (21 factorial). Because calculations of \(\pi\) typically use series like
\[\frac{1}{\pi} = 12\sum_{k=0}^{\infty}\frac{(-1)^{k}(6k)!(13591409 + 545140134k)}{(3k)!(k!)^{3}640320^{3k+3/2}}\]
even 64 bits of precision is a severe constraint.
Over the course of two or three challenges, you can develop your own library to represent and calculate with numbers of arbitary precision. Here, you begin with storing the numbers, printing them out, and adding and multiplying them together. Yes, libraries already exist for this purpose; however, it is instructive to create your own using the innate capabilities of your chosen programming language.
Create a class of arbitary precision numbers in Python or C++ (a class is the most natural way to implement this new data type; however, you can still create this functionality in a language that is not object-oriented). As a first step, your class should:
Once you have done this, exercise your new class:
In Python, you can use a list where each member represents a single digit. The list is a dynamic structure, so you can add as many members as you need. For efficiency, don't limit yourself to base 10. If your internal base is 1000 (for example), each member of your list can hold values between 0 and 999.
Don't implement subtraction or division, yet. There are clever ways to use the functionality you are building here to do those operations. We'll talk about them in the next challenge of this series.