[C++] Fibonacci tramite prodotto di matrici

[andrea]

Allora appunto stavo cercando di risolvere il problema di fibonacci tramite l'uso del metodo dei quadrati ripetuti applicato alle matrici, il problema e' che dopo aver scritto il mio bell codice che qui allego:

******************************************************

#include <iostream>

using namespace std;

unsigned long Fibonacci6(unsigned long [][2], int);
void PotenzaMatrice(unsigned long[][2], int);
void Prodotto(unsigned long [][2], unsigned long[][2]);

unsigned long J[2][2] = {{1,1},{1,0}};
unsigned long app[2][2];

int main() {

int n;
unsigned long nesimo;
unsigned long M[2][2]={{1,0},{0,1}};

cout << "Inserisci l'n-esimo numero di fibonacci che vuoi calcolare: ";
cin >> n;
nesimo = Fibonacci6(M,n);
cout << "L'n-esimo numero di fibonacci e': " << nesimo << endl;

system("pause");
return 0;
}

unsigned long Fibonacci6(unsigned long M[][2], int n) {
PotenzaMatrice(M,n-1);
return M[0][0];
}

void PotenzaMatrice(unsigned long M[][2], int n) {
if (n > 1) {
PotenzaMatrice(M,n/2);
Prodotto(M,M);
M = app;
}
if ((n%2) == 1) {
Prodotto(M,J);
M = app;
}
}

void Prodotto(unsigned long Mat1[][2], unsigned long Mat2[][2]) {
for (int i=1; i>=2; i++)
for (int j=1; j>=2; j++) {
app[i][j] = 0;
for (int k=1; k>=2; k++) {
app[i][j]=app[i][j]+Mat1[i][k]*Mat2[k][j];
}
}
}


******************************************************

non mi funziona una mazza :( mi da sempre uno per qualsiasi numero voglio calcolare che sia il 3 il 7 o che. Se qualcuno e' cosi gentile di dargli un occhiata. Purtroppo oltre tutto non so perche' non mi funziona il debugger del dev-c++ :muro:

Poi un' altra domanda che non ha che vedere direttamente con il codice...teoricamente questo dovrebbe essere l'algoritmo piu' veloce per trovare i numeri di fibonacci o almeno piu' veloce rispetto all'algoritmo ricorsivo ed a quello iterativo...ma perche'?nella moltiplicazione di matrici non perdo molto piu' tempo rispetto soprattutto ad un algoritmo iterativo fatto in questo modo:

algoritmo fibonacci(intero n) -> intero
a <- 1; b <- 1;
for i=3 to n do
c <- a + b;
a <- b; b <- c;
return b

[SnakePlissken]

Se è la velocità che ti interessa, avevo trovato questa soluzione:

double fibo(register double n) {
register double F[3] = {1.0, 1.0, 0.0};
register long long i;

if ((n < 0) || (fmod(n, 1.0))
return(-1);
if (n <= 2)
return(1);

for (i=2; i<(long long)n; i++)
F[i%3] = F[(i+4)%3] + F[(i+5)%3];

return(F[(i-1)%3]);
}

Ciao!

[andrea]

Intanto grazie per la risposta, dando un occhiata al codice da te scritto, mi sono accorto che in finale non e' altro che l'algoritmo in pseudocodice che avevo scritto prima trasposto in c ed ottimizzato naturalmente. Il fatto e' che quel tipo di algoritmo andandolo a studiare non e' piu' veloce rispetto quello con le matrici...visto che come tempo di esecuzione e' nell'ordine O(n) mentre quello con le matrici e di ordine O(log(N))! Poi naturalmente potrei sbagliare lo studio degli algoritmi pero' sinceramente non mi sembra.

[Banus]

Complimenti a SnakePlissken per il codice molto compatto ed elegante :D

Un algoritmo più efficiente di quello non lo conosco. In che cosa consiste il metodo dei quadrati ripetuti?

[andrea]

Originariamente inviato da Banus
Complimenti a SnakePlissken per il codice molto compatto ed elegante :D

Si per il codice in se e' perfetto :)



Un algoritmo più efficiente di quello non lo conosco. In che cosa consiste il metodo dei quadrati ripetuti?

L'idea di base e' la seguente: per calcolare ad esempio 3^8 si puo' moltiplicare 3 per 8 volte (3*3*3*3*3*3*3*3=6561) oppure ricorrere a quadrati ripetuti (ovvero, 3^2=9 9^2=3^4=81 81^2=3^8=6561). Con il metodo dei quadrati ripetuti si effettua un numero molto minore di moltiplicazioni. Con un po' di attenzione lo stesso metodo si puo' applicare a esponenti che non sono potenze di due e puo' anche essere adattato appunto a matrici.

nel seguente pseudo codice appunto e' applicato al'uso di matrici, per effettuare la serie di fibonacci:


algoritmo fib(int n) -> n
M <- [1,0;0,1] (matrice identita')
PotenzaDiMatrice(M,N-1)
return M[0][0]

procedura PotenzaDiMatrice(matrice M, int n/2)
if ( n > 1) then
PotenzaDiMatrice(M,n/2)
M <- M * M

if ( n e' dispari) then M <- M * [1,1;1,0]


In questo algoritmo tutto il tempo e' speso nella procedura potenza di matrice che calcola ricorsivamente la potenza n-esima della matrice M. Poi andando a studiare la relazione di ricorrenza dell'algoritmo appunto si arriva al risultato di O(log(n)) che appunto e' minore dell' O(n) che uno troverebbe studiando l'agoritmo del codice postato prima(Poi puo' darsi che ho sbagliato a studiarlo ma non mi sembra) quindi risulta che l'algoritmo delle matrice per trovare la serie di fibonacci e' piu' veloce di quello dell'algoritmo che usa il codice di SnakePlisSken.

[pela]

esiste anche una formula per calcolarli, non so quanto sia efficiente (ci sono le potenze):
Fn = 1/sqrt(5)*(((1+sqrt(5))/2)^(n+1)-((1-sqrt(5))/2)^(n+1))
le espressioni con la radice possono essere anche precalcolate, per non influire sulla velocità di esecuzione

[andrea]

Originariamente inviato da pela
esiste anche una formula per calcolarli, non so quanto sia efficiente (ci sono le potenze):
Fn = 1/sqrt(5)*(((1+sqrt(5))/2)^(n+1)-((1-sqrt(5))/2)^(n+1))
le espressioni con la radice possono essere anche precalcolate, per non influire sulla velocità di esecuzione

Si la formula tramite la sezione aurea 1.618 appunto (1+sqrt(5))/2 pero' non conviene sopratutto poi per il problema degli arrotondamenti usando un accuratezza di tre cifre decimali appunto 1.618 gia' al 18° numero di fibonacci arrotondando si ottiene un numero non corretto.

[Banus]

Le formule approssimate ovviamente hanno complessità costante ma si paga con poca accuratezza... O(log(n)) mi pare un risultato soddisfacente per la soluzione esatta :D

Ho controllato il codice del primo post e ho visto che è sbagliata la funzione che calcola il prodotto fra matrici:

for (int i=1; i>=2; i++)

se ci ragioni un attimo la condizione non è mai vera. Forse volevi scrivere:

for (int i=1; i<=2; i++)

ma dal momento che le matrici sono di dimensione fissa e piccole (2x2) ti conviene codificarle con un vettore scrivendo esplicitamente la formula del prodotto per ciascun elemento. Dovrebbe essere anche più veloce, dal momento che non ha indici da incrementare.
Il resto del programma mi sembra corretto.

[andrea]

Originariamente inviato da Banus

Ho controllato il codice del primo post e ho visto che è sbagliata la funzione che calcola il prodotto fra matrici:

for (int i=1; i>=2; i++)

se ci ragioni un attimo la condizione non è mai vire. Forse volevi scrivere:

for (int i=1; i<=2; i++)



:ops: ehm piccola svista :D


ma dal momento che le matrici sono di dimensione fissa e piccole (2x2) ti conviene codificarle con un vettore scrivendo esplicitamente la formula del prodotto per ciascun elemento. Dovrebbe essere anche più veloce, dal momento che non ha indici da incrementare.
Il resto del programma mi sembra corretto.

Si concordo, nel modo in cui lo ho fatto mi era risultato piu' veloce scriverlo :D ma per una matrice 2x2 non ha molto senso :)

[SnakePlissken]

Originariamente inviato da andrea
Purtroppo oltre tutto non so perche' non mi funziona il debugger del dev-c++ :muro:
Probabilmente hai la beta 5 che è ancora in fase di sviluppo.


Poi un' altra domanda che non ha che vedere direttamente con il codice...teoricamente questo dovrebbe essere l'algoritmo piu' veloce per trovare i numeri di fibonacci o almeno piu' veloce rispetto all'algoritmo ricorsivo ed a quello iterativo...ma perche'?nella moltiplicazione di matrici non perdo molto piu' tempo rispetto soprattutto ad un algoritmo iterativo fatto in questo modo:

algoritmo fibonacci(intero n) -> intero
a <- 1; b <- 1;
for i=3 to n do
c <- a + b;
a <- b; b <- c;
return b
Oops... è vero, questo e il mio sono la stessa cosa. Scusa ma avevo fatto di fretta senza leggere bene il tuo messaggio :confused:.
Anzi devo riconoscere che il tuo, tradotto "letteralmente", è pure più veloce del mio perché non fa uso di matrici e si risparmia tutte quelle operazioni per determinare gli indici :muro:
Proprio per questo non capisco come quello che usa la moltiplicazione delle matrici (che ammetto che non conoscevo) possa essere più veloce. Quello che hai codificato in pseudo-codice si riduce ad operazioni di addizione e assegnamento e sarà per questo senz'altro più veloce. Tutto questo credo sia proprio dal punto di vista operativo, in termini di velocità oggettiva.
Purtroppo non ho un compilatore montato su questo PC. Prova a fare un confronto "sperimentale" tra le prestazione tra le due versioni e facci sapere. Anche quello mio comunque (che a questo punto sembra essere la meno efficiente delle tre... :muro: :muro: ) mi sembra che riuscisse nei calcoli con una certa facilità...

esiste anche una formula per calcolarli, non so quanto sia efficiente (ci sono le potenze):

Fn = 1/sqrt(5)*(((1+sqrt(5))/2)^(n+1)-((1-sqrt(5))/2)^(n+1))

le espressioni con la radice possono essere anche precalcolate, per non influire sulla velocità di esecuzione
In fondo precalcolando le operazioni, come avete già osservato, la precisione scende di molto, e forse anche ad una precisione di 15 cifre propria dei double il risultato non sarebbe del tutto affidabile. Ma non era elevato ad n e non a (n+1)?


Ma poi cos'è tutta sta mania di velocità :D:D ?!?
Il mio calcola il massimo numero calcolabile che rientra nei double (fibo(1476)) in un batter d'occhio!
(che rozzezza di spirito sto ragionamento...:eek: ! perdono!)
Voglio dire che comunque a livello operativo le differenze sono quasi impercettibili tra queste versioni.

Ciauz!

[Banus]

Il metodo con le matrici è sicuramente più veloce del metodo iterativo perchè log(n) cresce molto più lentamente.

http://en.wikipedia.org/wiki/Fibonacci_number

Più che la velocità si cerca l'accuratezza nei calcoli. L'algoritmo con le matrici trova il risultato in meno passaggi.