FIBONACCI Numbers

1

how to find the sum of n fibonacci numbers so that time limit does not exceed?
where n <=10^18

1 Like
2

Actually the sum of fibonacci numbers is very similar to a fibonacci number. PROOF

3

this might help you

4

@psaini72 @knakul853
can it be done using matrix exponentiation ?

5

Yes, check hc notes. And their code. Its the fastest code on the internet to calculate nth-fibonacci number.
During a HMC contest, I tried 16-17 different possible codes from various places on internet to calculate nth-fibonacci number and the one I mentioned above gave AC, rest all TLE,even the code in above link did not work as TL was too strict :stuck_out_tongue:

6

yeah i have used in contest also for bruteforces solution.
btw what is this HMC contest

7

here is all approach

8

well here i am not talkin about nth term coz u have to take the exponentiation of a certain matrix .
i am talking about sum of n terms where n can be 10^18.Will this method wont be TLE?

9

Hello @phoenix0203
If you fiddle around with the expression of sum of n Fibonacci numbers, you will be able to express the sum of n fibonacci numbers as {fib(n+2) - 1}.
So the sum of first n fibonacci numbers S(n) can be written as
S(n) = fib(n+2) - 1;
Now i leave to you the question as to, why we can solve this in matrix exponentiation without breaching acceptable time limits.

Tread Carefully, Hints below

Hint1 : You can do this with a 2x2 matrix.
Hint2 : (A^x) for any integer x in can be done in O((n^3) * log2x), where A is the matrix and n is the dimension of matrix.
Happy Coding.

10

Hello @anon55659401
Can you please clarify what you mean by “hc notes” and “HMC contest”?
I am unable to deduce it.
Thank You

11

You can do it in o(1)
Nth Fibonacci no in given by
Fn = {[(√5 + 1)/2] ^ n} / √5
It’s a simple gp now
Use big integer in java to process in one go
Hope it helps :smile:

12

Hello @avenger786
I am aware of this approach. But first you have to reach S(n) = fib(n+2) -1 to apply that formula.

13

Use BigInteger.It might help

14

I think what you are looking for is matrix exponentiation.

15

Never use this, it does not give accurate results cuz of square root and divide operations, use matrix exponentiation which works in O(lgN) time.

16

Sum of Fibonacci Numbers - GeeksforGeeks Read this, I don’t have the time to explain the basic property of fibonacci numbers in detail…