Вычислить N-ю цифру Пи

Я пытаюсь вычислить n-ю цифру числа Пи без использования 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 для 32-й цифры и 85-й цифры, а также некоторых других, что явно неверно.

введите здесь описание изображения

Исходные цифры из числа 27 выглядят так:

...3279502884.....

но я получаю

...32794102884....

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


c# algorithm pi digit
person Dark Side    schedule 31.05.2015    source источник
comment
хорошо, используйте отладчик и сравните с исходной программой, вы думаете, мы должны отладить ее для вас?   -  person Philip Stuyck    schedule 31.05.2015
comment
Улучшение скорости заключается в том, что вычисление не вызывается в цикле, потому что вы пересчитываете список цифр снова и снова, просто чтобы извлечь другую цифру. Вернуть список вместо одного значения.   -  person M Oehm    schedule 31.05.2015
comment
@MOehm: Спасибо за идею. Но у вас также есть идея о неправильной цифре «10»? Как я мог исправить эту ошибку в алгоритме?   -  person Dark Side    schedule 31.05.2015

Ответы (1)


arrow_upward
5
arrow_downward

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

Правила следующие:

  • Цифра 31 неверна, потому что она должна быть 5, а не а 4.
  • Цифра 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;

     }

}
person samgak    schedule 01.06.2015