Solving the Fibonacci Sequence with Matrix Exponentiation

[@killuazoldyck7705]

Its always that one Indian person that explains it better than your learning materials and the teacher combined

[@alessandrocamillo4939]

You’ve been the first and the best to clearly explain the math behind fast Fibonacci matrix computation .

[@gkcs]

Thanks!

[@ITACHIUCHIHA-dr8sz]

6 years later, and still the best video explaining this on youtube!

[@gkcs]

Thank you!

[@shreyasahu481]

when the yellow tee turns blue magically! nice video though :)

[@gkcs]

Haha :-P Thanks Shreya!

[@abhaypatil2000]

also he wore spectacles

[@shreyaghosh2956]

Wow! Thank you for making it so simple to understand. This was the clearest explanation of matrix exponentiation.

[@manishankar1593]

I loved the Maths involved into this problem, fascinated!

[@iprakhar22]

Appreciate your work a lot, Man! Something I like about you is that you choose your words very carefully before speaking just so that every kind of audience can understand you.

[@gkcs]

Thanks Prakhar!

[@vidhansharma1787]

Thanks bhai.... People like you help guys ,those are not from good colleges in ind.. to improve their competitive programming skills......

[@Speak4Yourself2]

Not even the best of colleges in India teach any Competitive Programming.

[@Speak4Yourself2]

@ 'coDiNG cULtUre' starts from You. When you code, (and code well, with time and practice) your friends/juniors are inspired to follow in your footsteps. Over the years this inspiration spreads as a ripple effect batch after batch. Then the college calls itself as having good 'coDiNG cULtUre'.

[@subhodip5293]

Great Teaching. Your energy is very engaging to the viewer and your explanations are clear and intuitive.

[@theIcemanYT]

the channel I should have found a year ago. Awesome explanation.

[@gkcs]

Thanks! 😁

[@atulsaswat1153]

At 17:45, when we do the final multiplication, we should consider f(1) = 1 and f(0) = 0 giving us f(14) = 377 & f(13) = 233. That doesn't defeat the purpose of the understanding though. Your explanations have a good buildup and that is probably why it's so appealing.

[@rishavsaha5254]

Yes, you are correct but in the beginning of this video, he assumed both f(1) and f(0) equal to 1.

[@ashishchourasia2830]

The best explanation for this on the internet

[@andermerketegi1177]

It really helped me understand how to apply Matrix Exponentiation for my particular problem. Great video, thanks!

[@FeroChau]

This is amazing! It's so satisfying to watch this.

[@tanishq2766]

The way your eyes shined, when you said THE MATRIX ! NEO FOREVER

[@akhilesh59]

Best Explanation so far with reason behind each and every step! Loved it... Thank you Sir.. ♥

[@saranshdabas4223]

Learning a lot from your videos, they are unlike any other sources available for competitive programming...

[@gkcs]

Thanks Saransh!

[@NiceBot724]

This video needs a lot more likes than just hundreds

[@gkcs]

I agree 😉

[@abhishekkarn8918]

I can add one thing here if anyone is stuck until what power do we have to calculate the powers: just do: 2^(floor(ln(n)) and you will get the required number. For n=13, you will get 2^3, which is 8. Hope it proved to be of some help. And Thanks a Lot Gaurav for such a brilliant video. You are literally one of the best. :)

[@gkcs]

Thanks Abhishek :-)

[@adoq]

i was just looking for a way to find fibonacci numbers quickly with pen and paper, i didnt get my answer but i got valuable dynamic programming knowledge lol. works either way

[@gkcs]

Excellent!

[@Rajat_maurya]

6 years later also helping many of us

[@viditmathur8437]

your explanations are awesome , I really like the mathematical explanations . This video really helped me understand the log(n) approach to find fibonacci sequence which i couldn't understand from texts :D.

[@gkcs]

Thanks Vidit!

[@LuisaGrigorescu]

Great explanation! You made math much easier to understand. All the explanations from the internet are to mathematical and imply having prior knowledge to all these terms and formulaes.

[@dugong369]

For those who aren't aware, storing the lower powers isn't needed (see wikipedia article on Exponentiation by Squaring for example). Following a sequence of squaring and multiplication determined by the binary bits of the exponent eliminates the need to store those intermediate results. It's probably better that you explained it the way you did though because that avoids a complication which isn't relevant to the main point, O(log n).

[@Manojshankaraj]

Great video Gaurav! Please keep posting such wonderful videos. Thanks a lot!

[@udaysaiphanindra3138]

what an explanation sir, MIND BLOCK

[@ZMacZ]

Less coffee or more meditation, enhances calm during explanation.

[@abhimanyubahree1455]

Wow solid explaination!!! Very easy to understand

[@securityintech]

at 4:20 I don't understand why do we require f(n-1) in the matrix, if the conditions are satisfied, we got [1 1] and f(1) and f(0), both of them are 1x2 and 2x1 matrix, resulting will be 1x1.

[@aayush_dutt]

Elegantly explained bro! Thanks a lot

[@gkcs]

Thanks!

[@amoghdesai9138]

Should have this channel earlier. Very concise and useful explanation :)

[@sohanursohan2426]

It's helpful.Good work brother. From Bangladesh ❤

[@MegaAkash123456]

Great tutorial! matrix exponentiation is very useful in solving such linear recurrences in dp problems.

[@gkcs]

Thanks Akash!

[@themusicalmonk2732]

You are Simply Genius.. man..

[@fenil861]

Thanks for this video. It helped me in gaining good insights for the approach to this problem.

[@khudkikhoz]

Exactly this depth all we need... tx brother

[@parth7300]

Goat explanation 🐐🐐

[@Chesstreamer]

Just scrolling through your videos and bazzinga, found this fibonacci video,i have once used the code without understanding it somewhere on codechef but now i have understand it thoroughly,very simple and lucid exlplanation of yours helped me a lot.can u do some more problems on dp like state reduction and those involving trees tha would be of great help

[@beonthego8725]

Bless you Gaurav. Thank you

[@vijaypratap356]

bro i am frustated from data structure and algorithm but there is some which does not let it go.when i will see ur videos they encourages me to learn but i dont know what exactly to learn for understanding complex problems of ds and algo.how do you solve the problems in minutes thats really amazing.

[@shaswatdas6553]

17:45 "Both of them will be 1 and 1"

[@uarangat]

Wonderful teaching brother, keep it up. Helped a lot. Many thanks.

[@xiquandong1183]

Very good explanation. Thanks !!

[@gkcs]

Thanks!

[@purvampujari]

Thanks bro , helped me solve medium level ( broken clock ) problem of this feb18 long !

[@gkcs]

+Purvam Pujari Awesome!

[@travelinGuitarist]

lol

[@jayshree9037]

Any topic become interesting when it's you 😁 also those spects give me granny vibes😄🤫 Thanks😍

[@gkcs]

😂😉

[@sivasainagireddi7956]

such a great explination !!!! thanks broo

[@siddhantsharma7107]

You've explained it wonderfully. Wow!

[@sumit-kushwah]

Thank you Gaurav 💌

[@beautifultime9031]

Very well explained. Thanks for sharing.

[@Snehaa2296]

very cool intro GKCS!

[@ManishKumar-kw7qe]

Great explanation

[@kiransfitnesstips4095]

Nice explanation bro...

[@rethink20s]

Great teaching skill bro...

[@RapartiChaitanya]

Loved this explanation!

[@sunnysam69]

Amazing bro. Very nicely explained. Have been struggling to calculate fibonacci term efficiently.

[@gkcs]

Glad it helped :-)

[@nazrulhassan6310]

great explanation brother

[@shaziasamreen8584]

Very good explanation

[@BluEx22329]

Sequences of threes? Wow that's the holy trinity. My mind is blown and im agnostic

[@TravellerMann]

Good efforts bro..keep it up

[@gkcs]

Thanks!

[@AmanSharma-hi3fd]

12:04 The Matrix XD , you are the chosen one.

[@sarcaastech]

Great video .. I saw some other video on the same topic but it was not engaging like this one ... ✌️🔥

[@91vasanth]

Wonderful explanation Gaurav. That smile at 18:19 haha ! And I have one doubt from that point. How did you say that to raise to the power we just took log(n) time? and you also said something about the number of bits to represent that number. Could you please explain me this? I was so satisfied with the understanding until I arrived at this point ! :(

[@gkcs]

Hey Vasanth, thanks for the feedback 😁 This link will help explain the logn bits: qr.ae/TWyJOx

[@ravirayal7590]

amazing and very informative video, thanks

[@souryasaha4001]

Nice Explanation. Keep up the good work.

[@gkcs]

Thanks Sourya!

[@angshumanbhowmik1020]

Amazing video sir👍

[@srijanpaul]

I remember this from the book SICP! It was an exercise in the first chapter iirc. I saw the solution on community scheme wiki and was very impressed by this way of thinking about the problem.

[@omshree901]

What is the full form of SICP?

[@the_dark_kerm]

Really great explanation

[@gkcs]

Thank you 😁

[@prathameshautade2679]

Amazing explanation dude:)

[@tarunpatel8168]

that an awesome explanation, thankyou for the video

[@ronaldvonk]

Very nice explanation and nice correction :-). The only thing is: even though this way of calculation may seem efficient; the total sum wil rise exponential and will be difficult to hold in memory; even for low values of N!

[@gkcs]

Yes that's true, although most of the questions around this have us taking a remainder of the result. So ans % m turns out to be small enough to fit in memory :)

[@ronaldvonk]

But you will store every 2^N th step of the Fibonacci sequence in memory, right Gaurav Sen? The 2^3=8th step is only [[34,21],[21,[13]] , but the 2^5=32th step is already [[3.524.578, 2.178.309],[2.178.309, 1.346.269]] and rising exponential; resulting is a lot of digits. Which step will you take the modulo m and with what purpose?

[@ronaldvonk]

But you certainly gave me an idea for storing these exponential rising values as (mod 2^k) :-D. This may do the trick. Is that what you meant?

[@gkcs]

@@ronaldvonk yup 😁

[@ronaldvonk]

Like: the actual stored values in the matrices too?

[@9871aa]

If you set F(0) = 0, like wikipedia says, you could have even a simpler algorithm: raise matrix to the n-th power and get the 1-st row, 1-st column element.

[@gkcs]

Good idea 👍

[@rajatparab8116]

Awesome explanation Keep up this great work Thanks a lot broo👍

[@manthankhorwal1477]

Why can't we use implementation of pow function to modify it to directly calculate for matrix same as we do it for a number ?

[@arreankit]

Thanks, Gaurav !! Nice Explanation.

[@gkcs]

Thanks Ankit!

[@kautukraj]

Very helpful!

[@joshua_dlima]

Enjoyed it, thank you!

[@gkcs]

Cheers!

[@vanshgupta24]

the curious thing about fibonacci is that every fibonacci is golden ratio times bigger than the previous fibonacci , like 8 and 5 are in the ratio of 1.6 or 8 is golden ratio times bigger than 5. early numbers dont show it but eventually the pairs starts to converge to golden ratio, so for any large n the fibonacci is phi raised to some expnonent of n (check yourself). so you can just return pow(phi,n)*base , base here is any suitable fibonacci number that has significantly converged, and n is new shifted target .

[@gkcs]

You won't get the exact number using this, but you will get an approximation.

[@KaranDoshicool]

very well explained

[@wedonotgogymnow]

How to multiply those 2 matrices [1 1] x [f(n-1) f(n-2]?

[@tanvirahmed-vu2xy]

In which order i will multiply the matrix?? If i take the reverse order is it correct??

[@ankitmishra-dp9tx]

Thanks alot for this video. Immensely helpful and love your passion while explaining the problem. Newly created fan :D

[@zaid6527]

thanks, very well explaned

[@mansinawani8970]

Thanks for this amazing video...

[@monideepde7413]

Very nicely explained. Thank you

[@gkcs]

+Monideep De Thanks!

[@rahulsaxena5015]

How do we find the matrix to be "exponentiated" in different questions?

[@umangbehl8152]

good explanation

[@Pro3512]

Why it is showing class not found exception when i ran the code in github in online IDE for JAVA ?

[@gkcs]

Lmgtfy.

[@misudey3281]

Nice Video And good explanation :) liked it a lot :)

[@gkcs]

Thanks Misu :-)

[@ktxh]

hi, shouldn't matrix^0 be an identity matrix?

[@khalilshaik6161]

thanks dude!

[@letsghoomo]

good job Sir

[@longvu2033]

very nice explanation =))

[@neosapien247]

Damn, I wish I had teachers like this in college.

[@sivanipentapati5538]

can u post the link of code??

[@harshsrivastava5255]

FIBOSUM on spoj..

[@amankumarkashyap400]

How can matrix multiplication be O(1) ?? let's assume that we are multiplying two n*n matrices ,than the time complexity will be O(n^3).

[@gkcs]

If the size is a constant, it can be assumed to be constant. N cube for 3 is a constant: 27 :)

[@chalapathinagavarmabhupath8432]

Yeah thank you 😊😊.

[@priyabratamallick7629]

Hey Gaurav , It is a wonderful explanation, but I found a small flaw in the explanation. i.e. f(14) is 377 not 610 and f(13) is 233 not 377. We are getting it wrongly beacuse you have considered f(0)=1 which is actually 0. Anyway thanks of your nice work dude.

[@gkcs]

Thanks Priyabrata!

[@karthikrockrr]

Mind blown !

[@mandavasairaghavendradines6582]

Hey, great explanation. Nowadays you are doing more of system design stuff. I think once a while you can also post more these kind of videos

[@gkcs]

More to come!

[@mandavasairaghavendradines6582]

cool, keep going!!

[@jayseagal3681]

Thank you so much bro

[@subhajitdas2784]

Man that was so good

[@gkcs]

+Subhajit Das Thanks!