Problem : TSHOW2 - Fibonacci brain
Solution :
We can easily calculate nth Fibonacci number by dynamic programming using the recurrence relation - \[ { f(x) } = \left\{ \begin{array}{ll} { f(x-1) + f(x-2) } & \mbox{if } x > 2 \\ 1 & \mbox{if } x = 2 \\ 0 & \mbox{if } x = 1 \end{array} \right. \]
f[1] = 0
f[2] = 1
for i in { 3 ... n }
f[i] = f[i-1] + f[i-2]
But we cannot calculate Fibonacci number by dynamic programming when n is large like 10^18.
We can easily calculate large 10^18 Fibonacci number by matrix exponentiation.
We can write that,
\[ \begin{bmatrix} {1} & {1} \\ {1} & {0} \end{bmatrix} ^ {n} = \begin{bmatrix} { f(n+1) } & { f(n) } \\ { f(n) } & { f(n-1) } \end{bmatrix} \]
n is large , using binary exponentiation we can calculate nth Fibonacci number by O(log n) complexity.
Solution :
We can easily calculate nth Fibonacci number by dynamic programming using the recurrence relation - \[ { f(x) } = \left\{ \begin{array}{ll} { f(x-1) + f(x-2) } & \mbox{if } x > 2 \\ 1 & \mbox{if } x = 2 \\ 0 & \mbox{if } x = 1 \end{array} \right. \]
f[1] = 0
f[2] = 1
for i in { 3 ... n }
f[i] = f[i-1] + f[i-2]
But we cannot calculate Fibonacci number by dynamic programming when n is large like 10^18.
We can easily calculate large 10^18 Fibonacci number by matrix exponentiation.
We can write that,
\[ \begin{bmatrix} {1} & {1} \\ {1} & {0} \end{bmatrix} ^ {n} = \begin{bmatrix} { f(n+1) } & { f(n) } \\ { f(n) } & { f(n-1) } \end{bmatrix} \]
n is large , using binary exponentiation we can calculate nth Fibonacci number by O(log n) complexity.
Comments
Post a Comment