Fastest way to calculate Fibonacci number

10

I know the answer but I am busy with something…

12

Is this the way of talking in a discuss forum?

Not taking any sides, but I am very displeased by how such random comments cause a lot of spam in some threads. Please maintain professionalism.

5 Likes
13

So sorry @vijju123 ,:pensive:

1 Like
15

it is the simplest way to calculate the fibonacci no
a,b=0,1
print(a,b,end=" “)
for i in range(50):
c=a+b
a,b=b,c
if(c<=50):
print(c,end=” ")

1 Like
16

Hello… I appreciate your effort my friend ; but I think we both are not on the same page… or maybe I was not able to understand something in your explanation…

Actually I understand every single detail about the matrix exponentiation trick… from where it comes ; to its correctness and time complexity of O(log N).

What I don’t know is the method which @anon55659401 mentioned… ( The fast doubling one… ) That from where does those two formulas come from…

I have seen that formula earlier also ; but I forget it each time bcos I don’t know form where it comes ( That’s why they are hard to remember for me ) …

And in my previous comment also ; I replied him ( @anon55659401 ) for that formula only… If you know how do they come ; please share…Thanks…

17

Ok bro… no problem :+1: ; but whenever you get time ; please re-visit this ; I am eager to know from where they come… Thanks…!

19

If you know how do they come ; please share…Thanks…

Hi! Here I am using the same matrix exponentiation to derive the fast doubling formula. The explanation is fairly straightforward. Let me know if something needs further explanation!

24_1
New Doc 2019-08-12 08.29.24_1.jpg1852Ă—2560 244 KB

1 Like
21

Woooo…! Pleased to see how much efforts forum members put in to help others… Was opening the discuss page for past few days just for something like this… It really helped ; Thanks…! :slight_smile:

1 Like
22

http://cp-algorithms.com/ It all comes from here @ritesh1340

1 Like
23

long int n;
scanf("%d",&n);
double d;
d=(0.4472)*pow(1.6180,n-1);
printf("%0.lf",d);

This will work

24

No it does not work fail for large values @anon55659401 look into this

25

this is very nice :slight_smile:

1 Like
26

Yeaah! :slight_smile:

27

I used it in a contest where n<=10^18, and I got AC :slight_smile:

28

ig this one is better than fast doubling as it can be easily applied to diff variations of this que.
As @prmondal said

29

But I think in your exam time limit is more bcz 10^18 is very big range…

30

Time limit was 1 second. It was HMC contest, I guess even Abdullah used the same code in that contest. I’ll check it out :slight_smile:
Log(10^18) is not that time consuming :slight_smile:

31

But how can u implement sieve of this long range

32

We are calculating fibonacci numbers, not prime numbers…

33

Oh sry sry…wrong context…