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$
-
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
5 Answers
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
-
1I agree i$n$ co$n$tests a$n$swer always required modulo some **long long** or **int** number. – 2012-07-03
$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.
-
4A little simpler to just call it $2^{F_n}$, no? – 2012-07-03
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 https://stackoverflow.com/questions/101439/the-most-efficient-way-to-implement-an-integer-based-power-function-powint-int