Successione di Fibonacci: algoritmi e prestazioni in c# #algoritmi #fibonacci #prestazioni #math

Ok, stavolta niente economia o politica e torniamo un po’ alla sana informatica.

Girasole [Fonte: Wikipedia; Autore: Asio otus]

Girasole [Fonte: Wikipedia; Autore: Asio otus]

Ultimamente, non so il motivo, mi ha preso la mania di Fibonacci. Senza stare a farla troppo lunga (per quello c’è Wikipedia), Fibonacci era un matematico pisano vissuto a cavallo tra il XII ed il  XIII secolo e si  è fatto una bella pensata matematica inventando (anche se preferisco pensare alle invenzioni matematiche come a delle scoperte) una successione di numeri che prende il suo nome.

Per chi non è amante della matematica e per farla sempre breve, una successione di numeri è semplicemente una sequenza di numeri. Un po’ come le classifiche della MotoGP o della Formula1. In prima posizione c’è un pilota, in seconda un altro e così via, solo che, al posto dei piloti, ci sono dei numeri (potreste pensarli come se fossero il numero del pilota…)

La successione di Fibonacci

Bene, la successione di Fibonacci è molto carina e chiunque sappia fare una semplice addizione può mettersi lì e, con tanta pazienza, iniziare a fare un po’ di conti. Funziona in maniera semplice: dati due numeri, il terzo è pari alla somma dei due precedenti. Più facile farlo vedere. Prendiamo 0 e 1 come primi due numeri e vediamo cos’accade:

0 1 -> 0+1 = 1 –> 1 1 -> 1+1 = 2 –> 1 2 -> 1+2 = 3 ecc.

La successione di Fibonacci, pertanto, comincia in questo modo: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Ora, la cosa può sembrare un semplice giochino matematico per gente che non ha nulla da fare tutto il giorno. Ok è vero, può anche esserlo.

Come vi ho detto, però, la matematica è una scienza che scopre e che non inventa (a mio avviso). A quella successione numerica possiamo associare tanti fenomeni che accadono in natura. Pensiamo alla distribuzione delle foglie sulle piante monocotiledoni (se non ricordo male), o ad una spirale o, in qualunque caso, al rapporto aureo (1,618033 e così via). Il rapporto tra due numeri vicini della successione di Fibonacci tende più o meno alla sezione aurea (il rapporto alterna una volta maggiore, una volta minore e si affina sempre più alla sezione aurea).

In tutto questo la successione di Fibonacci possiamo scriverla, più o meno, così:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) con n>1

Un po’ di programmazione: viva l’informatica!!!

DISCLAIMER: Se non sei sufficientemente nerd o curioso, non proseguire! Qui comincia la parte pallosa del post 😀

Insomma, in questo periodo mi sono un po’ lanciato in questa cosa e, pertanto, voglio condividerla sul blog. Mi sono lanciato così tanto che l’ho sfruttata per cominciare a fare un po’ di prove in C# (linguaggio di programmazione Microsoft) per iniziare ad usare le Windows Form (in pratica fare i programmi per desktop con questo linguaggio).

Visto che l'”Hello World” non mi piaceva granché, ho pensato di realizzare un paio di TextBox con un pulsante di calcolo ed un autoaggiornamento dinamico. Cosa meglio di un buon Fibonacci per testare anche tempi e simili?

Beh, del progetto non credo interessi granché, ma degli esiti delle tempistiche penso di sì.

Ho realizzato due funzioni per calcolare F(n): una iterativa, l’altra ricorsiva.

I concetti di iterazione e di ricorsività sono molto noti in informatica e, soprattutto l’iterazione, sono la base di una quantità di azioni che fate sul pc tutti i giorni, che nemmeno vi immaginate. L’iterazione è un modo tecnico per definire un ciclo. L’informatica si basa sui cicli… Prendiamo una richiesta ajax. Avete presente che quando siete su Facebook la pagina non diventa bianca tutte le volte che si aggiorna da sola, ma “semplicemente fa comparire” il nuovo messaggio o il nuovo status…? Ecco, li dietro c’è un ciclo che, ogni tot millisecondi, richiede informazioni sullo status.

Per dire qualcosa di più semplice possiamo pensare a come possiamo tradurre una semplice moltiplicazione: 2×4 è come sommare 2 per quattro volte, no? 2 x 4 = 2 + 2 + 2 + 2. In pratica è un ciclo dove alla domanda: cosa faccio? La risposta è: somma 2. Quante volte? 4 volte.

Il concetto di ricorsività è leggermente più complesso, ma si può ricondurre, anch’esso, ad un ciclo. Una funzione ricorsiva è una funzione che richiama se stessa fintantoché non vengono raggiunte le condizioni di terminazione (il tipico problema universitario è la Torre di Hanoi…).

Beh, volendo sperimentare sul campo le differenze di prestazioni tra ricorsiva e iterativa (in modalità debug) ho scritto le funzioni che mi calcolino il numero della successione di Fibonacci all’ennesimo passo, laddove n è un input dell’utente >= 1;

A titolo “accademico” riporto le due funzioni, Fibonacci per la Fibonacci ricorsiva, FibonacciNonRec per Fibonacci iterativa:

      public UInt64 Fibonacci(Int64 c)
      {
          UInt64 n = 0;
          n = (c > 2) ? Fibonacci(c - 1) + Fibonacci(c - 2) : n + 1;
          return n;
      }

      public UInt64 FibonacciNonRec(Int64 c)
      {
          UInt64 a = 0;
          UInt64 b = 1;
          UInt64 temp = a;
          for (int i = 0; i < c; i++)
          {
              temp = a;
              a = b;
              b = temp + b;
          }
          return a;
      }

Si nota facilmente come la seconda sia più lunga da scrivere in termini di programmazione e come la prima sia effettivamente molto più elegante e compatta; la differenza di prestazioni tra le due, però, è notevole già da F(40) (che per vostra curiosità fa 102334155): FibonacciNonRec = 0ms | Fibonacci = 3920,0055ms.

Il motivo, senza stare ad entrare nei dettagli tecnici, è da ricondursi a come viene occupata la memoria in cui risiedono le informazioni di esecuzione (tecnicamente dipende da come viene allocato e gestito lo stack).

Per i curiosi specifico che nella Fibonacci è stato utilizzato l’operatore ternario per l’assegnazione: valore = (condizione) ? operazione_se_condizione_vera : operazione_se_condizione_falsa. In pratica è un if..else in linea.

Nota ulteriormente tecnica per chi è nerd e proprio non ha nulla da fare

Il code timing (calcolo del tempo di esecuzione di un codice) l’ho fatto semplice semplice:

DateTime startTime = DateTime.Now;
Console.WriteLine("Start: {0}", startTime);
--la funzione l'ho messa in questo punto
DateTime stopTime = DateTime.Now;
Console.WriteLine("Stop: {0}", stopTime);
TimeSpan elapsedTime = stopTime - startTime;
Console.WriteLine("ms:" + elapsedTime.TotalMilliseconds);
Console.WriteLine("----------------------------------------------------");
Annunci

4 Pensieri su &Idquo;Successione di Fibonacci: algoritmi e prestazioni in c# #algoritmi #fibonacci #prestazioni #math

  1. Reblogged this on Racconti e voli pindarici di un emerito D… and commented:

    Rebloggo qui un post di sipronunciaaigor, che gioca con la matematica. A dire il vero, la parte più informatica io l’ho persa un po’ via 😉 … ma magari no. Ad ogni modo, una cosa interessante è l’esempio usato per far capire in modo semplice cosa sia una sequenza di numeri: è probabile che la riprenderò quando, fra un po’, parlerò di una cosa simile, seppure più legata alle capacità del cervello. Per ora fate “due calcoli” : )
    PS: anche per il discorso “sezione aurea”, c’è wikipedia.

  2. Pingback: Successione di Fibonacci: complessità algoritmica, frattali e natura #fractals #fibonacci #math « sipronunciaaigor

  3. Pingback: Caldo e approfondimenti #estate2012 #nerone #caldo « sipronunciaaigor

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...