ALGORITMI PER IL CALCOLO DEL FATTORIALE

Negli articoli precedenti abbiamo visto che l’algoritmo “naive” per il calcolo della media, varianza e covarianza, non sempre risulta essere il migliore, infatti spesso di preferisce un algoritmo leggermente più complesso ma molto più efficiente. Questo discorso può essere fatto anche per il calcolo di un fattoriale. Nell’articolo precedente è stato preso come esempio per l’utilizzo della struttura try-catch proprio l’algoritmo naive, invece ora presentiamo un algoritmo migliore e più efficiente. Questo metodo, facente parte dei metodi “divide & conquer” è detto Binary Split e consiste nel dividere ricorsivamente in due parti il prodotto. L’idea di base è che in un intervallo di numeri interi e consecutivi [m , n] ci sono n-m+1 termini; volendo dividere in due questo intervallo, potrei avere problemi se la lunghezza dell’intervallo fosse dispari. In questo caso però, attraverso la funzione floor che considera l’itero più piccolo di un numero passato come argomento, è possibile dividere l’intervallo esattamente in due, infatti risulterà [m , n] = [m , m+floor((m-n)/2)] + [m+floor((m-n)/2)+1 , n]. I due split possono essere ulteriormente splittati, fino ad arrivare ai singoli fattori, in questo modo si diminuisce il numero di prodotti. Utilizzando VB.NET mettiamo ora a confronto i due algoritmi

\\ naive

Public Function Fattoriale (n As Integer) As Integer
 Dim Fatt As Integer = 2
 Try
  For i = 3 To n
   Fatt *= i
  Next
 Catch ex As OverflowException
  Return -1
 End Try
 Return Fatt
End Function

\\ binary split

Function Split (m As Integer, n As Integer) As Integer
 Dim SemiDifferenza As Integger = CInt(Math.Floor((n-m)/2)
 Dim F1 As Integer = Split(m,m+SemiDifferenza)
 Dim F2 As Integer = Split(m + SemiDifferenza + 1, n)
 Return F1*F2
End Function