Any fastest algorithm for $$ f(n) = f(n-1)\cdot f(n-2)\quad\text{ where }\quad f(1) = 1,\quad f(2) = 2 $$ for $3 \leq n \leq 1000000 $.
Any fastest algorithm for $f(n) = f(n-1) \cdot f(n-2)$ where $3 \leq n \leq 1000000$
1
$\begingroup$
algorithms
functions
recursive-algorithms
-
4Be more precise about what you want to compute. There aren't enough atoms in the universe to store the digits of $f(1000000)$. This sounds a lot like a programming contest where you are only interested in $f(n)$ modulo some small number. – 2012-07-03
-
0It was already suggested in several answers, that this is related to [Fibonacci numbers](http://en.wikipedia.org/wiki/Fibonacci_number). See e.g. this question at SO: [nth fibonacci number in sublinear time](http://stackoverflow.com/questions/1525521/nth-fibonacci-number-in-sublinear-time). – 2012-07-03