Implementação – Fast Doubling

Descobrir o n-ésimo elemento da sequência de fibonacci é o problema mais manjado de competições de programação, mas mesmo assim sempre há uma forma criativa de expor esse conceito e por isso é bom estar preparado.

Se você só conhece o método recursivo e/ou iterativo (O(n)), uma hora ou outra vai passar algum apuro para descobrir alguns valores maiores.

Por mais que essa sequência seja um grande mistério, e ainda não se conhece uma fórmula* 100% precisa para descobrir os elementos, para nossa salvação há alguns métodos com complexidade bem “amigáveis”.

Clique no link abaixo para ver a implementação do algoritmo Fast Doubling, que descobre o n-ésimo elemento em complexidade O(log N).

#include <math.h>
#include <vector>
using namespace std;
typedef long long int lli;
typedef pair<lli, lli> ii;

ii fast_doubling(lli n, lli mod) {
	if(n == 1) return ii(1, 1);
	else if(n == 2) return ii(1, 2);
	
	ii aux = fast_doubling(n/2, mod);
	ii ret;
	ret.first = (aux.first*(aux.second*2 + mod - aux.first))%mod;
	ret.second = ((lli)pow(aux.first, 2)+(lli)pow(aux.second, 2))%mod;
	
	if(n%2 == 0) {
		return ret;
	} else {
		return ii(ret.second, (ret.first+ret.second)%mod);
	}
}

O principal motivo de eu postar esse código é porque existem outras maneiras de implementá-lo que não são fiéis à complexidade prometida.

* Existe uma fórmula para calcular um elemento da sequência de fibonacci baseada na lendária razão dourada (google it), mas ela não é 100% precisa.

3 comentários em “Implementação – Fast Doubling”

    1. Perdão Thalyson, o objetivo do post era só exibir uma implementacão mesmo, pois algumas outras que encontrei na internet não funcionavam tão bem.
      Para mais detalhes sobre o algoritmo em si, por hora eu recomendo que você pesquise no google mesmo.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.