The Magic of the Fibonacci Numbers & why we love computing them - part 2

#computerscience #cpp

In the previous post, we've discussed some of the "magical" properties that the numbers of the Fibonacci Sequence have. We now clearly have an idea about why they're so popular, and today we will be exploring their properties and means of computing a little bit further!

Properties

The Fibonacci sequence is periodic modulo any positive integer greater than or equal to 2

Let's take a look at the first 6 Fibonacci Numbers modulo 2:

If we were to continue, we would have got a cycle repeating at the length of 3: 0, 1, 1; 0, 1, 1; 0, 1, 1 and so on. Well, we will always get a cycle when calculating the Fibonacci Sequence modulo any positive integer >= 2.
Why is that? The reason is that there is only a finite number of remainders when dividing by let's say, m, that being: 0, 1, 2, ... m-1 (m numbers), hence being only a finite number of remainder pairs that we can add up (m*m) - so we will eventually get to a point where we add the same pair together for a second time. Also, a period always starts with 0, 1.

The cycle length is called a Pisano period.

The Fibonacci numbers are important in the computational runtime analysis of Euclid's algorithm

The worst case input for Euclid's algorithm are two consecutive Fibonacci numbers Lamé's Theorem (Knuth), 1997

Computing

Constant memory, iterative approach

We can compute the n-th Fibonacci number using constant memory by observing something very simple: from the formula, we only need the previous two numbers, so there's no point in storing all of them.

int iterativeFibo(int n) {
    if(n == 1) return 0;
    if(n == 2) return 1;

    int prev = 0, secondPrev = 1,
        current;

    for(int i = 2; i <= n; i++) {
        current = prev + secondPrev; /// F(n) = F(n-1) + F(n-2)

        secondPrev = prev; /// F(n-2) -> F(n-1) 
        prev = current; /// F(n-1) -> F(n)
        /// F(n-1) and F(n) are the only things we need to compute F(n+1), so we're good to go.
    }

    return current;
}

Without much analysis, we can clearly see that this function takes O(n) time and constant space: we are only storing 3 variables, no matter how big the input (n) is.

Precalculating for numerous queries using Pisano periods.

If we need the Fibonacci numbers modulo m and we will be doing lots of queries, we can use memoization to answer our queries in constant time. Let's say we have to answer with the n-th Fibonacci number modulo m, with a very large n. It is a lot less costly to precalculate the first cycle of the period and then answer a query using our precomputed results.

vector<int> fibo;
int pisanoPeriod = 0;

void pisanoFibo(int m) {
    fibo.push_back(0);
    fibo.push_back(1);

    int last = 1;
    while((fibo[last] + fibo[last-1]) % m != 0 || fibo[last] != 1) { /// 0, 1 start a new cycle
        fibo.push_back((fibo[last] + fibo[last-1]) % m);
        last++;
    }

    pisanoPeriod = last;
}

int query(int n) {
    return fibo[(n-1)%(pisanoPeriod+1)]; /// because we started from 0
}

This approach has an O(pisanoPeriod) time and space complexity and can be applied to various dynamic programming problems, when faced with a large number of queries or a periodic result.

That being said, that's the end of the article. In the next article, we are going to talk a little about the golden ratio and we will be looking even further into means of computing the Fibonacci numbers - we will see how we can compute the n-th Fibonacci number in O(log n) time and constant space, a very useful method for solving recurrence relations in logarithmic time. Feel free to express yourself in the comments!