Calculate Nth Pi Digit

Question

I am trying to calculate the nth digit of Pi without using Math.Pi which can be specified as a parameter. I modified an existing algorithm, since I like to find the Nth digit without using string conversions or default classes. This is how my algorithm currently looks like:

   static int CalculatePi(int pos)
    {
        List<int> result = new List<int>();
        int digits = 102;
        int[] x = new int[digits * 3 + 2];
        int[] r = new int[digits * 3 + 2];
        for (int j = 0; j < x.Length; j++)
            x[j] = 20;
        for (int i = 0; i < digits; i++)
        {
            int carry = 0;
            for (int j = 0; j < x.Length; j++)
            {
                int num = (int)(x.Length - j - 1);
                int dem = num * 2 + 1;
                x[j] += carry;
                int q = x[j] / dem;
                r[j] = x[j] % dem;
                carry = q * num;
            }
            if (i < digits - 1)

                result.Add((int)(x[x.Length - 1] / 10));
            r[x.Length - 1] = x[x.Length - 1] % 10; ;
            for (int j = 0; j < x.Length; j++)
                x[j] = r[j] * 10;
        }
        return result[pos];
    }

So far its working till digit 32, and then, an error occurs. When I try to print the digits like so:

  static void Main(string[] args)
    {
        for (int i = 0; i < 100; i++)
        {
            Console.WriteLine("{0} digit of Pi is : {1}", i, CalculatePi(i));
        }

        Console.ReadKey();
    }

This I get 10 for the 32rd digit and the 85rd digit and some others as well, which is obviously incorrect.

The original digits from 27 look like so:

...3279502884.....

but I get

...32794102884....

Whats wrong with the algorithm, how can I fix this problem? And can the algorithm still be tweaked to improve the speed?

Answer 1

So far it works right up until the cursor reaches digit 32. Upon which, an exception is thrown.

Rules are as follows:

• Digit 31 is incorrect, because it should be 5 not a 4.
• Digit 32 should be a 0.
• When you get a 10 digit result you need to carry 1 over to the previous digit to change the 10 to a 0.

The code changes below will work up to ~ digit 361 when 362 = 10.

Once the program enters the 900's then there are a lot of wrong numbers.

Inside your loop you can do this by keeping track of the previous digit, only adding it to the list after the succeeding digit has been computed.

Overflows need to be handled as they occur, as follows:

    int prev = 0;

    for (int i = 0; i < digits; i++)
    {
        int carry = 0;

        for (int j = 0; j < x.Length; j++)
        {
            int num = (int)(x.Length - j - 1);

            int dem = num * 2 + 1;

            x[j] += carry;

            int q = x[j] / dem;

            r[j] = x[j] % dem;

            carry = q * num;

        }

        // calculate the digit, but don't add to the list right away:
        int digit = (int)(x[x.Length - 1] / 10);

        // handle overflow:
        if(digit >= 10)
        {
            digit -= 10;

            prev++;

        }

        if (i > 0)
            result.Add(prev);

        // Store the digit for next time, when it will be the prev value:

        prev = digit;

        r[x.Length - 1] = x[x.Length - 1] % 10;

        for (int j = 0; j < x.Length; j++)
            x[j] = r[j] * 10;

    }

Since the digits are being updated sequentially one-by-one, one whole iteration later than previously, the if (i < digits - 1) check can be removed.

However, you need to add a new one to replace it: if (i > 0), because you don't have a valid prev value on the first pass through the loop.

The happy coincidence of computing only the first 100 digits means the above will work.

However, what do you suppose will happen when a 10 digit result follows a 9 digit one? Not good news I'm afraid, because the 1 with need carrying over to the 9 (the previous value), which will make it 10.

A more robust solution is to finish your calculation, then do a loop over your list going backwards, carrying any 10s you encounter over to the previous digits, and propagating any carries.

Consider the following:

for (int pos = digits - 2; pos >= 1; pos--)
{
     if(result[pos] >= 10)
     {
          result[pos] -= 10;

          result[pos - 1] += 1;

     }

}