How to solve a such problem based on fiboncci ?

general
, , ,
1

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)

1 Like
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 :slight_smile:

1 Like
3

@meooow

can you provide source code.

4

For finding the nth fibonacci number, you can use matrix exponentiation.

See code at https://ronzii.wordpress.com/2011/07/09/using-matrix-exponentiation-to-calculated-nth-fibonacci-number/

2 Likes
5

@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.

6

@meooow @likecs @spinovations @slimtashady

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.

7

@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.

8

@meooow

why do we need to cast values to long?

9

@meooow
is there any technique for further optimazation.

It’s taking too log for the inputs

A=2147483647 A=2147483647 N=1000000000

10

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.

2 Likes
11

@likecs
Thanks.

Can you help me with this,

https://discuss.codechef.com/questions/84745/how-to-find-distance-between-adjacent-elements-in-an-array.

12

Good code provided in comment no 2

1 Like
13

@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.

14

I think the question is already answered by @spinovations.

15

Can you explain what does mulmod function do?

16

You can refer to this http://codeforces.com/blog/entry/15884