21 junio 2006

Sucesión de Fibonacci

La Sucesión de Fibonacci es una lista de número muy famosa en matemáticas:

1, 1, 2, 3, 5, 8, ...

Los 2 primeros números son 1, y luego cada números posterior es la suma de los 2 anteriores:

1, 1, 1+1, 1+2, 2+3, 3+5, ...

Si quieres saber el número de Fibonacci que está en la posición 1 millón, puedes calcularlos uno a uno hasta llegar a 999.998 y 999.999, al sumarlos tendrás el Fibonacci 1.000.000.

Pero hay una forma más rápida, encontré este algoritmo que permite calcular 3 números de Fibonacci en tiempo logarítmico. El truco está en que calculando la potencia de una cierta matriz se pueden obtener varios valores de la sucesión y cómo sí se conoce un algoritmo de coste logarítmico para exponenciar, se puede utilizar para calcular número de Fibonacci mucho más rápido que con el método simple.


// Fibonacci (Divide y vencerás)
// calcula el término f(n) utilizando en tiempo O(log n)
// Utiliza esta propiedad de las matrices y el algoritmo de
// exponenciación DyV
// | 0 1 |^n | f(n-2) f(n-1) |
// | 1 1 | = | f(n-1) f(n) |
// cuidado! sólo da el resultado correcto para n <= 93

unsigned long long fibDyV(unsigned int n) {
unsigned long long int i, h, j, k, t;
i = h = 1;
j = k = 0;
while (n > 0) {
if (n%2 == 1) {
t = j*h;
j = i*h + j*k + t;
i = i*k + t;
}
t = h*h;
h = 2*k*h + t;
k = k*k + t;
n /= 2;
}
return j;
}