Any fastest algorithm for $f(n) = f(n-1)  \cdot f(n-2)$ where $3 \leq n \leq 1000000$ 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 $.
 A: 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 <iostream>
#include <vector>

class matrix2x2
{
    public:

        matrix2x2() : matr_(2,std::vector<int>(2,0))
        { }

        matrix2x2(int matr00, int matr01, int matr10, int matr11) 
                : matr_(2,std::vector<int>(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<std::vector<int> > 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
A: $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)$.
A: $$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.
A: 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$.

A: 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
