Calculate Nth Pi Digit

Question

Я пытаюсь вычислить n-ю цифру Pi, не используя Math.Pi, который может быть указан как параметр. Я изменил существующий алгоритм, так как мне нравится находить N-й разряд без использования строковых преобразований или классов по умолчанию. Это как мой алгоритм в настоящее время выглядит следующим образом:

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]; 
    } 

До сих пор его работы до цифры 32, а затем, возникает ошибка. Когда я пытаюсь напечатать цифры следующим образом:

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(); 
    } 

Это я 10 для 32rd цифры и 85rd цифры и некоторые другие, а также, что, очевидно, неверно.

Оригинальные цифры от 27 выглядеть так:

... 3279502884 .....

, но я получаю

... 32794102884. ...

Что не так с алгоритмом, как я могу исправить эту проблему? И может ли алгоритм по-прежнему корректироваться, чтобы улучшить скорость?

Answer 1

Пока он работает до тех пор, пока курсор не достигнет цифры 32. На это выдается исключение.

Правила заключаются в следующем:

• Digit 31 is incorrect, поскольку она должна быть 5 не 4.
• Digit 32 должен быть 0.
• Когда вы получите результат на 10 цифр вам необходимо перенести 1 на предыдущую цифру, чтобы сменить значение 10 на 0.

Нижеуказанные изменения кода будут работать до ~ цифры 361, когда 362 = 10.

Как только программа входит в 900-е годы, есть много неправильных цифр.

Внутри вашей петли вы можете сделать это, сохранив предыдущую цифру, добавив ее только в список после того, как последующая цифра была вычислена.

Переполнение должны быть обработаны, как они происходят, следующим образом:

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; 

    } 

Поскольку цифры обновляется последовательно один за другим, одно целое итерации позднее, чем ранее, if (i < digits - 1) проверка может быть удалена.

Для того, чтобы его заменить, необходимо добавить новый: if (i > 0), так как у вас нет действительного значения prev при первом проходе через цикл.

Счастливое совпадение вычисления только первых 100 цифр означает, что выше будет работать.

Однако, как вы думаете, что произойдет, когда результат из 10 цифр следует за 9-значным? Нехорошая новость. Боюсь, потому что 1 с необходимостью переносить на 9 (предыдущее значение), что сделает его 10.

Более надежное решение - это закончить расчет, а затем выполнить цикл над вашим список идет назад, перенося любые 10, с которыми вы сталкиваетесь на предыдущие цифры, и распространяете любые переносы.

Рассмотрим следующий пример:

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

      result[pos - 1] += 1; 

    } 

}