6

How to find nth tribonacci number with matrix multiplication method if the initial values are some arbitrary numbers say 1, 2 3 i.e T(1) = 1, T(2) =2 and T(3) = 3.

If T(n) = T(n-1) + T(n-2) + T(n-3) then how to find T(n) if n is very very large, I would appreciate if anyone can explain with matrix multiplication method. How to construct initial matrix.

user650521
  • 583
  • 1
  • 9
  • 23
  • Does it need to necessarily be with matrix multiplication? FYI there are better ways to do it. – arshajii Sep 08 '12 at 13:14
  • @A.R.S. can u explain your solution with this example please – user650521 Sep 08 '12 at 13:16
  • @user650521 Refer to this document: http://mathworld.wolfram.com/TribonacciNumber.html – nullpotent Sep 08 '12 at 13:16
  • Is there any specific language you're using? The final answer will look something like the answer to [this](http://stackoverflow.com/questions/12255193/count-number-of-possible-paths-up-ladder/12255200#12255200) question. But you will use not only `a` and `b`, but also a `c` (since its tribonacci not fibonacci). Also, you would just add (3, 3) to the map as well (in that static initializer block). – arshajii Sep 08 '12 at 13:17
  • @A.R.S. Im using C, but I dont want to use a recurrence relation. It would either consume lot of time or lot of space. If it is fast multiplication method it would solve my problem. – user650521 Sep 08 '12 at 13:24
  • @iccthedral How to fit my question in that explanation?...Can u help – user650521 Sep 08 '12 at 13:24
  • @user650521 Just click the edit button under the question. – arshajii Sep 08 '12 at 13:37

2 Answers2

9

The matrix multiplication method involves using the matrix recurrence relation.

For the Fibonacci series, we can define a vector of length 2 to represent adjacent Fibonacci numbers. Using this vector, we can define a recurrence relation with a matrix multiplication:

enter image description here

Similarly, the Tribonacci series recurrence relation can be written in this way:

enter image description here

The only difference is that the vector and matrix sizes are different.

Now, to calculate a large Tribonacci number, we just apply the matrix multiplication n times, and we get:

enter image description here

The matrix to the power of n (Mn) can be efficiently calculated, because we can use an exponentiation algorithm.

Many efficient exponentiation algorithms for scalars are described by Wikipedia in Exponentiation by Squaring. We can use the same idea for matrix exponentiation.

I will describe a simple way to do this. First we write n as a binary number, eg:

n = 37 = 100101

Then, calculate M to each power of 2 by squaring the previous power of 2: M1, M2 = M1M1, M4 = M2M2, M8 = M4M4, M16 = M8M8, M32 = M16M16, ...

And finally, multiply the powers of M corresponding to the binary digits of n. In this case, Mn = M1M4M32.

After calculating that, we can multiply the matrix with the Tribonacci vector for the first 3 values, ie.

enter image description here

Because the matrices have fixed size, each matrix multiplication takes constant time. We must do O(log n) matrix multiplications. Thus, we can calculate the nth Tribonacci number in O(log n) time.

Compare this to the normal dynamic programming method, where it takes O(n) time, by calculating each Tribonacci number up to the nth Tribonacci number (ie. for (i = 3 to n) {T[i] = T[i-1]+T[i-2]+T[i-3];} return T[n];).

I will assume that you know how to code up matrix multiplication in the language of your choice.

ronalchn
  • 12,225
  • 10
  • 51
  • 61
4

Consider:

                           | a1 b1 c1 |
[f(n) f(n - 1) f(n - 2)] * | a2 b2 c2 | = [f(n + 1) f(n) f(n - 1)]
                           | a3 b3 c3 |

Find the unknowns in the matrix based on that and that will be the matrix you want.

The answer in this case is:

1 1 0
1 0 1
1 0 0

The method is general however, it works even if you sum k previous terms, even if they have constants in front of them etc.

IVlad
  • 43,099
  • 13
  • 111
  • 179