Con un amico stiamo analizzando/realizzando un software statistico che fa largo uso del fattoriale e del coefficiente binomiale. Dovendo calcolare il fattoriale di valori come 500, non possiamo utilizzare i “normali” tipi di dato offerti dal .Net Framework 3.5, dato che, con un float calcoliamo al più 34!, con un UInt64 65! e con un double 170!. Ben lontani dal nostro obiettivo...
Si potrebbe allora utilizzare qualche formula di approssimazione, come la formula di Stirling (utilizzabile operativamente in questo modo). Così facendo potremmo ottenere un risultato esprimibile secondo la notazione scientifica: 1,21993348682175 *10^1134, ma non potremmo operare direttamente, a meno di ulteriori approssimazioni e utilizzando operazioni tra potenze. Ricordo allora che nella versione CTP del .Net Framework 3.5 esisteva la classe BigInteger, poi rimossa dalla versione finale, ma presente nella versione beta del .Net Framework 4.0. Proviamo a vedere cosa succede in questo caso. Scrivendo una semplice routine ricorsiva e un’applicazione console di test:
static void Main(string[] args)
{
BigInteger value = 500;
BigInteger result = Fattoriale(value);
Console.WriteLine(result.ToString());
Console.ReadKey();
}
public static BigInteger Fattoriale(BigInteger n)
{
if (n == 0)
return 1;
else
return n * Fattoriale(n - 1);
}
otteniamo:
Perfetto!
Però, essendo il .Net Framework 4.0 in versione beta, come possiamo risolvere utilizzando la versione 3.5 ?
Su CodePlex,troviamo un’interessante progetto: IntX. Una libreria scritta interamente in codice C# 2.0 che una volta referenziata ai nostri progetti permettere di risolve brillantemente il problema. Secondo l’autore la complessità computazionale dell’algoritmo di calcolo è O(N * log N). Utilizzando il codice d’esempio sul sito del progetto, otteniamo che 500! è uguale a:
Quello che ci aspettavamo. Utilizzando il tipo IntX possiamo eseguire operazioni di moltiplicazione, divisione, potenza etc…
P.S.: Una lista dei primi 999 fattoriali può essere trovata qui.
Technorati Tag:
BigInteger