Passa ai contenuti principali

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

Commenti

Post popolari in questo blog

VB.NET: Convertire un file DOC in RTF e PDF con office interop

In questo post vorrei proporvi del codice per poter convertire un file .doc in un file .rtf oppure .pdf utilizzando le API di interoperabilità di Office.Creeremo una classe, DocConverter, che esporrà le due funzionalità sopra citate.Cominciamo con il prevedere un attributo privato della classe che rappresenterà l’applicazione Word che utilizzeremo per la conversione. Creeremo l’istanza dell’attributo privato all’interno del costruttore della classe:PublicSubNew()
IfNot CreateWordApp() Then
ThrowNew ApplicationException("Assembly di interoperabilità con Office non trovato!")
EndIf
EndSub
Private _wordApp As Word.ApplicationClass
ProtectedFunction CreateWordApp() AsBoolean
Dim retval = True
Try
_wordApp = New Word.ApplicationClass()
_wordApp.Visible = False
Catch ex As System.Exception
_wordApp = Nothing
retval = False
EndTry
Return retval
EndFunction

La conversione del file doc sarà effettuata aprendo il file stesso ed eseguendo un’operazione di SaveAs:

Pr…

VB.NET for Dummies: Gli Eventi

Vorrei iniziare con questo post una serie dedicata ad aspetti di VB.NET di base che possono essere utile a coloro che si avvicinano al mondo .NET e che, in genere, non vengono trattati a livello base.La serie di post non ha la pretesa di essere assolutamente esaustivi sugli argomenti che tratteròIn questo primo post parleremo degli eventi.Cosa sono e a cosa servonoUn evento è la “notifica” dell’accadimento di qualcosa.Quando, ad esempio, premiamo un bottone della finestra di un’applicazione, dietro le quinte, il bottone stesso “notifica” al mondo circostante che qualcuno, in quell’istante, lo ha premuto.Sta, poi, al mondo circostante preoccuparsi di “intercettare” l’evento stesso per gestirlo (tramite un gestore di evento).Attenzione a non confondere la pressione del tasto con la “notifica” della pressione del tasto: l’evento è la “notifica” dell’accadimento, non l’accadimento stesso.Ma a cosa serve tutto ciò?Utilizzare gli eventi è un modo per disaccoppiare due o più attori del nostr…

Creare uno shortcut con VB.NET

Prendendo spunto da un post comparso sul forum MSDN vorrei proporvi un tip su come creare uno shortcut utilizzando VB.NET.Per poter creare uno shortcut possiamo procedere in due modi: o ci studiamo la struttura del file .lnk e scriviamo una classe che è in grado di ricreare tale struttura oppure utilizziamo Windows Scripting Host.La prima soluzione è percorribile ma laboriosa perchè la struttura di un file lnk non è banale. Chi fosse interessato a vedere come è composto, internamente, un file lnk può scaricare la seguente reference guide (link).Io vorrei proporvi la seconda strada e realizzerò una classe che incapsula l’utilizzo di Windows Scripting Host.L’object model di Windows Scripting Host è contenuto nella dll IWshRuntimeLibrary che può essere referenziata, nel nostro progetto, utilizzando il tab COM della finestra di aggiunta delle reference:Tra gli oggetti che troviamo all’interno della libreria utilizzeremo la classe WshShell e la classe WshShortcut.La prima delle due rappres…