lunedì 26 luglio 2010

System.Numerics.BigInteger + Parallel.For …… ed il fattoriale è servito!!

Uno dei sogni dei matematici di tutti i tempi è quello di calcolare il fattoriale di un qualsiasi numero intero. Ora, con l’introduzione della structure BigInteger del namespace System.Numerics il sogno diventa realtà.

La structure BigInteger consente di memorizzare un numero intero di qualsiasi dimensione:

Structure BigIntegerLa struttura memorizza il numero intero utilizzando un array di UInt32 e il segno con un Int32.

La struttura mette a disposizione una serie di metodi e di operatori che consentono di eseguire le usuali operazioni matematiche tra interi (anche utilizzando Int16, Int32 o Int64).

Un esempio classico di utilizzo della BigInteger è il calcolo del fattoriale.

Per chi non lo sapesse, il fattoriale si definisce nel seguente modo:

In matematica, se n è un intero positivo, si definisce n fattoriale e si indica con n! il prodotto dei primi n numeri interi positivi. In formule,

 n! := \prod_{k=1}^n k = 1\cdot2\cdot3\cdots(n-1)\cdot n

per definizione si chiede poi che 0!=1.

La funzione fattoriale può anche essere definita in modo ricorsivo:

 n! := \left\{ \begin{matrix}1 \quad&&\mbox{se } n=0;
                      \\
                      n(n-1)! &&\mbox{se } n\ge1~.\end{matrix} \right.

Questa definizione ci viene utile per poter eseguire il calcolo effettivo del fattoriale con un ciclo iterativo.

Se proviamo ad implementare una funzione per il calcolo del fattoriale con il massimo intero messo a disposizione dal framework prima dell’introduzione del BigInteger (cioè UInt64), possiamo arrivare al calcolo di :

20! = 2432902008176640000

in quanto 21! sarebbe pari a 51090942171709440000 che è maggiore del massimo intero contenuto in un UInt64 (18446744073709551615).

Una soluzione è memorizzare l’intero in un array di UInt64 e mettere in piedi tutta l’aritmetica che si occupa di “shiftare” i valori contenuti nell’array a seguito delle comuni operazioni matematiche e di “allargare” l’array in maniera opportuna.

L’alternativa offerta dal framework 4.0 è utilizzare la struttura BigInteger.

Utilizzando BigInteger non c’è virtualmente limite al numero n di cui calcolare il fattoriale.

La soluzione riportata in allegato contiene una semplice applicazione WPF 4.0 che permette di calcolare il fattoriale (utilizzando anche algoritmo parallelo).

L’applicazione utilizza un pattern MVVM il cui diagramma delle classi è il seguente:

Diagramma delle classi

Il fulcro dell’applicazione è la classe FactorialModel che contiene l’algoritmo di calcolo vero e proprio:

  1. Imports System.Numerics
  2. Imports System.Threading.Tasks
  3.  
  4. Namespace Model
  5.     Public Class FactorialModel
  6.         Public Property Argument As Int64
  7.  
  8.         Private _Factorial As BigInteger?
  9.         Public Property Factorial As BigInteger?
  10.             Get
  11.                 Return Me._Factorial
  12.             End Get
  13.             Protected Set(ByVal value As BigInteger?)
  14.                 Me._Factorial = value
  15.             End Set
  16.         End Property
  17.  
  18.         Public Property UseParallelAlgorithm As Boolean = True
  19.  
  20.         Public Function Calculate() As Boolean
  21.             Dim retval = False
  22.             Dim fatt As BigInteger = 1
  23.             If Argument < 0 Then
  24.                 Factorial = Nothing
  25.             Else
  26.                 Try
  27.                     If UseParallelAlgorithm Then
  28.                         Parallel.For(2, Argument + 1,
  29.                            Sub(i)
  30.                                fatt *= i
  31.                            End Sub)
  32.                     Else
  33.                         For i = 2 To Argument
  34.                             fatt *= i
  35.                         Next
  36.                     End If
  37.                     Factorial = fatt
  38.                     retval = True
  39.                 Catch ex As Exception
  40.                     Factorial = Nothing
  41.                 End Try
  42.             End If
  43.             Return retval
  44.         End Function
  45.     End Class
  46. End Namespace

La proprietà Argument definisce il valore di cui calcolare il fattoriale, la proprietà UseParallelAlgorithm definisce se utilizzare un For Each parallelo (disponibile nel framework 4.0) o uno classico e il metodo Calculate() esegue l’effetivo calcolo valorizzando opportunamente la proprietà Factorial:

 

  1. Public Function Calculate() As Boolean
  2.     Dim retval = False
  3.     Dim fatt As BigInteger = 1
  4.     If Argument < 0 Then
  5.         Factorial = Nothing
  6.     Else
  7.         Try
  8.             If UseParallelAlgorithm Then
  9.                 Parallel.For(2, Argument + 1,
  10.                              Sub(i)
  11.                                  fatt *= i
  12.                              End Sub)
  13.             Else
  14.                 For i = 2 To Argument
  15.                     fatt *= i
  16.                 Next
  17.             End If
  18.             Factorial = fatt
  19.             retval = True
  20.         Catch ex As Exception
  21.             Factorial = Nothing
  22.         End Try
  23.     End If
  24.     Return retval
  25. End Function

 

Da notare l’utilizzo del costrutto Parallel.For che diminuisce il tempo di calcolo nel caso di valori Argument molto alti.

Con l’utilizzo del BigInteger, quindi si può pensare di calcolare 1.000.000!:

1000000!

1.000.000! è un intero con 792.366 cifre!

Ora possiamo sognare anche altro!!!


 

P.S.: Vorrei ringraziare Alessandro Del Sole la classe RelayCommand che ho “meschinamente” utilizzato nella mia soluzione. Grazie Ale!!!

Nessun commento: