Repeating ratios

Question

How to calculate the number of tribonacci for a very large n (say 10 ^ 14) in the best difficulty. The number of tribonacci is defined as F(n)=F(n-1)+F(n-2)+F(n-3) using F0=1, F1=2, F2=4 .

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

I want to calculate the nth member in log (n) in the same way as the nth Fibonacci number.

How can I generate a base matrix to use an exponential matrix to calculate the nth term?

I used to try to implement it using DP, but since we cannot take an array of such a large size, it does not work fine. Similarly, recursion did not work due to very large numbers of the order of 10 ^ 14.

Answer 1

The best asymptotic complexity of the tribonacci numbers will use the exponential matrix method, such as the one for Fibonacci numbers . In particular, it is written correctly, these are O (log n) entire operations, and not O (n) (as a dynamic programming method) or O (3 ⁿ ) (as a naive solution).

Matrix of interest

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

and the number n th tribonacci is in the upper left corner of M ⁿ . The expression of the matrix 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:

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

and the result: {F _{n + 2} , F _{n + 1} , F _n } = M ⁿ {F ₂ , F ₁ , F ₀ }, also see here .)

Answer 2

A Dynamic programming solution does NOT require an array of 10 ^ 14 elements. Only 3 required .

Note that each step uses only the previous 3 elements, so for F(1000) you really don't need F(5) .

You can simply redefine items that are no longer needed and treat them as a new number.

The % operator is your friend for this purpose.