Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  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

5 Answers 5

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

share|improve this answer
2  
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
1  
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)$.

share|improve this answer

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

share|improve this answer
4  
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$.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.