A Log(n) Solution for the Fibonacci Sequence

The Problem in Brief

The problem defines a new Super Fibonacci sequence.

$$ F_{0}=F_{1}=F_{2}=F_{3}=F_{4} = 1 $$

$$ F_{N}= 2018 \times F_{N-1} + 2017 \times F_{N-2} + 2016 \times F_{N-3} + 2015 \times F_{N-4} + 2014 \times F_{N-5} $$

Given an N, compute the Nth value of the sequence.

N in the problem is very large — the size of a 64-bit int. Each additional term needs 5 multiplications and 5 additions. Computing term by term will definitely time out. But is there a simpler way?

Computing the Ordinary Fibonacci

After reading the problem I thought about computing the ordinary Fibonacci sequence, because I had learned of a Log(n) method that works via matrix fast exponentiation.

$$ F_{N}= F_{N-1} + F_{N-2} $$

The method is roughly this:

$$ M1 \times M = M2 $$

If we plug the simple Fibonacci computation into the formula:

$$ \begin{bmatrix} F_{N-1} & F_{N-2} \ 0 & 0 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix}

\begin{bmatrix} F_{N} & F_{N-1} \ 0 & 0 \end{bmatrix} $$

Here M is $$ \begin{bmatrix} 1 & 1 \ 1 & 0 \end{bmatrix} $$

And $$ M_{1} \times M \times M … \times M = M_{n}$$ can be transformed into \(M_{1} \times M^{n} = M_{n}\) — just solve for \(M^{n}\) and the result follows.

With such a method, obtaining the M matrix is the important part, right?

How to Solve for the Key M Matrix

Here I offer a simple approach. For Super Fibonacci we can set it up like this: first, this M matrix must be a \( 5 \times 5\) matrix; then we can assume the first row of \(M_{n-1}\) looks like this:

$$ \begin{bmatrix} F_{n-1} & F_{n-2} & F_{n-3} & F_{n-4} & F_{n-5} \end{bmatrix} $$

Then the first row of \(M_{n}\) should look like this:

$$ \begin{bmatrix} F_{n} & F_{n-1} & F_{n-2} & F_{n-3} & F_{n-4} \end{bmatrix} $$

Don’t ask me why it’s like this — if it weren’t, how would you iterate? With the assumption above, we fill all other rows with zeros.

From the first rows of the two matrices, I think the M matrix can be derived (by working backwards — compute the matrix multiplication):

$$ \begin{bmatrix} 2018 & 1 & 0 & 0 & 0 \ 2017 & 0 & 1 & 0 & 0 \ 2016 & 0 & 0 & 1 & 0 \ 2015 & 0 & 0 & 0 & 1 \ 2014 & 0 & 0 & 0 & 0 \end{bmatrix} $$

For any n, we can first compute \(M^{n}\) and then obtain the final result.

Using Matrix Fast Exponentiation

This is a simple fast-exponentiation solution for \(a^{b}\); the Java code below comes from fast exponentiation:

private static int cifang(int a, int b) {
    int s = 1;
    while (b > 0) {
        if (b % 2 == 1) { // b=b>>1 guarantees this if-branch executes on the last step
            s = s * a;
        }
        a = a * a;
        b = b >> 1;
    }
    return s;
}

For us, fast exponentiation is done on matrices.

unsigned long long orig_m_mtx[][5] = {
    {2018, 1, 0, 0, 0},
    {2017, 0, 1, 0, 0},
    {2016, 0, 0, 1, 0},
    {2015, 0, 0, 0, 1},
    {2014, 0, 0, 0, 0},
}; // the M matrix

// Fast exponentiation implementation; compare with the Java code above
unsigned long long get_rlt(unsigned long long n) {
    if(n < 5) return 1;
    int cur = n - 4;

    unsigned long long m_mtx[5][5];
    unsigned long long m_mtx_tmp[5][5];


    unsigned long long mtx_rlt[5][5] {  // int s = 1;
        {1, 0, 0, 0, 0},
        {0, 1, 0, 0, 0},
        {0, 0, 1, 0, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 0, 1},
    };
    save_mtx(m_mtx, orig_m_mtx);

    while(cur > 0) {
        if(cur % 2 == 1) {
            mk_times(m_mtx, mtx_rlt, m_mtx_tmp); // m_mtx_tmp = m_mtx * mtx_rlt
            save_mtx(mtx_rlt, m_mtx_tmp);        // mtx_rlt = m_mtx_tmp
        }
        mk_twice(m_mtx, m_mtx_tmp);              // m_mtx_tmp = m_mtx * m_mtx
        save_mtx(m_mtx, m_mtx_tmp);              // m_mtx = m_mtx_tmp
        cur  = cur >> 1;
    }

    return mk_rlt(mtx_rlt);
}

See the gist for the detailed code.

Extension (O(1))

If you’ve studied linear algebra, you may be able to follow this solution: The Linear Algebra View of the Fibonacci Sequence. This solution derives the closed form directly. But the computation is not small, haha.