anupamshah_'s blog

Help needed in Matrix Exponentiation !!!
By anupamshah_, history, 6 years ago, In English

How to solve the following recurrence relation for N ≤109

F(n)=F(n−1)+F(n−2)+F(n−1)∗F(n−2)

(Assuming that we are provided with the values of F(1) and F(2) )

(EDIT: The problem link is attached.)

  • Vote: I like it
  • +18
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

$$$F(n) + 1 = (1 + F(n - 1)(1 + F(n - 2))$$$

Lets say $$$t_n = F_n + 1$$$, then $$$t_n = t_{n - 1} * t_{n - 2} $$$, expanding $$$t_n$$$ it can be realised that $$$t_n = t_0^{p_n} t_1^{q_n}$$$, where $$$p_n, q_n$$$ follows fibonacci recurrence.

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Add 1 on both sides

1+F(n)= 1+F(n-1)+F(n-2)+F(n-1)*F(n-2)

1+F(n)=(1+F(n-1))*(1+F(n-2))

let g(n)=1+F(n)

-> g(n)=g(n-1)*g(n-2)

Now taking log on both sides

log(g(n))=log(g(n-1))+log(g(n-2))

let h(n)=log(g(n))

h(n)=h(n-1)+h(n-2)

Now the nth term of h can be found using matrix exponentation in O(log(n))

→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    It's implied the value needs to be found under a modulo. In this method you need to find the discrete logarithm of the two starting values, which needs BSGS, and even worse, sometimes the discrete logarithm doesn't even exist.

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +12 Vote: I do not like it

      If we have to find f(n)%MOD and MOD is prime then h(n) can be found under mod MOD-1 as h(n)=log2(g(n)) g(n)=2^h(n) and 2^(MOD-1)=1%MOD by Fermats Theorem so we can find h(n) under mod MOD-1 then g(n)=(2^(h(n)% MOD-1))%MOD

      Therefore no need to take the logaritm its just for explanation.

      → Reply
»
6 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

Like so:

First, factor the recurrence to get F(n)=(F(n-1)+1)(F(n-2)+1)-1.

Then, set G(n)=F(n)+1; we find G(n)=(F(n-1)+1)(F(n-2)+1)=G(n-1)G(n-2).

Let A=G(1)=F(1)+1 and B=G(2)=F(2)+1. Since G(n) will always be the product of some earlier terms, we can make a function x(n) and y(n) so that G(n)=A^(x(n))*B^(y(n)).

We have the initial values x(1)=1,x(2)=0,y(1)=0,y(2)=1 and the recurrence relations x(n)=x(n-1)+x(n-2),y(n)=y(n-1)+y(n-2). This is the same as Fibonacci but with different starting values.

Use matrix exponentiation to find x(n) and y(n), and then fast exponentiation to find A^(x(n))*B^(y(n)); the answer is A^(x(n))*B^(y(n))-1.

→ Reply
»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by anupamshah_ (previous revision, new revision, compare).

→ Reply