Tribonacci Series

Question

Possible duplicate:
Recurring relationship

How to find the n: th number in tribonacci? I need and the algorithm is fast enough for n to 10 ^ 15.

The number of tribonacci is defined as a (n) = a (n-1) + a (n-2) + a (n-3) with a (0) = a (1) = 0, a (2) = 1.

Answer 1

For any sequence with linear recursion, the exponential matrix algorithm works.

If, for example, the sequence has recurrence

 a[k] = x*a[k-1] + y*a[k-2] + z*a[k-3] 

for k >= 3 and the initial values a[0], a[1], a[2] , you get a triple (a[n+2], a[n+1], a[n]) by multiplying

 |xyz|^n |a[2]| |1 0 0| * |a[1]| |0 1 0| |a[0]| 

The matrix can be raised to power n ^th using exponentiation by re-squaring in steps O(log n) .