计算第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

到目前为止,它一直工作直到光标到达数字32.此时,抛出异常.

规则如下:

• 数字31 不正确,因为它应该是5而不是4.
• 数字32应为0.
• 当你得到一个10位数的结果时,你需要将1转到前一个数字,将10改为0.

当362 = 10时,下面的代码更改将最多为〜数字361.

一旦程序进入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;

     }

}