Iterative Version of Modified Fibonacci Sequence

Question

I was just going through the iterative version of fibonacci series algorithm. I found this following code

int Fibonacci(int n)
{
   int f1 = 0;
   int f2 = 1;
   int fn;
   for ( int i = 2; i < n; i++ )
   {
      fn = f1 + f2;
      f1 = f2;
      f2 = fn;
   }
}  

A silly question just raised in my mind. The function above adds two previous numbers and returns the third one and then get variables ready for the next iteration. What if it would be something like this. "Return a number of series which is the sum of previous three numbers" how we can change the above code to find such a number.u

Solution 1

As a hint, notice that the above algorithm works by "cycling" the numbers through some variables. In the above code, at each point you are storing

 F_0    F_1
  a      b

You then "shift" them over by one step in the loop:

 F_1    F_2
  a      b

You then "shift" them again in the next loop iteration:

 F_2    F_3
  a      b

If you want to update the algorithm sum the last three values, think about storing them like this:

 T_0    T_1    T_2
  a      b      c

Then shift them again:

 T_1    T_2    T_3
  a      b      c

Then shift them again:

 T_2    T_3    T_4
  a      b      c

Converting this intuition into code is a good exercise, so I'll leave those details to you.

That said - there is a much, much faster way to compute the nth term of the Fibonacci and "Tribonacci" sequences. This article describes a very clever trick using matrix multiplication to compute terms more quickly than the above loop, and there is code available here that implements this algorithm.

Hope this helps!

Solution 2

I like recursion. Call me a sadist.

static int rTribonacci (int n, int a, int b, int c) {
    if (n == 0) return a;
    return rTribonacci (n-1, b, c, a + b + c);
}

int Tribonacci (int n) { return rTribonacci(n, 0, 0, 1); }

Solution 3

I don't normally answer questions that "smell" like homework, but since someone else already replied this is what I would do:

int Tribonacci(int n)
{
    int last[3] = { 0, 0, 1 }; // the start of our sequence

    for(int i = 3; i <= n; i++)
        last[i % 3] = last[i % 3] + last[(i + 1) % 3] + last[(i + 2) % 3];

    return last[n % 3];
}

It can be improved a bit to avoid all the ugly modular arithmetic (which I left in to make the circular nature of the last[] array clear) by changing the loop to this:

    for(int i = 3; i <= n; i++)
        last[i % 3] = last[0] + last[1] + last[2];

It can be optimized a bit more and frankly, there are much better ways to calculate such sequences, as templatetypedef said.

Comments

[Marc B]

umm... f = (f - 1) + (f - 2) + (f - 3) which boils down to algebra: f = (3*f) - 6

[templatetypedef]

@MarcB- What you have written above is true, but the notation is wrong. The recurrence is f(n) = f(n - 1) + f(n - 2) + f(n - 3), which cannot be simplified the way you're describing it.

[talhaMalik22]

that is the easy part. how we would values of f1,f2,f3 to get ready for the next iteration?

[talhaMalik22]

You right on the spot. this was actually the tricky part, the way it reassigning values to variables. It is working. Thanks and well done.