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

MVP Reconnect …… ovvero quando entri nella “famigghia” resti sempre nella “famigghia”!!!

Ma di che “famigghia” stiamo parlando!!!!

Fermi tutti, non si tratta di robe strane o sette segrete o affari malavitosi….stiamo parlando della grande famiglia dei Microsoft MVP.

Per chi non sapesse cosa sono i Microsoft MVP, vi consiglio di fare un giro sul sito ufficiale del programma (link), ma, volendolo spiegare in pochisime parole, si tratta di un riconoscimento che Microsoft da a persone che si distinguono per il loro impegno, aiutando gli altri ad ottenere il massimo grazie alle tecnologie Microsoft. Si tratta di persone, non dipendenti Microsoft, che mettono la loro passione, il loro tempo, la loro buona volontà per la divulgazione e la condivisione della conoscenza. Non necessariamente (come qualcuno erroneamente sostiene, evidentemente non conoscendo le basi del programma) si tratta di professionisti nel termine letterale del termine ma si tratta comunque di un gruppo di persone che sacrifica un pò del suo tempo (e, a volte, vi assicuro neanche pò!!!) per la sua passione.

Pe…

Nuova versione del Band SDK

E’ di ieri l’annuncio del rilascio della nuova versione dell’SDK per il Microsoft Band.
Si tratta della versione 1.3.10417 (la precedente e, prima della serie, era la 1.3.10219 preview).
Maggiori informazioni, download dell’SDK per le tre piattaforme Windows Phone, iOS e Android all’indirizzo http://developer.microsoftband.com/.
Allo stesso indirizzo potrete trovare anche la documentazione.
Nei mesi scorsi mi sono gia’ occupato della precedente versione e questi sono i post che ne parlano:
Microsoft Band SDK Preview - First LookMicrosoft Band SDK Preview - ”Hello Band”Microsoft Band SDK Preview - Accesso ai sensoriMicrosoft Band SDK Preview - TileMicrosoft Band SDK Preview - NotificheMicrosoft Band SDK Preview - Personalizzazione
Gli argomenti trattati e il codice proposto dovrebbe, ad una prima lettura delle nuove funzionalita’ inserite, essere ancora valido e funzionante ma nei prossimi giorni prendero’ in esame tutti gli argomenti dei precedenti post e vedremo cosa cambia e cosa e’ …

Template di progetto per sviluppare applicazioni WPF con Intel® RealSense™

E’ disponibile, nella gallery di Visual Studio, la prima versione del mio template di progetto per applicazioni WPF scritte in C# che permette di realizzare applicazioni con l’SDK di Intel® RealSense™.Il template si può scaricare direttamente all’interno Visual Studio utilizzando il tool “Extensions and Updates”oppure all’indirizzo https://visualstudiogallery.msdn.microsoft.com/1c36ecfd-8c00-4aee-b20c-a1726ab6424dIl template esegue le seguenti operazioni per voi:Aggiunge la reference all’assembly libpxcclr.cs.dll (nelle due distinte versioni per x86 e x64);Aggiunge lo script di post build per copiare la libreria libpxccpp2c.dll dalla cartella dell’SDK alla cartella bin del vostro progetto.Una volta creato il progetto dovete rimuovere la configurazione di compilazione AnyCPU (che non ha più senso) dalla vostra solution e sarete pronti per sviluppare con Intel® RealSense™.Ovviamente dovete installare l’SDK che potete scaricare all’indirizzo https://software.intel.com/en-us/intel-realsen…