c# - Calculate Nth Pi Digit -

i trying calculate nth digit of pi without using math.pi can specified parameter. modified existing algorithm, since find nth digit without using string conversions or default classes. how algorithm 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];         (int j = 0; j < x.length; j++)             x[j] = 20;         (int = 0; < digits; i++)         {             int carry = 0;             (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; ;             (int j = 0; j < x.length; j++)                 x[j] = r[j] * 10;         }         return result[pos];     } 

so far working till digit 32, , then, error occurs. when try print digits so:

  static void main(string[] args)     {         (int = 0; < 100; i++)         {             console.writeline("{0} digit of pi : {1}", i, calculatepi(i));         }          console.readkey();     } 

this 10 32rd digit , 85rd digit , others well, incorrect.

the original digits 27 so:

...3279502884.....

but get

...32794102884....

whats wrong algorithm, how can fix problem? , can algorithm still tweaked improve speed?

so far works right until cursor reaches digit 32. upon which, exception thrown.

rules follows:

• digit 31 is incorrect, because should 5 not 4.
• digit 32 should 0.
• when 10 digit result need carry 1 on previous digit change 10 0.

the code changes below work ~ digit 361 when 362 = 10.

once program enters 900's there lot of wrong numbers.

inside loop can keeping track of previous digit, adding list after succeeding digit has been computed.

overflows need handled occur, follows:

    int prev = 0;      (int = 0; < digits; i++)     {         int carry = 0;          (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 digit, don't add 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 digit next time, when prev value:          prev = digit;          r[x.length - 1] = x[x.length - 1] % 10;          (int j = 0; j < x.length; j++)             x[j] = r[j] * 10;      } 

since digits being updated sequentially one-by-one, 1 whole iteration later previously, if (i < digits - 1) check can removed.

however, need add new 1 replace it: if (i > 0), because don't have valid prev value on first pass through loop.

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

however, suppose happen when 10 digit result follows 9 digit one? not news i'm afraid, because 1 need carrying on 9 (the previous value), make 10.

a more robust solution finish calculation, loop on list going backwards, carrying 10s encounter on previous digits, , propagating carries.

consider following:

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