Your task in this exercise is to calculate 5000 digits of pi. In particular, you will implement the Spigot algorithm as originally proposed by Stanley Rabinowitz and Stan Wagon. The algorithm has a few nice properties, which is that it has limited memory footprint (the memory footprint is essentially just a consequence of the required number of digits), the digits are computed one by one, and each iteration involves only integer computations. The following explanation is taken from the below link, please check it out for more visual descriptions of what the algorithm is supposed to do (Essentially the first page of the document is enough), and there is also an example Pascal code towards the end of the document.

http://stanleyrabinowitz.com/bibliography/spigot.pdf

Those who are interested in the origin of the algorithm (basis conversion) are encouraged to do further research online. Here we only explain how the algorithm works:

• The algorithm starts by defining an array A filled with the number 2. The length of A is a consequence of the required number of digits N. In particular, if N=5000, the length is to be set to len = floor(10 * N/3) + 1.
• We assign a fractional coefficient to each column i (the first column being denoted by i=1). The numerator num_i is equal to (i­‐1) and the denominator den_i is equal to (2 * i – 1).
• We now process each column starting from the right-­most one and towards the left. For each column i, multiply the corresponding entry in A by 10 and add the “carry” from the previous column i+1. How to calculate the “carry” for each column is indicated below, and simply use 0 for the starting, right-­‐most column.
• For the resulting value in the currently treated column i of A, calculate the quotient q and remainder r after division by den_i. Replace the value in A by the remainder r, and define the carry of the column as q * num_i (to be used for the next column, i.e. column i-­1).
• A special case is given by column 1 (i.e. the left-­‐most one). For this column, we divide the number by 10 rather than 1. The quotient is the next digit of pi, and the remainder is retained as the first element in A.

There is only one tricky part in the algorithm, which is that the quotient may be 10 on some occasions. If this happens, the previous digit should be incremented by 1. If the previous digit is 9, the second-­‐last digit should be incremented instead, etc.

To solve this problem, the smallest set of preceding digits that includes exactly one non-­‐9 digit needs to be first buffered before being printed. Printing then happens conditionally and according to the following examples:

Buffer: [4], New digit: 3 -> Print 4 and set buffer to [3]
Buffer: [4], New digit: 9 -> Print nothing and set buffer to [4,9] 
Buffer: [4], New digit: 10 -> Print 5 and set buffer to [0]
Buffer: [4,9]. New digit: 2 -> Print 49 and set buffer to [2]
Buffer: [4,9]. New digit: 9 -> Print nothing and set buffer to [4,9,9] 
Buffer: [4,9]. New digit: 10 -> Print 50 and set buffer to [0]
Buffer: [4,9,9]. New digit: 0 -> Print 499 and set buffer to [0]
Buffer: [4,9,9]. New digit: 9 -> Print nothing and set buffer to [4,9,9,9] 
Buffer: [4,9,9]. New digit: 10 -> Print 500 and set buffer to [0]
…

Note that the buffer is always of the form of a single digit that is different from 9 followed by a certain number of 9’s (possibly none). It is best to store the buffer as such rather than as a dynamically resized array.

The last exercise requires you to work with C-­arrays. An array of a certain type and length can simply be defined by the declaration statement:

type arrayName[length];

and elements within this array can be referred to by using

type copy = arrayName[indexVariable];

or

arrayName[indexVariable] = newValue;

Note that length in the declaration statement needs to be a constant, not a variable. Though modern definitions of C permit variable sized arrays, the strict standard in fact does not preview this. Good luck!