CODEWITHSUNDEEP
c++fibonacci
M00000001
M00000001

Reputation: 309

Cannot Make Sense of Fibonacci Solution Using Modulo

I got the following piece code to generate Fibonacci series but I cannot make sense of it, what is the math methodology behind it?

Here is the code: comes from 5.3 of Quant Job Interview Questions and Answers by Mark Joshi

int Fib2(int N):
{
    std::vector<int> v(3);
    v[0] = 1;
    v[1] = 1;
    for (int j = 0; j<=N-2; ++j)
      v[(j+2)%3] = v[(j+1)%3] + v[(j)%3];
    return v[N%3];
}

Also, what is the meaning of std::vector in the above code?

Upvotes: 0

Views: 52

Answers (1)

scohe001
scohe001

Reputation: 15446

An std::vector is a container (similar to an array). In this case, it's storing 3 integers. Essentially, they're trying to be fancy and not use 3 int variables that they constantly reassign every loop (which would be simpler/more readable code).

To calculate a Fib number, you need to sum the last two Fib numbers. So we really only need 3 integers at a time: the last two Fib numbers, and then another integer to store our new Fib number.

We're using modulo here to tell us which index is which. So the vector will look like this through the loops: (the star denotes the index we just calculated and assigned)

+--------------------------+
| Fib(0) | Fib(1) | *Fib(2)|
+--------------------------+
|   1    |   1    |    2   |
+--------------------------+

+--------------------------+
|*Fib(3) | Fib(1) | Fib(2) |
+--------------------------+
|   3    |   1    |    2   |
+--------------------------+

+--------------------------+
| Fib(3) | *Fib(4) | Fib(2)|
+--------------------------+
|   3    |   5     |   2   |
+--------------------------+

etc...

A simpler implementation with 3 integers (that's functionally the same as this) would look like:

int Fib2(int N) {
    int last, curr;
    last = curr = 1;

    for (int j = 0; j<=N-2; ++j) {
      int newest = last + curr;
      last = curr, curr = newest;
    }
    return curr;
}

Upvotes: 3

Related Questions