两个 Ulong 整数相除输出错误的结果

Question

我正在为加泰罗尼亚语数字编写程序。所以这里是公式：

我决定使用公式的中间部分，因为其他部分对我的知识来说太抽象了（也许我在数学上睡得太多了类）。实际上，我的程序在 n = 0;、n = 5;、n = 10; 上工作正常，但是如果我输入 n = 15; - 繁荣来了 - 输出应该是 2 9694845。所以这是我的 child:

using System;
namespace _8_Numbers_of_Catalan
{
    class CatalanNumbers
    {
        static void Main()
        {
            Console.Write("n: ");
            int n = int.Parse(Console.ReadLine());
            Console.WriteLine("Catalan({0})", n);
            //calculating the Catan number from the formula 
            // Catan(n) = [(2*n)!]/[(n+1)! * n!]
            Console.WriteLine((factorial(2 * n)) / (factorial(n + 1) * factorial(n)));
        }//finding the factorial
        private static ulong factorial(int n)
        {
            ulong fact = 1;
            for (int i = 1; i <= n; i++)
            {
                fact *= (ulong)i;
            }
            return fact;
        }
    }
}

如果有明显错误，请提前感谢您的理解。我是编程新手。

Answer 1

你应该为此使用 System.Numerics.BigInteger。（在您的项目中添加 System.Numerics 作为参考）。

private static BigInteger factorial(int n)
{
     BigInteger fact = 1;
     for (int i = 1; i <= n; i++)
     {
        fact *= i;
     }
     return fact;
 }

 // output: 9694845

Answer 2

那是因为您正在使用最多包含 64 位的整数变量执行这些计算。

您对 factorial(15 * 2) 的调用是 30!，这将导致值

265,252,859,812,191,058,636,308,480,000,000

远远超过 64 位整数变量的容量：

18,446,744,073,709,551,615 (0xFFFFFFFFFFFFFFFF).

您可以选择使用 System.Numerics.BigInteger 类型（慢）或 double（最大值为 1.7976931348623157E+308）。这意味着您将失去一些精度，这可能相关也可能不相关。

您拥有的另一个选择是使用一种算法来使用渐近逼近法来逼近大阶乘的值，例如 Mathematica 使用的 Schönhage–Strassen algorithm。

您可能还想查看一些现有的在线资源以在 .NET 中计算大阶乘

作为最后一个 但并非最不重要的 选项（我还没有彻底检查），在我看来可能存在特定的算法可以让你计算（或近似于足够的准确度和精确度）a Catalan number.

两个 Ulong 整数相除输出错误的结果

Dividing two Ulong integers outputs wrong result

c#

math

factorial

catalan