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.
@ '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'.
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.
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. :)
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
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).
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.
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.
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.
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.
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 .
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.
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 ! :(
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
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.
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!
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 :)
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?
Its always that one Indian person that explains it better than your learning materials and the teacher combined
6 years later, and still the best video explaining this on youtube!
Thank you!
You’ve been the first and the best to clearly explain the math behind fast Fibonacci matrix computation .
Thanks!
Wow! Thank you for making it so simple to understand. This was the clearest explanation of matrix exponentiation.
when the yellow tee turns blue magically! nice video though :)
Haha :-P
Thanks Shreya!
also he wore spectacles
I loved the Maths involved into this problem, fascinated!
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.
Thanks Prakhar!
The best explanation for this on the internet
Thanks bhai....
People like you help guys ,those are not from good colleges in ind.. to improve their competitive programming skills......
Not even the best of colleges in India teach any Competitive Programming.
@ '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'.
the channel I should have found a year ago. Awesome explanation.
Thanks! 😁
Best Explanation so far with reason behind each and every step! Loved it... Thank you Sir.. ♥
Learning a lot from your videos, they are unlike any other sources available for competitive programming...
Thanks Saransh!
It really helped me understand how to apply Matrix Exponentiation for my particular problem. Great video, thanks!
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.
Yes, you are correct but in the beginning of this video, he assumed both f(1) and f(0) equal to 1.
This video needs a lot more likes than just hundreds
I agree 😉
This is amazing! It's so satisfying to watch this.
The way your eyes shined, when you said THE MATRIX !
NEO FOREVER
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. :)
Thanks Abhishek :-)
Great Teaching. Your energy is very engaging to the viewer and your explanations are clear and intuitive.
6 years later also helping many of us
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
Excellent!
It's helpful.Good work brother.
From Bangladesh ❤
what an explanation sir, MIND BLOCK
Wow solid explaination!!! Very easy to understand
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).
Goat explanation 🐐🐐
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.
Less coffee or more meditation, enhances calm during explanation.
Great video Gaurav! Please keep posting such wonderful videos. Thanks a lot!
amazing and very informative video, thanks
You are Simply Genius.. man..
Elegantly explained bro!
Thanks a lot
Thanks!
Thanks for this video. It helped me in gaining good insights for the approach to this problem.
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.
Exactly this depth all we need... tx brother
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.
Thanks Vidit!
Bless you Gaurav. Thank you
such a great explination !!!! thanks broo
Great video .. I saw some other video on the same topic but it was not engaging like this one ... ✌️🔥
Should have this channel earlier. Very concise and useful explanation :)
Wonderful teaching brother, keep it up. Helped a lot. Many thanks.
Really great explanation
Thank you 😁
Great tutorial!
matrix exponentiation is very useful in solving such linear recurrences in dp problems.
Thanks Akash!
Thank you Gaurav 💌
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.
great explanation brother
Nice explanation bro...
very cool intro GKCS!
Nice Explanation. Keep up the good work.
Thanks Sourya!
Very good explanation. Thanks !!
Thanks!
Very good explanation
Very well explained. Thanks for sharing.
Great explanation
Amazing video sir👍
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 .
You won't get the exact number using this, but you will get an approximation.
Loved this explanation!
You've explained it wonderfully. Wow!
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 ?
Enjoyed it, thank you!
Cheers!
Good efforts bro..keep it up
Thanks!
Awesome explanation
Keep up this great work
Thanks a lot broo👍
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.
What is the full form of SICP?
Any topic become interesting when it's you 😁 also those spects give me granny vibes😄🤫
Thanks😍
😂😉
Amazing explanation dude:)
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 ! :(
Hey Vasanth, thanks for the feedback 😁
This link will help explain the logn bits:
qr.ae/TWyJOx
Great teaching skill bro...
In which order i will multiply the matrix?? If i take the reverse order is it correct??
Amazing bro. Very nicely explained. Have been struggling to calculate fibonacci term efficiently.
Glad it helped :-)
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
Thanks, Gaurav !! Nice Explanation.
Thanks Ankit!
Why it is showing class not found exception when i ran the code in github in online IDE for JAVA ?
Lmgtfy.
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).
If the size is a constant, it can be assumed to be constant. N cube for 3 is a constant: 27 :)
Yeah thank you 😊😊.
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.
Good idea 👍
Thanks bro , helped me solve medium level ( broken clock ) problem of this feb18 long !
+Purvam Pujari Awesome!
lol
17:45 "Both of them will be 1 and 1"
How to multiply those 2 matrices [1 1] x [f(n-1) f(n-2]?
that an awesome explanation, thankyou for the video
12:04 The Matrix XD , you are the chosen one.
why did you added f(n-1) there, what is the need? at 4.21 time and even if we did why not take f(n-2) why only f(n-1)
What's the recursion? Think over it.
@@gkcs if we want to multiply 2*2 only take f(n) and f(n-2) , will it affect my result
Nice Video And good explanation :) liked it a lot :)
Thanks Misu :-)
How do we find the matrix to be "exponentiated" in different questions?
thanks, very well explaned
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!
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 :)
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?
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?
@@ronaldvonk yup 😁
Like: the actual stored values in the matrices too?
Very nicely explained. Thank you
+Monideep De Thanks!
Thanks alot for this video. Immensely helpful and love your passion while explaining the problem. Newly created fan :D
Damn, I wish I had teachers like this in college.
Will this algorithm work if you change the first two terms of the sequence say f(0)=2 and f(1)=3
@Gaurav Sen
Yup, it will. Of course, your sequence will change accordingly. You can try the code in the description
very well explained
hi, shouldn't matrix^0 be an identity matrix?
Very helpful!
Sequences of threes? Wow that's the holy trinity. My mind is blown and im agnostic
good explanation
can we make the matrix diagnolised so that the time complexity can be further reduced??
Won't matter much, as the overall complexity will still be the same.
You are doing great work!
good job Sir
Thanks for this amazing video...
can u post the link of code??
FIBOSUM on spoj..
Man that was so good
+Subhajit Das Thanks!
i m the one jiko samaj nhi bhyia when that level will come jub ye videos easily samaj aa jaige fcu..
Thank You❤