Recurrence Relations [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 7 years ago.

How to calculate tribonacci number for very large n ( say 10^14 ) in best complexity. Tribonacci numbers are defined as F(n)=F(n-1)+F(n-2)+F(n-3) with F0=1, F1=2, F2=4.

Or recurrence defined as F(n)=aF(n-1)+bF(n-2)+cF(n-3) with F0=1, F1=2, F2=4.

I want to Calculate nth term in log(n) just like nth Fibonacci number.

How can I generate the Base Matrix for using matrix exponentiation to calulate the nth term?

Previously I was trying to implement it using DP but as we cannot take array of such large size its not working fine. Similarly Recursion didn't work here due to stack overflow for very large numbers of order of 10^14.

Answer 1

A Dynamic programming solution does NOT require 10^14 elements array. It only requires 3.

Note that each step is only using previous 3 elements, so for F(1000), you really do not need F(5).

You can simply override elements that are no longer needed, and regard them as a new number.

The % operator is your friend for this purpose.

Answer 2

The best asymptotic complexity for tribonacci numbers will be using a matrix exponentiation method like the one for Fibonacci numbers. Specifically, written correctly, this is O(log n) integer operations, rather than O(n) (like the dynamic programming method) or O(3ⁿ) (like the naive solution).

The matrix of interest is

    [1, 1, 1]
M = [1, 0, 0]
    [0, 1, 0]

and the nth tribonacci number is in the upper left corner of Mⁿ. The matrix exponentiation must be computed by squaring to achieve log(n) complexity.

(for F(n+3) = a F(n+2) + b F(n+1) + c F(n), the matrix is:

    [a, b, c]
M = [1, 0, 0]
    [0, 1, 0]

and the result is {F_n+2,F_n+1,F_n} = Mⁿ {F₂,F₁,F₀}, also see here.)