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:

La 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,

per definizione si chiede poi che 0!=1.

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

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:

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!:

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!!!

Technorati Tags: Fattoriale,100000!,Parallel.For,BigInteger,WPF,MVVM