c# - 计算第 N 个 Pi 数字

Question

我试图在不使用可以指定为参数的 Math.Pi 的情况下计算 Pi 的第 n 个数字。我修改了现有算法，因为我喜欢在不使用字符串转换或默认类的情况下找到第 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;

     }

}