You are not logged in. Please login at www.codechef.com to post your questions!

×

How to solve a such problem based on fiboncci ?

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

saksham458's gravatar image

0★saksham458
4648
accept rate: 50%

edited 10 Sep '16, 21:31


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/

link

answered 10 Sep '16, 02:32

akshit_96's gravatar image

4★akshit_96
3093
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) saksham4580★

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.

link

answered 11 Sep '16, 15:32

likecs's gravatar image

6★likecs
3.7k1774
accept rate: 9%

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) error_503_4044★
(13 Sep '16, 15:20) likecs6★

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 :)

link

answered 09 Sep '16, 03:06

meooow's gravatar image

6★meooow ♦
6.7k717
accept rate: 48%

@meooow

can you provide source code.

(09 Sep '16, 23:06) saksham4580★

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

(10 Sep '16, 07:37) saksham4580★

@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) saksham4580★

@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) saksham4580★

@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

Good code provided in comment no 2

link

answered 11 Sep '16, 22:46

rbpt's gravatar image

2★rbpt
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,879
×1,617
×226
×137

question asked: 09 Sep '16, 01:12

question was seen: 4,428 times

last updated: 13 Sep '16, 15:20