1
$\begingroup$

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 $.

  • 4
    Be 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
  • 0
    It 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

5 Answers 5