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

-
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. –  Erick Wong Jul 3 '12 at 9:17
It was already suggested in several answers, that this is related to Fibonacci numbers. See e.g. this question at SO: nth fibonacci number in sublinear time. –  Martin Sleziak Jul 3 '12 at 9:33

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

-
Note that the long long datatype will already overflow for $n=100$, let alone the wholly unrealistic range specified in the title. –  Erick Wong Jul 3 '12 at 9:33
That is why I recommend to use long arithmetic –  userNaN Jul 3 '12 at 9:37
I agree in contests answer always required modulo some long long or int number. –  userNaN Jul 3 '12 at 9:39

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

-

$$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 little simpler to just call it $2^{F_n}$, no? –  Gerry Myerson Jul 3 '12 at 9:17

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

-

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 http://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int

-