计算第 N 个 Pi 数字

Question

我正在尝试计算 Pi 的第 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();
    }

第32位和第85位以及其他一些我得到10，这显然是不正确的。

27 的原始数字如下所示：

...3279502884.....

但我明白了

...32794102884....

算法有什么问题，我该如何解决这个问题？是否仍可以调整算法以提高速度？

Answer 1

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

规则如下：

数字 31 is incorrect，因为它应该是 5 而不是 4。
第 32 位应为 0。
当您得到 10 位数的结果时，您需要将 1 移到前一位以将 10 更改为 0。

当 362 = 10 时，下面的代码更改将工作到 ~ 数字 361。

一旦程序进入 900's，就会有很多错误的数字。

在您的循环中，您可以通过跟踪前一个数字来完成此操作，仅在计算出后续数字后才将其添加到列表中。

溢出需要在发生时进行处理，如下：

    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;

     }

}

计算第 N 个 Pi 数字

Calculate Nth Pi Digit

c#

algorithm

pi

digit