Newsgroup: it.scienza.informatica
Titolo: Efficienza funzione Fibonacci in ML

Mi sto avvicinando alla programmazione funzionale con ML attraverso il
suo dialetto OCaML.
Tra gli esercizi basilari, ho pensato di scrivere la funzione che
restituisce l'n-esimo numero di Fibonacci.
let rec fib = function
    0 -> 1
  | 1 -> 1
  | n -> fib(n-1) + fib(n-2)
questo ben noto algoritmo a complessità esponenziale chiama fib(n-1) e
fib(n-2); bene, sotto C è ovviamente più conveniente scrivere una
funzione iterativa, e la stessa cosa credo andrebbe fatta in ML, al fine
di evitare tempi di esecuzione biblici; in quest'ultimo caso, dovrei
usare variabili di riferimento, oppure i costrutti di controllo
imperativi di OCaML, ma tali soluzioni non rappresentano una
contraddizione, dato che sto usando un linguaggio funzionale? Il libro
di testo che sto consultando dice che dal punto di vista dello stile
funzionale esse vanno considerate aberrazioni a cui ricorrere solo dove
necessario o quando portano a un notevole incremento di efficienza. Con
Fibonacci il notevole incremento di efficienza indubbiamente c'è, quindi
mi conviene comunque usare costrutti imperativi... beh, e allora dove
sarebbe il vantaggio della programmazione funzionale?
D'altra parte, sullo stesso libro leggo che un'esecuzione efficiente può
essere ottenuta con una ricorsione di coda (tail recursion), in modo da
avere una sorta di iterazione; ok, ma mi sembra che con Fibonacci non si
possa ricorrere alla tail recursion.
Non è assolutamente mia intenzione sollevare un flame, ma essendo un
principiante vorrei che qualcuno mi chiarisse meglio la situazione.
Il secondo problema che mi sono posto, è sapere qual è il numero intero
massimo. Con Fibonacci fa sempre comodo saperlo, per evitare di ottenere
risultati sballati. Con il C ho la costante INT_MAX di limits.h, sotto
OCaML (o altri ML)? In altre parole si può conoscere il numero di bit
con cui viene rappresentato un int, o con la programmazione funzionale
anche questo è un concetto che devo dimenticarmi?

Ciao,
non so programmare in ML, ma proprio ora ho scritto dei predicati in prolog
per il calcolo dei numeri di Fibonacci.
Forse la mia implementazione ti può essere d'aiuto.
/*Versione 1 (complessità esponenziale) */
fibonacci(0, 0).
fibonacci(1, 1).
fibonacci(N, Res) :-
    N >= 2,
    A is N - 1,
    B is N - 2,
    fibonacci(A, RA),
    fibonacci(B, RB),
    Res is RA + RB.
/*Versione 2 (complessità lineare) */
fibonacci(0, 0).
fibonacci(1, 1).
fibonacci(N, Res) :-
    N >= 2,
    fibonacci_iterative(N, 2, 1, 1, Res).
fibonacci_iterative(N, I, F1, F2, F) :-
    I < N,
    SUM is F1 + F2,
    NI is I + 1,
    fibonacci_iterative(N, NI, SUM, F1, F).
fibonacci_iterative(N, I, F1, F2, F) :-
    I is N,
    F is F1.
L'ultima versione in C dovrebbe essere una cosa del genere:
unsigned int fibonacci(unsigned int n) {
  if (n < 2)
    return n;
  else
    return fibonacci_r(n, 2, 1, 1);
}
unsigned int fibonacci_r(unsigned int n, unsigned int i, unsigned int f1,
unsigned int f2) {
  if (i < n)
    return fibonacci_r(n, i + 1, f1 + f2, f1);
  else
    return f1;
}
Come vedi non ho utilizzato variabili ne istruzioni di controllo di flusso
diverse dalla chiamata a funzione.
Il codice C però non l'ho testato, quindi prendilo con le pinze. :)
Questa implementazione dovrebbe avere complessità O(n) sia in tempo che in
spazio, a differenza di una normale implementazione iterativa che è O(n) in
tempo e costante in spazio.
Spero di esserti stato utile, ciao.

   | n -> fib(n-1) + fib(n-2)
Scusa ma la definizione matematica di numero di fibonacci non è:
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)
?

 ?
No, fib(0) = 1.

 No, fib(0) = 1.
Beh sono la stessa successione ma una traslata di un posto rispetto
all'altra.
Benedetti informatici :))))
--
_-==.==-_*_-==.==-_
  _    _   __    _   " Ogni sistema ha le sue leggi :
 |_)_ |_) (_  _ |_)     alcune possono essere eluse
 | (_|| \o__)(/_| \    altre...infrante " (Morpheus)
 (Giacomo Bellucci)
 
PaR._IL_BIAN...@libero.it
     _________
    /ficm code\          Per rispondermi togliete
    \ [Hx23B] /        _IL_BIANCONIGLIO_ dall'email
     ¯¯¯¯¯¯¯¯¯

 Benedetti informatici :))))
Volevo scriverlo ma non volevo apparire troppo saputello... :-p

 Benedetti informatici :))))
Io non la farei cosě semplice.
Se sei abituato a ragionare "all'infinto" per te sono la stessa cosa, ma in
generale non č cosě.

Benedetti informatici :))))
Questa facciamo finta di non averla sentita senno' finiamo in un flame
ricorsivo di complessità superiore di qualche ordine a quella di
Fibonacci :-p

 qual è il principio della successione?
1, vai tranquillo.