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…

Cambiare la lingua di Visual Studio 2008

Oggi ho avuto qualche problema installando Windows Mobile 6 Professional SDK Refresh e Windows Mobile 6 Standard SDK Refresh.Scaricati i file di installazione e installati, ho provato a creare un progetto di tipo Windows Mobile 6.0 e mi sono beccato questo errore:Dopo qualche smanettamento abbiamo scoperto (e ringrazio il mitico Matteo per l’aiuto) che il mio Visual Studio 2008, pur essendo in Inglese (prova ne era il fatto che gli hotfix e la SP installata erano nella lingua di Albione) aveva come lingua impostata quella del sistema operativo (italiano).Ovviamente, non avrebbe mai potuto trovare la cartella 1040 (italiano) visto che l’installazione dell’SDK aveva supposto che la lingua del Visual Studio fosse Inglese (1033).La soluzione del problema è duplice:1) Duplicate la cartella 1033 presente nel percorso evidenziato dall’errore e la rinominate 10402) cambiate la lingua di Visual Studio.Per questa ultima eventualità basta andare nel menù Strumenti/Opzioni:e cambiare il linguaggi…

Tascam DR-05 registratore digitale per tutti

Diverso tempo fa ho acquistato il registratore digitale Tascam DR-05 e, ora, dopo diversi mesi di utilizzo, posso dire la mia a proposito.

Si tratta di un ottimo registratore digitale con microfono stereo che permette di ottenere registrazioni di ottima qualitaà anche in ambienti non perfetti dal punto di vista acustico.

Interessante la possibilità di utilizzare un cavalletto di piccole dimensioni come HAMA Mini treppiede o Mini Cavalletto Universale per tenere il microfono sollevato dal tavolo in fase di registrazione grazie allàattacco universale per macchina fotografica che il microfono ha nella parte inferiore.

Da segnalare anche il menu’ ben fatto e la possibilita’ di utilizzare una scheda SD esterna per memorizzare i file audio. Anche a livello di consumo batterie non e’ niente male. Consiglio l’uso delle alcaline non ricaricabili.

Il mio utilizzo e’ stato prettamente di registrazione di podcast vocali (no musica) ma le recensioni confermano che se la cava egregiamente con la mu…