Come posso calcolare un fattoriale in C# usando una chiamata alla biblioteca?

Question

Ho bisogno di calcolare il fattoriale di numeri fino a circa 100! per determinare se una serie di dati in stile flip moneta è casuale, come da this Wikipedia entry on Bayesian probability. Come puoi vedere, la formula necessaria riguarda 3 calcoli fattoriali (ma, interessante, due di questi calcoli fattoriali sono calcolati lungo la strada verso il terzo).

Ho visto this question here, ma pensavo che il numero intero sarebbe esploso abbastanza rapidamente. Potrei anche fare una funzione più intelligente del calcolo fattoriale (cioè, se ho 11!/(7! 3!), Come per l'esempio wiki, potrei andare a (11 * 10 * 9 * 8)/3!), Ma questo mi fa pensare ad un'ottimizzazione prematura, nel senso che voglio che funzioni, ma non mi interessa la velocità (ancora).

Quindi cos'è una buona libreria C# che posso chiamare per calcolare il fattoriale per ottenere tale probabilità? Non sono interessato a tutte le meraviglie che possono andare nel calcolo fattoriale, voglio solo il risultato in modo che io possa manipolarlo. Non sembra esserci una funzione fattoriale nello spazio dei nomi Math, quindi la domanda.

Answer 1

Si potrebbe provare Math.NET - Non ho usato quella libreria, ma elencano Factorial e Fattoriale logaritmico.

Answer 2

C'è stato un previous question su un argomento simile. Qualcuno ha collegato il sito web Fast Factorial Functions, che include alcune spiegazioni di algoritmi efficienti e persino il codice sorgente C#.

Answer 3

Vuoi calcolare fattoriali o coefficienti binomiali?

Sembra che si vogliano calcolare i coefficienti binomiali, specialmente quando si parla di 11!/(7! 3!).

Potrebbe esserci una libreria che può farlo per voi, ma come programmatore (presumibilmente) che visita lo stack overflow non c'è motivo di non scriverne uno da soli. Non è troppo complicato.

Per evitare l'overflow della memoria, non valutare il risultato fino a quando non vengono rimossi tutti i fattori comuni.

Questo algoritmo deve ancora essere migliorato, ma qui si trovano le basi per un buon algoritmo. I valori del denominatore devono essere suddivisi nei fattori primi per il miglior risultato. Così com'è, questo verrà eseguito per n = 50 abbastanza rapidamente.

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; 
} 

posso stimare n = 110, k = 50 (restituisce 6x10^31), ma non può essere eseguito 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

Il seguente in grado di calcolare il fattoriale di 5000 in 1 secondo.

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; 
    } 
}