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

  • 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.2012-07-03
  • 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

  • 2
    Note that the long long datatype will already overflow for $n=100$, let alone the wholly unrealistic range specified in the title.2012-07-03
  • 0
    That is why I recommend to use long arithmetic2012-07-03
  • 1
    I agree in contests answer 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