如何使用庫調用在C＃中計算一個階乘？

Question

我需要計算數字的階乘達到100左右！爲了確定一系列硬幣翻轉式數據是否是隨機的，根據this Wikipedia entry on Bayesian probability.正如您在那裏看到的那樣，必要的公式涉及3個階乘計算（但是，有趣的是，這些階乘計算中的兩個計算是在第三個階段）。

我看到了this question here，但我認爲這個整數很快就會被炸掉。如果我有11！/（7！3！），我可以根據維基例子做一個更智能的函數（例如，我可以去（11 * 10 * 9 * 8）/ 3），但這對我來說過早地優化了，因爲我希望它能夠工作，但我並不關心速度（還）。

那麼，爲了得到這個概率，我可以調用一個好的C＃庫來計算階乘？我對可以進行階乘計算的所有精彩內容不感興趣，我只是希望以我能夠操縱它的方式獲得結果。數學命名空間中似乎沒有一個因子函數，因此是問題。

Answer 1

你可以嘗試Math.NET - 我沒有使用過這個庫，但他們列出了因子和對數因子。

Answer 2

關於類似的話題已有previous question。有人鏈接了Fast Factorial Functions網站，其中包括一些有效算法的解釋，甚至包括C＃源代碼。

Answer 3

是否要計算階乘係數或二項式係數？

這聽起來像你想計算二項式係數 - 特別是當你提到11！/（7！3！）。

有可能是能爲你做這個圖書館，但作爲一個（大概）程序員訪問堆棧溢出沒有理由不自己寫一個。這不是太複雜。

爲避免內存溢出，請不要評估結果，直到刪除所有常見因素。

這個算法仍然需要改進，但是這裏有一個很好的算法的基礎。分母的值需要被分解爲它們的主要因素以獲得最佳結果。就目前而言，這很快就會運行n = 50。

float CalculateBinomial(int n, int k) 
{ 
    var numerator = new List<int>(); 
    var denominator = new List<int>(); 
    var denominatorOld = new List<int>(); 

    // again ignore the k! common terms 
    for (int i = k + 1; i <= n; i++) 
     numerator.Add(i); 

    for (int i = 1; i <= (n - k); i++) 
    { 
     denominator.AddRange(SplitIntoPrimeFactors(i)); 
    } 

    // remove all common factors 
    int remainder;     
    for (int i = 0; i < numerator.Count(); i++) 
    { 
     for (int j = 0; j < denominator.Count() 
      && numerator[i] >= denominator[j]; j++) 
     { 
      if (denominator[j] > 1) 
      { 
       int result = Math.DivRem(numerator[i], denominator[j], out remainder); 
       if (remainder == 0) 
       { 
        numerator[i] = result; 
        denominator[j] = 1; 
       } 
      } 
     } 
    } 

    float denominatorResult = 1; 
    float numeratorResult = 1; 

    denominator.RemoveAll(x => x == 1); 
    numerator.RemoveAll(x => x == 1); 

    denominator.ForEach(d => denominatorResult = denominatorResult * d); 
    numerator.ForEach(num => numeratorResult = numeratorResult * num); 

    return numeratorResult/denominatorResult; 
} 

static List<int> Primes = new List<int>() { 2, 3, 5, 7, 11, 13, 17, 19, 
    23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 }; 

List<int> SplitIntoPrimeFactors(int x) 
{ 
    var results = new List<int>(); 
    int remainder = 0; 

    int i = 0; 
    while (!Primes.Contains(x) && x != 1) 
    { 
     int result = Math.DivRem(x, Primes[i], out remainder); 
     if (remainder == 0) 
     { 
      results.Add(Primes[i]); 
      x = result; 
      i = 0; 
     } 
     else 
     { 
      i++; 
     } 
    } 
    results.Add(x); 
    return results; 
} 

我可以估計N = 110，K = 50（返回6×10^31），但不能運行N = 120，K = 50。

Answer 4

using System; 
//calculating factorial with recursion 
namespace ConsoleApplication2 
{ 
    class Program 
    { 
     long fun(long a) 
     { 
      if (a <= 1) 
      { 
       return 1;} 
      else 
      { 
       long c = a * fun(a - 1); 
       return c; 
      }} 

     static void Main(string[] args) 
     { 

      Console.WriteLine("enter the number"); 
      long num = Convert.ToInt64(Console.ReadLine()); 
      Console.WriteLine(new Program().fun(num)); 
      Console.ReadLine(); 
     } 
    } 
} 

Answer 5

以下可以計算出的5000的階乘在1秒。

public class Number 
{ 
    #region Fields 
    private static long _valueDivision = 1000000000; 
    private static int _valueDivisionDigitCount = 9; 
    private static string _formatZeros = "000000000"; 
    List<long> _value; 
    #endregion 

    #region Properties 
    public int ValueCount { get { return _value.Count; } } 
    public long ValueAsLong 
    { 
     get 
     { 
      return long.Parse(ToString()); 
     } 
     set { SetValue(value.ToString()); } 
    } 
    #endregion 

    #region Constructors 
    public Number() 
    { 
     _value = new List<long>(); 
    } 
    public Number(long value) 
     : this() 
    { 
     SetValue(value.ToString()); 
    } 
    public Number(string value) 
     : this() 
    { 
     SetValue(value); 
    } 
    private Number(List<long> list) 
    { 
     _value = list; 
    } 
    #endregion 

    #region Public Methods 
    public void SetValue(string value) 
    { 
     _value.Clear(); 
     bool finished = false; 
     while (!finished) 
     { 
      if (value.Length > _valueDivisionDigitCount) 
      { 
       _value.Add(long.Parse(value.Substring(value.Length - _valueDivisionDigitCount))); 
       value = value.Remove(value.Length - _valueDivisionDigitCount, _valueDivisionDigitCount); 
      } 
      else 
      { 
       _value.Add(long.Parse(value)); 
       finished = true; 
      } 
     } 
    } 
    #endregion 

    #region Static Methods 
    public static Number operator +(Number c1, Number c2) 
    { 
     return Add(c1, c2); 
    } 
    public static Number operator *(Number c1, Number c2) 
    { 
     return Mul(c1, c2); 
    } 
    private static Number Add(Number value1, Number value2) 
    { 
     Number result = new Number(); 
     int count = Math.Max(value1._value.Count, value2._value.Count); 
     long reminder = 0; 
     long firstValue, secondValue; 
     for (int i = 0; i < count; i++) 
     { 
      firstValue = 0; 
      secondValue = 0; 
      if (value1._value.Count > i) 
      { 
       firstValue = value1._value[i]; 
      } 
      if (value2._value.Count > i) 
      { 
       secondValue = value2._value[i]; 
      } 
      reminder += firstValue + secondValue; 
      result._value.Add(reminder % _valueDivision); 
      reminder /= _valueDivision; 
     } 
     while (reminder > 0) 
     { 
      result._value.Add(reminder % _valueDivision); 
      reminder /= _valueDivision; 
     } 
     return result; 
    } 
    private static Number Mul(Number value1, Number value2) 
    { 
     List<List<long>> values = new List<List<long>>(); 
     for (int i = 0; i < value2._value.Count; i++) 
     { 
      values.Add(new List<long>()); 
      long lastremain = 0; 
      for (int j = 0; j < value1._value.Count; j++) 
      { 
       values[i].Add(((value1._value[j] * value2._value[i] + lastremain) % _valueDivision)); 
       lastremain = ((value1._value[j] * value2._value[i] + lastremain)/_valueDivision); 
       //result.Add((); 
      } 
      while (lastremain > 0) 
      { 
       values[i].Add((lastremain % _valueDivision)); 
       lastremain /= _valueDivision; 
      } 
     } 
     List<long> result = new List<long>(); 
     for (int i = 0; i < values.Count; i++) 
     { 
      for (int j = 0; j < i; j++) 
      { 
       values[i].Insert(0, 0); 
      } 
     } 
     int count = values.Select(list => list.Count).Max(); 
     int index = 0; 
     long lastRemain = 0; 
     while (count > 0) 
     { 
      for (int i = 0; i < values.Count; i++) 
      { 
       if (values[i].Count > index) 
        lastRemain += values[i][index]; 
      } 
      result.Add((lastRemain % _valueDivision)); 
      lastRemain /= _valueDivision; 
      count -= 1; 
      index += 1; 
     } 
     while (lastRemain > 0) 
     { 
      result.Add((lastRemain % _valueDivision)); 
      lastRemain /= _valueDivision; 
     } 
     return new Number(result); 
    } 
    #endregion 

    #region Overriden Methods Of Object 
    public override string ToString() 
    { 
     string result = string.Empty; 
     for (int i = 0; i < _value.Count; i++) 
     { 
      result = _value[i].ToString(_formatZeros) + result; 
     } 
     return result.TrimStart('0'); 
    } 
    #endregion 
} 

class Program 
{ 
    static void Main(string[] args) 
    { 
     Number number1 = new Number(5000); 
     DateTime dateTime = DateTime.Now; 
     string s = Factorial(number1).ToString(); 
     TimeSpan timeSpan = DateTime.Now - dateTime; 
     long sum = s.Select(c => (long) (c - '0')).Sum(); 
    } 
    static Number Factorial(Number value) 
    { 
     if(value.ValueCount==1 && value.ValueAsLong==2) 
     { 
      return value; 
     } 
     return Factorial(new Number(value.ValueAsLong - 1)) * value; 
    } 
}