Como calcular fibonacci em O(log n)?

[leigan]

Boa noite, o que quero saber é o seguinte, preciso calcular o n-ésimo fibonacci em log n, tem a dica de usar uma matriz, mas não sei como usa-la,

quem souber e puder ajudar agradeço.

a matriz 2x2:

1 1

1 0

abraço

[Binder]

Opa, pelo o que entendi você gostaria de declarar uma matriz?

Se for isso, declare assim:

int main() {

     int  i,j, m[2][2];

}

Onde foi criado uma matriz 2x2, duas linhas e duas colunas. as variaveis "i" e "j" são para você percorrer a matriz, usei esses nomes, mas fique a vontade de declarar como você achar melhor. Não esqueça que para percorrer a matriz você irá precisar de 2 for.

for(i=0;i<2;i++){
      for(j=0;j<2;j++){
            //bloco de codigo
       }
 }

Agora se precisar atribuir os valores conforme você postou faça assim:

m[0][0] = 1
m[0][1] = 1
m[1][0] = 1
m[1][1] = 0

Editado Fevereiro 8, 2012 por Binder

[leigan]

não não, minha duvida é como usar a matriz para achar o n-ésimo numero de fibonacci

bom consegui chegar até esse codigo, mas ele ainda não devolve o n-esimo, a ideia é fazer elevar a matriz² log n vezes,

Então a pergunta é, o que falta nesse codigo para ele dar o resultado do n-esimo?

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

void imprime(int mz[2][2]){
     for(int j = 0; j < 2; j++){
         for(int k = 0; k < 2; k++){
            printf("%d ",mz[j][k]);
         }
         printf("\n");
      }
      printf("\n\n");
}


int main(){
   int mz[2][2];
   mz[0][0] = 1;
   mz[0][1] = 1;
   mz[1][0] = 1;
   mz[1][1] = 0;    
   int mzt[2][2];    
   int n = 10;
   imprime(mz);
   for(int i = n; i >= 1; i = i/2){    
      mzt[0][0] = mz[0][0]*mz[0][0] + mz[0][1]*mz[1][0];
         mzt[0][1] = mz[0][1]*(mz[0][0] + mz[1][1]);
         mzt[1][0] = mz[1][0]*(mz[0][0] + mz[1][1]);
         mzt[1][1] = mz[1][1]*mz[1][1] + mz[0][1]*mz[1][0];
    
         mz[0][0] = mzt[0][0];
         mz[0][1] = mzt[0][1];
         mz[1][0] = mzt[1][0];
      mz[1][1] = mzt[1][1];
      imprime(mz);
    }
      
    system("pause");
    return 0;    
}

[Jonathan Queiroz]

Veja se isso ajuda: Calculando n-ésimo número de Fibonacci em O(log n)

[leigan]

então, já tinha visto "A potência de n é calculada elevando-se a matriz ao quadrado repetidas vezes."

foi o que eu fiz, como entrada n = 10 a saida deveria ser 55

mas tive a seguinte saida:

1 1

1 0

2 1

1 1

5 3

3 2

34 21

21 13

1597 987

987 610

o programa bate com a sequencia de fibonacci:

F(0) = 0...... F(1) = 1 ..... F(2) = 1 ..... F(3) = 2

F(4) = 3..... F(5) = 5 ..... F(6) = 8 ..... F(7) = 13

F(8) = 21 ..... F(9) = 34 ..... F(10) = 55 ..... F(11) = 89

F(12) = 144 ..... F(13) = 233 ..... F(14) = 377 ..... F(15) = 610

F(16) = 987 ..... F(17) = 1597

[leigan]

Boa tarde galera,

consegui achar um codigo que resolve o problema, mas esta em java, alguém pode me ajudar a converter para c, já que não entendo de java

import java.math.BigInteger;
/**
 *
 * @author Halaby
 */
public class Power {

// multiply 2x2 matrices
    public static BigInteger[][] multiply(BigInteger a[][], BigInteger b[][]) {
        BigInteger c[][] = new BigInteger[2][2];
        c[0][0] = a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0]));
        c[0][1] = a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]));
        c[1][0] = a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0]));
        c[1][1] = a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]));
        return c;
    }

// raise a 2x2 matrix a to the nth
    public static BigInteger[][] power(BigInteger a[][], long n) {
        BigInteger res[][] = new BigInteger[2][2];
        res[0][0] = BigInteger.ONE;
        res[1][1] = BigInteger.ONE;
        res[0][1] = BigInteger.ZERO;
        res[1][0] = BigInteger.ZERO;
        if (n == 0) {
            return res;
        }
        while (true) {
            if (n % 2 == 1) {
                res = multiply(res, a);
            }
            n = n / 2;
            if (n == 0) {
                break;
            }
            a = multiply(a, a);
        }
        return res;
    }

// compute the nth Fibonacci
    public static BigInteger fib(long n) {
        if (n == 0) {
            return BigInteger.ZERO;
        }
        BigInteger a[][] = new BigInteger[2][2];
        a[0][0] = BigInteger.ONE;
        a[1][1] = BigInteger.ZERO;
        a[0][1] = BigInteger.ONE;
        a[1][0] = BigInteger.ONE;
        BigInteger res[][] = power(a, n - 1);
        return res[0][0];
    }
}

[leigan]

Bom, consegui achar de forma recursiva, achei que seria interessante postar a solução

void multi(int a[2][2], int c[2][2]){
  int b[2][2];
   
   b[0][0] = (a[0][0]*c[0][0]) + (a[0][1]*c[1][0]);
   b[0][1] = (a[0][0]*c[0][1]) + (a[0][1]*c[1][1]);
   b[1][0] = (a[1][0]*c[0][0]) + (a[1][1]*c[1][0]);
   b[1][1] = (a[1][0]*c[1][0]) + (a[1][1]*c[1][1]);
   a[0][0] = b[0][0];
   a[0][1] = b[0][1];
   a[1][0] = b[1][0];
   a[1][1] = b[1][1];
}
int fibonacci(int n){
   if(n == 1){
      a[0][0] = 1;
      a[0][1] = 1;
      a[1][0] = 1;
      a[1][1] = 0;
   }
   
   c[0][0] = 1;
   c[0][1] = 1;
   c[1][0] = 1;
   c[1][1] = 0;    
   
   
   if(n != 1){
      fibonacci (n / 2);
      if(n %2 == 1){
         multi(a, a);
         multi(a, c); 
      }else{
         multi(a, a);
      }
   }
   return a[0][0];
}