Una struttura per i coefficienti binomiali
Recentemente mi sono trovato di fronte alla necessità di fare dei calcoli con coefficienti binomiali, ma la presenza di tutti quei fattoriali non è certo di buon auspicio. Se dovessi calcolare ogni coefficiente binomiale secondo la definizione dovrei calcolare tre fattoriali. Essendo una funzione che diverge in modo estremamente veloce, sarebbe già un'impresa calcolare qualcosa di irrisorio come 30! Per questo ho scritto una struttura che semplicemente memorizza i fattori moltiplicativi presenti al numeratore e al denominatore della frazione, immaginando di sviluppare tutti i fattoriali. Inoltre, elimina i fattori uguali, ossia semplifica la frazione. Per ottenere il risultato come double, poi, moltiplica e divide alternativamente per i coefficienti presenti al numeratore o al denominatore, per arginare la perdita di precisione dovuta al passaggio di ordine di grandezza (questa parte si può migliorare ulteriormente). Spero che possa essere utile a qualcuno:
struct BinomialCoefficient
{
private List<Int32> numFactors, denFactors;
public BinomialCoefficient(Int32 n, Int32 k)
{
numFactors = Enumerable.Range(1, n).ToList();
denFactors = Enumerable.Range(1, k).Concat(Enumerable.Range(1, n - k)).ToList();
this.Simplify();
}
public static BinomialCoefficient operator *(BinomialCoefficient binom1, BinomialCoefficient binom2)
{
BinomialCoefficient result = new BinomialCoefficient();
result.InitFields();
result.numFactors.AddRange(binom1.numFactors.Concat(binom2.numFactors));
result.denFactors.AddRange(binom1.denFactors.Concat(binom2.denFactors));
result.Simplify();
return result;
}
public static BinomialCoefficient operator /(BinomialCoefficient binom1, BinomialCoefficient binom2)
{
BinomialCoefficient inverse2 = new BinomialCoefficient();
inverse2.numFactors = binom2.denFactors;
inverse2.denFactors = binom2.numFactors;
return binom1 * inverse2;
}
public static explicit operator Double(BinomialCoefficient binom)
{
binom.numFactors.Sort();
binom.denFactors.Sort();
Double result = 1.0;
Int32 minCount = Math.Min(binom.numFactors.Count, binom.denFactors.Count);
for (Int32 i = 0; i < minCount; i++)
result *= (Double)binom.numFactors[i] / binom.denFactors[i];
if (binom.numFactors.Count > binom.denFactors.Count)
for (Int32 i = minCount; i < binom.numFactors.Count; i++)
result *= (Double)binom.numFactors[i];
else
for (Int32 i = minCount; i < binom.denFactors.Count; i++)
result /= (Double)binom.denFactors[i];
return result;
}
private void InitFields()
{
numFactors = new List<int>();
denFactors = new List<int>();
}
private void Simplify()
{
for(Int32 i = 0; i < this.numFactors.Count; i++)
for(Int32 j = 0; j < this.denFactors.Count; j++)
if (this.numFactors[i] == this.denFactors[j])
{
this.numFactors.RemoveAt(i);
this.denFactors.RemoveAt(j);
i--;
break;
}
}
}
Leave a Reply
You must be logged in to post a comment.
