[C++] Dubbio teologico: la serie di fibonacci

[Ippo343]

Salve a tutti!

Credo di aver scritto un programma sbagliato. La mia teoria per spiegare quello che vedo è che non so abbastanza dei compilatori per capire cosa succede davvero. Non credo insomma che il valore venga davvero calcolato ogni volta, ma che ci sia una sorta di scorciatoia da qualche parte che non vedo.

Io ho scritto per caso questo codice, ancora due anni fa, per calcolare la sequenza di fibonacci. (Non era proprio identico perchè era in pascal, oggi l'ho portato a C++)

char index = 42;
long a = 1;
long b = 0;

for (char i = 1; i < index; a += b, b = a - b, i++);

cout << a;

Questo come alternativa al tradizionale metodo ricorsivo in cui si ha una cosa tipo

if (index < 2) return 1;
else return fib(index - 1) + fib(index - 2);

Il secondo metodo, quello ricorsivo, è basato sulla definizione, ma se ragionate un filo su quello che ho scritto io, anche il mio fa le stesse cose. Il punto è che il mio codice risulta alcune centinaia di volte più veloce!!!

Provate per credere! per esempio, calcolate il 42 esimo numero usando entrambi i codici. E' così veloce che mi rifiuto di credere che funzioni davvero! Cioè no è impossibile, ci deve essere qualcosa che non ho considerato!!!

Qua sotto c'è il listato del programma, già pronto da compilare... Oo

#include <iostream>

using namespace std;

unsigned long int fib(char index);
unsigned long int fastfib(char index);

int main()
{
    char ind = 42;

    cout << "fastfib: ";
    cout << fastfib(ind) << endl;
    cout << "fib: ";
    cout << fib(ind) << endl;

    return 0;
}

unsigned long int fib(char index)
{
    if (index == 1 || index == 2)
        return 1;
    else
        return (fib(index-1) + fib(index-2));
}

unsigned long int fastfib(char index)
{
    unsigned long int a, b;
    a = 1;
    b =0;

    for (char i = 1; i < index; a+=b, b=a-b, i++);

    return a;
}

:master:

[MItaly]

Nulla di strano, la ricorsione è notoriamente più lenta dell'iterazione, visto che la chiamata a funzione ha un certo overhead; per ogni chiamata alla funzione ci sono una serie di operazioni di inizializzazione dello stack (che, su codice effettivo da eseguire così ridotto si sente eccome) e i dati vengono passati tramite lo stack (visto che sono parametri) e non possono essere quindi mantenuti nei registri (cosa che invece avviene nella versione iterativa). Tra l'altro la versione iterativa in questione è rallentata ulteriormente dal continuo cast char=>unsigned int dovuto al fatto che il parametro e il tipo restituito sono di tipi differenti.

[oregon]

Di tutto cio' mi sfugge il senso del "teologico" ...

[Ippo343]

Non c'è un senso per il teologico, da solo un'idea di "cosa grossa" che trovo divertente ^^

Ok, che la versione ricorsiva ha un sacco di overhead lo sapevo e lo immaginavo, ma è possibile che sia COSI' tanto?

Sul pc dove sono ora, la versione ricorsiva per il 50esimo numero è stata circa 1000 volte più lenta di quella iterativa... non è che mi sembra tanto il tempo di quella ricorsiva, mi sembra troppo poco il tempo di quella iterativa!

[YuYevon]

No aspettate qui non c'entra tanto l'overhead dovuto alla ricorsione... se per calcolare il 45° numero della successione di Fibonacci si impiegano 40 secondi con la soluzione ricorsiva mentre con quella iterativa un tempo che nemmeno è apprezzabile dall'essere umano, è chiaro che c'è qualcosa che non va a livello di algoritmo... e infatti è così.

L'algoritmo ricorsivo che ha postato Ippo343 ha una complessità asintotica di tempo esponenziale, con base (si può dimostrare) pari alla sezione aurea, quindi è T(n) = O(1.6^n), dove n è il numero della successione che vogliamo calcolare. Da dove viene fuori questa complessità esponenziale, cioè il fatto che l'algoritmo impieghi così tanto tempo? Sta in questo: vengono ripetuti troppe volte gli stessi calcoli! Mi spiego con un esempio:

supponiamo di voler calcolare fib(5) con quell'algoritmo ricorsivo: per come è stato scritto, fib(5) si "biforca" in fib(4) e fib(3), ma poi ché succede? fib(4) autoattiva fib(3) e fib(2), cioè abbiamo di nuovo una chiamata a fib(3) che già avevamo avuto prima... e la stessa cosa... fib(3) della prima autoattivazione da luogo a fib(2) (un'altra volta!) e fib(1)... e questo si ripete fino al caso base, cioè quando appunto abbiamo fib(1) e fib(0) che sono immediatamente calcolabili.

E' chiaro che se abbiamo fib(5) le chiamate ricorsive ripetute sono poche, ma se proviamo a calcolare fib(45) le cose cambiano...

Insomma basta vedere l'immagine di Wikipedia



per rendersi conto che fib(3) viene calcolato due volte, fib(2) 3 volte e fib(1) 5 volte... e inutilmente, perché se io ho già calcolato una cosa una volta perché mai farlo di nuovo?

A questo punto interviene la programmazione dinamica. Quell'algoritmo ricorsivo potrebbe infatti essere riscritto così (già compilabile ed eseguibile):

#include <stdio.h>
#include <stdlib.h>

double calcolati[100];/*dichiarazione globale di un array statico di 100 elementi
                        per la memorizzazione delle chiamate alle function       */

double fibonacci(short n)
{
  if ( n < 0 ) {
     /*L'ordinale della successione non può essere negativo*/
     exit(1);
  }

  if ( n <= 1 )
     return (double)n;

  if ( calcolati[n] )
     return calcolati[n];
  else {
     calcolati[n] = fibonacci(n-1) + fibonacci(n-2);
     return calcolati[n];
  }
  /*Anziché restituire direttamente fibonacci(n-1)+fibonacci(n-2), la function
    prima salva le due chiamate nell'n-esimo elemento dell'array e poi le
    restituisce (return calcolati[n], ossia return fibonacci(n-1)+fibonacci(n-2)*/
}

int main(void)
{
  short n, i;
 
  for ( i = 0; i < n; i++ ) { /* azzeramento esplicito di tutti gli elementi dell'array */
     calcolati[i] = 0;
  }

  printf("Immettere l'ordinale dell'elemento della successione di Fibonacci\n"
         "che si vuole calcolare: ");

  scanf("%hd", &n);

  printf("Elemento della successione di Fibonacci n. %hd: %.lf", n, fibonacci(n));

  return 0;
}

e in questo modo anche fib(45) viene calcolato in un tempo così piccolo da non essere apprezzato... questo perché apportando la modifica dell'array che "salva" i valori già calcolati, l'algoritmo diventa a complessità lineare O(n), esattamente la stessa dell'algoritmo iterativo...

In un certo senso, c'è un po' di teologia in tutto questo

[oregon]

Originariamente inviato da Ippo343
Non c'è un senso per il teologico, da solo un'idea di "cosa grossa" che trovo divertente ^^

Ah ... è come se avessi intitolato il tuo thread:

Grosso dubbio: ...

Ho capito.

[Ippo343]

@ YuYevon:

spiegazione fantastica però mi pare ancora di capire che il mio algoritmo sia giusto. Questo continua a lasciarmi perplesso ahah

@ Oregon:

Si esatto, sono io un tipo dall'umorismo abbastanza curioso :P

[YuYevon]

Originariamente inviato da Ippo343
@ YuYevon:

spiegazione fantastica però mi pare ancora di capire che il mio algoritmo sia giusto. Questo continua a lasciarmi perplesso ahah

Cosa ti lascia perplesso? Sia la versione iterativa che quella ricorsiva dell'algoritmo sono corrette, in particolare per quella ricorsiva c'è da fare la distinzione tra quella con l'approccio di programmazione dinamica (che impiega un tempo O(n) proprio come l'algoritmo iterativo, e infatti l'output si ottiene nello stesso tempo...) e quello senza programmazione dinamica, che invece impiega un tempo elevatissimo perché è a complessità esponenziale, come dicevo. Tolte queste considerazioni sui tempi, però, gli algoritmi sono tutti assolutamente corretti... non è raro avere versioni iterative e ricorsive entrambe efficienti per uno stesso algoritmo eh... anche se ovviamente (come ti suggeriva MItaly, anche se qui la questione era diversa) la ricorsione richiede un overhead maggiore rispetto alla programmazione iterativa, sebbene a vantaggio - spesso - di una maggiore concisione ed eleganza (e magari anche chiarezza...)

Poi è ovvio che se proprio vogliamo ricorrere alla versione ricorsiva ci serviremo della programmazione dinamica, altrimenti rischiamo di far piantare il computer anche per calcolare numeri della successione di Fibonacci nell'ordine delle prime decine.. e se consideri che a volte può capitare di andare ben oltre il 40-esimo numero (in passato a me è capitato di arrivare a calcolare i numeri di Fibonacci fino al 100000-esimo e oltre per alcuni problemi del progetto Eulero, ovviamente ricorrendo alla NTL per la gestione dei grandi numeri) direi proprio che quella soluzione ricorsiva semplice sia da scartare, e con ignominia anche :°D

[Ippo343]

Si si lo so che è corretto, sono solo stupito perchè l'ho scritto due anni fa, in terza superiore, così di botto senza nemmeno rifletterci su. L'ho inventato più che altro di fortuna in circa 10 minuti. Quello che mi stupisce è sia che funzioni, sia che funzioni così bene :P