anupamshah_'s blog

Help needed in Matrix Exponentiation !!!
By anupamshah_, history, 4 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?
»
4 years ago, # |
  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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am getting the idea, just wanted to clarify that Is pn always ≤ qn ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yeah, you can prove it inductively. 2nd Term satisfies the condition and the third as well. Since from next term onwards, it's just the multiplication of the last two terms, pn≤qn for all of them.

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

    How did you get the idea that pn and qn will follow fibbonacci recurrence

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

    Could you please help me debug my code?

    I am getting a WA, although I tested at various random inputs with an accepted code.

    → Reply
»
4 years ago, # |
  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
  • »
    »
    4 years ago, # ^ |
      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
    • »
      »
      »
      4 years ago, # ^ |
      ← 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
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you explain more about when to take %MOD and %MOD-1 please.

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

          // ^^ means exp

          let u need to find (a^^p)%m, where m is prime.

          and value of p cannot be stored, same as in this ques ==> fib powers cannot be stored.

          using fermats theorem [ a^^(m-1) % m = 1 ]

          (a^^p)%m = (a^^r)%m, where r = p % (m-1)

          → Reply
»
4 years ago, # |
  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
»
4 years ago, # |
  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