×

# How to solve a such problem based on fiboncci ?

 2 A function is defined as follows : GF(A,B,0)=A GF(A,B,1)=B GF(A,B,N)= GF(A,B,N-1)+GF(A,B,N-2) where N>1 Given 3 non negative numbers A B N returns remainder from division by 1000000007 For example given A =3 B=4 n =5 the function should return 29 BECAUSE GF(3,4,0)= 3 mod 1000000007 = 3 GF(3,4,1)= 4 mod 1000000007 = 4 GF(3,4,2)= (GF(3,4,0)+GF(3,4,1)) mod 1000000007 =7 GF(3,4,3)= (GF(3,4,1)+GF(3,4,2)) mod 1000000007 =11 GF(3,4,4)= (GF(3,4,2)+GF(3,4,3)) mod 1000000007 =18 GF(3,4,5)= (GF(3,4,3)+GF(3,4,4)) mod 1000000007 =29 Can anyone solve this question in time complexity: O(logN) space complexity: O(1) asked 09 Sep '16, 01:12 46●4●9 accept rate: 50%

 4 For finding the nth fibonacci number, you can use matrix exponentiation. answered 10 Sep '16, 02:32 309●3 accept rate: 54% @akshit_96 Can you please code it I am facing issue with overflow. or this is my code http://ideone.com/mmGyDZ if you can fix integer overflow in it. This code is not able to calculate it for big numbers. It would be a great help. (10 Sep '16, 07:37)
 4 For getting a very fast implementation of only fibonacci numbers, you can refer to this thread : https://discuss.codechef.com/questions/62693/fastest-way-to-calculate-nth-fibonacci-number-modulo-m BTW, I have a even smaller implementation for fibonacci numbers and according to the FIB64 problem on Spoj, I was ranked 14 among some of the fastest solution. You can find my implementation at https://github.com/likecs/Competitive-Coding/blob/master/C%2B%2B/Maths/fibonacci_mod_m.cpp It works for all types on input and also handles the case even if we are multiplying even 2 "long long " values as well. The complexity is O(logn) and space complexity is O(1). Also, since mod operations are costly, the code has been designed in such a way so as to carry out mod operations only when required. Hope it helps now. answered 11 Sep '16, 15:32 6★likecs 3.7k●19●78 accept rate: 9% @likecs Thanks. Can you help me with this, https://discuss.codechef.com/questions/84745/how-to-find-distance-between-adjacent-elements-in-an-array. (11 Sep '16, 19:06) I think the question is already answered by @spinovations. (12 Sep '16, 13:49) likecs6★ Can you explain what does mulmod function do? (13 Sep '16, 00:04) You can refer to this http://codeforces.com/blog/entry/15884 (13 Sep '16, 15:20) likecs6★
 2 If we observe the given function, we can see a pattern G(a, b, 0) = a G(a, b, 1) = b G(a, b, 2) = a + b G(a, b, 3) = a + 2b G(a, b, 4) = 2a + 3b G(a, b, 5) = 3a + 5b G(a, b, 6) = 5a + 8b G(a, b, 7) = 8a + 13b ... and so on. So if we consider the Fibonacci series as 0,1,1,2,3,5,8,13... with F(0) = 0, then G(A, B, N) = A for N = 0 = F(N-1)*A + F(N)*B for all N > 0 It is possible to calculate F(N) in O(log N). The math is explained here. The algorithm for the same can be found here (see Method 5 and 6). All that is left is to evaluate the expression properly modulo 109+7. Hope this helps :) answered 09 Sep '16, 03:06 6★meooow ♦ 6.9k●7●17 accept rate: 49% @meooow can you provide source code. (09 Sep '16, 23:06) This is my code http://ideone.com/mmGyDZ if you can fix integer overflow in it. This code is not able to calculate it for too big values. It would be a great help. (10 Sep '16, 07:37) @saksham458 You are facing overflow because of lines such as these int x = ((F[0][0]*M[0][0])%MOD + (F[0][1]*M[1][0])%MOD)%MOD; It overflows when you do ((int)*(int)), so taking modulo of the wrong result does not help. You need to do this int x = (int)((((long)F[0][0]*M[0][0])%MOD + ((long)F[0][1]*M[1][0])%MOD)%MOD); so that the type is first promoted to long and then the expression is evaluated... or simply change the type of F and M arrays to long. (10 Sep '16, 18:02) meooow ♦6★ @meooow why do we need to cast values to long? (10 Sep '16, 18:25) @meooow is there any technique for further optimazation. It's taking too log for the inputs A=2147483647 A=2147483647 N=1000000000 (10 Sep '16, 18:26) @saksham458 Your code is taking too long for N=1000000000 because you are using a method of complexity O(n). Please pay attention my comment as well as the others who have commented. We clearly mention that Fibonacci should be calculated with O(log n) complexity and we have provided relevant links for that. (11 Sep '16, 23:29) meooow ♦6★ showing 5 of 6 show all
 2 Good code provided in comment no 2 answered 11 Sep '16, 22:46 2★rbpt 11 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:

×1,966
×1,632
×228
×137

question asked: 09 Sep '16, 01:12

question was seen: 4,664 times

last updated: 13 Sep '16, 15:20