×

# Matrix exponentiation

 0 1 For equation F(x) = F(x-1) + F(x-2) + ( F(x-1) * F(x-2) ) given F(0) and F(1) can we calculate F(n) in log(n) time? asked 19 Feb, 19:40 94●4 accept rate: 0%

 3 Well, you can just define $G(x) = F(x)+1$, which has the recurrence relation $G(x) = G(x-1)G(x-2)$, which you can calculate in $\log(n)$ time. answered 20 Feb, 23:29 43●4 accept rate: 0% Wow..... How did you got this logic ?? Awesome.... (21 Feb, 00:57) I see it's available on math. stack exchange (21 Feb, 01:05) @theoneyowwant how to calculate G(x) = G(x-1)G(x-2) in log(n) time? (21 Feb, 10:06) It's just Fibonacci in power... Take log and see the pattern... Then use matrix exponentiation as shared by @sagar2405 (21 Feb, 10:09) I hope it's not a question for an ongoing contest... Otherwise you can be banned from discuss site... Please delete this post in case it's for an ongoing contest... (21 Feb, 10:10) Well, I just thought of this myself, since it's somewhat similar to think of it as a functional equation, where such transforms are quite common. In general, you can try such substitutions on various reccurences to get a better form/ to solve it faster. You may have also solved some dynamic programming problems where redefinitions give a faster solution. (21 Feb, 12:05) 1 Its not from a ongoing contest , its from a past contest i cam across .. (22 Feb, 13:34) showing 5 of 7 show all
 0 We can easily found f(n) in O(n) time,but not sure about O(logn). answered 20 Feb, 22:13 0●1 accept rate: 0% yeah O(n) is pretty simple but the problem required log(n) or something similar . 0 < n < 10^8.. (20 Feb, 23:07) This problem is similar of finding nth Fibonacci in O(logn) time. I found this, https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ , in which we can find fibonnaci in O(logn) time. Hope this might help. (20 Feb, 23:28)
 0 I found it online that $F(n) = 2^{Fib(n)}-1$ when f(0)=0 and f(1)=1. And $2^{fib(n)}$ can be calculated in $logn$. But it is special case. For the generalized version, @theoneyouwant wrote the perfect answer. answered 21 Feb, 01:16 33●5 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×138