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

  • 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

6

Consider $F_n=\log_2(f_n)$. Then $ F_n=F_{n-1}+F_{n-2},\quad F_1=0\quad F_2=1 $ This is exactly the definition of fibonacci sequence. If you want to quickly compute $f_n$, you just need to find quickly $F_n$, and the compute $f_n=2^{F_n}$. This can be done the following way.

Rewrite recurrurence relation for fibbonacci numbers $F_n=F_{n-1}+F_{n-2}$ in matrix form $ \begin{Vmatrix}F_n\\F_{n-1}\end{Vmatrix}=\begin{Vmatrix}1 & 1\\1 & 0\end{Vmatrix}\begin{Vmatrix}F_{n-1}\\F_{n-2}\end{Vmatrix}. $ Hence we get $ \begin{Vmatrix}F_n\\F_{n-1}\end{Vmatrix}=\begin{Vmatrix}1 & 1\\1 & 0\end{Vmatrix}^{n-1}\begin{Vmatrix}F_{1}\\F_{0}\end{Vmatrix} $ It is remains to quickly find $n-1$-th power of matrix $ \begin{Vmatrix}1 & 1\\1 & 0\end{Vmatrix} $ In order to powerize quickly we will use the following identities $ A^{2k+1}=AA^{2k},\qquad A^{2k}=(A^k)^2 $

#include  #include   class matrix2x2 {     public:          matrix2x2() : matr_(2,std::vector(2,0))         { }          matrix2x2(int matr00, int matr01, int matr10, int matr11)                  : matr_(2,std::vector(2,0))         {             matr_[0][0] = matr00;             matr_[0][1] = matr01;             matr_[1][0] = matr10;             matr_[1][1] = matr11;         }          matrix2x2(const matrix2x2& matrix)         {             matr_ = matrix.matr_;         }          const matrix2x2& operator = (const matrix2x2& rhs)         {             if (this != &rhs)             {                 matr_ = rhs.matr_;             }             return *this;         }          int& operator()(int i, int j)         {             return matr_[i][j];         }          const int& operator()(int i, int j) const         {             return matr_[i][j];         }          matrix2x2& operator * (const matrix2x2 rhs)         {             *this = product(*this, rhs);             return *this;         }      private:          matrix2x2 product(const matrix2x2& lhs, const matrix2x2& rhs) const         {             return  matrix2x2(lhs(0,0) * rhs(0,0) + lhs(0,1) * rhs(1, 0),                               lhs(0,0) * rhs(0,1) + lhs(0,1) * rhs(1, 1),                               lhs(1,0) * rhs(0,0) + lhs(1,1) * rhs(1, 0),                               lhs(1,0) * rhs(0,1) + lhs(1,1) * rhs(1, 1));         }       private:          std::vector > matr_; };  matrix2x2 matrix_power(const matrix2x2& matrix, int power) {     if (power == 0)     {         return matrix2x2(1,0,0,1);     }     if (power % 2 == 1)     {         return matrix_power(matrix, power - 1) * matrix;     }      matrix2x2 half_power = matrix_power(matrix, power / 2);     return half_power * half_power; }  long long fibbonacci_number(int n) {     matrix2x2 fibbonacci_matrix = matrix_power(matrix2x2(1,1,1,0), n - 1);     return fibbonacci_matrix(0,0); }  int main() {     std::cout << fibbonacci_number(40);      return 0; } 

Of course you need to use long arithmetic to compute this huge numbers

  • 1
    I agree i$n$ co$n$tests a$n$swer always required modulo some **long long** or **int** number.2012-07-03
3

$f(n) = f(n-1) * f(n-2)\\ f(n) = (f(n-2))^2 * (f(n-3))^1\\ f(n) = (f(n-3))^3 * (f(n-3))^2\\ f(n) = (f(n-3))^5 * (f(n-4))^3$

$\cdots \cdots$

$f(n) = f(2)^{F(n-2)} * f(1)^{F(n-3)}$ ;where $F(n)$ is nth Fibonacci number

Therefore, $f(n) = 2^{F(n-2)}$

So it is enough if we caluculate $(n-2)^\text{nd}$ Fibonacci number to calculate $f(n)$.

2

$f(n)=exp(c_1F_n+c_2L_n)$ where $Fn$ are the Fibonacci Numbers and $Ln$ the Lucas numbers. Given the initial conditions it's easy to find the constants.

  • 4
    A little simpler to just call it $2^{F_n}$, no?2012-07-03
1

Use $F(n)=\log_2 f(n+1)$ to get $\begin{aligned} F(0)&=0 \\ F(1)&=1 \\ F(n)&=F(n-1)+F(n-2) \quad\forall n>1, \end{aligned}$ the definition of the Fibonacci numbers. A fast algorithm for computing large Fibonacci numbers:

We also have the formula $ F(n)=\frac{\alpha^n-\beta^n}{\alpha - \beta} \tag{3}, $ ... where $\alpha=(1+\sqrt{5})/2\; $ and $\beta=(1-\sqrt{5})/2$.

0

Observe that $f(1)=2^0, f(2)=2^1,f(3)=2^1,f(4)=2^2,f(5)=2^3,f(6)=2^5$ and so on...The general term for given recursion is $2^{t_n}$ where $t_n$ represents $n_{th}$ fibonacci number.So, the problem reduces to find fastest algorithm for calculation of fibonacci number.we know that $t_n=\frac{\phi^n-\theta^n}{\sqrt{5}}$ where $\phi=\frac{1+\sqrt5}{2}$ and $\theta=\frac{1-\sqrt5}{2}$ and powers can be calculated in $O(\log n) $.For $O(\log n)$ power calculation algorithm , visit https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int