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. :)
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).
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
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.
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.
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
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.
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 .
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?
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.
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 ! :(
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.
Hi tanishq, the video for that is already out! th-cam.com/video/OEthLiejmHk/w-d-xo.html I suggest you have a look upto the 18th minute. Thats contains the explanation of bitmask and dp.
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!
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'.
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.
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 :-)
Best Explanation so far with reason behind each and every step! Loved it... Thank you Sir.. ♥
the channel I should have found a year ago. Awesome explanation.
Thanks! 😁
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).
It really helped me understand how to apply Matrix Exponentiation for my particular problem. Great video, thanks!
The best explanation for this on the internet
Learning a lot from your videos, they are unlike any other sources available for competitive programming...
Thanks Saransh!
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!
The way your eyes shined, when you said THE MATRIX !
NEO FOREVER
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.
6 years later also helping many of us
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!
This is amazing! It's so satisfying to watch this.
This video needs a lot more likes than just hundreds
I agree 😉
Less coffee or more meditation, enhances calm during explanation.
Great Teaching. Your energy is very engaging to the viewer and your explanations are clear and intuitive.
what an explanation sir, MIND BLOCK
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 video Gaurav! Please keep posting such wonderful videos. Thanks a lot!
Bless you Gaurav. Thank you
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
It's helpful.Good work brother.
From Bangladesh ❤
You are Simply Genius.. man..
Wow solid explaination!!! Very easy to understand
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?
Thank you Gaurav 💌
Thanks for this video. It helped me in gaining good insights for the approach to this problem.
Exactly this depth all we need... tx brother
Should have this channel earlier. Very concise and useful explanation :)
Elegantly explained bro!
Thanks a lot
Thanks!
Great tutorial!
matrix exponentiation is very useful in solving such linear recurrences in dp problems.
Thanks Akash!
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.
Great explanation
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"
Wonderful teaching brother, keep it up. Helped a lot. Many thanks.
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 good explanation
Any topic become interesting when it's you 😁 also those spects give me granny vibes😄🤫
Thanks😍
😂😉
Goat explanation 🐐🐐
such a great explination !!!! thanks broo
great explanation brother
Nice explanation bro...
Great video .. I saw some other video on the same topic but it was not engaging like this one ... ✌️🔥
Really great explanation
Thank you 😁
very cool intro GKCS!
Very good explanation. Thanks !!
Thanks!
Sequences of threes? Wow that's the holy trinity. My mind is blown and im agnostic
Very well explained. Thanks for sharing.
You've explained it wonderfully. Wow!
Amazing bro. Very nicely explained. Have been struggling to calculate fibonacci term efficiently.
Glad it helped :-)
Enjoyed it, thank you!
Cheers!
Great teaching skill bro...
In which order i will multiply the matrix?? If i take the reverse order is it correct??
Loved this explanation!
thanks, very well explaned
amazing and very informative video, thanks
Nice Explanation. Keep up the good work.
Thanks Sourya!
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.
Thanks Priyabrata!
good explanation
Amazing video sir👍
12:04 The Matrix XD , you are the chosen one.
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
Awesome explanation
Keep up this great work
Thanks a lot broo👍
Thanks alot for this video. Immensely helpful and love your passion while explaining the problem. Newly created fan :D
that an awesome explanation, thankyou for the video
Amazing explanation dude:)
very well explained
Thanks, Gaurav !! Nice Explanation.
Thanks Ankit!
Good efforts bro..keep it up
Thanks!
Why it is showing class not found exception when i ran the code in github in online IDE for JAVA ?
Lmgtfy.
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 ?
hi, shouldn't matrix^0 be an identity matrix?
good job Sir
How do we find the matrix to be "exponentiated" in different questions?
Nice work. Your videos can not be viewed in 2x speed. you already speak so quickly 😁😜
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.
Very nicely explained. Thank you
+Monideep De Thanks!
Thanks for this amazing video...
How to multiply those 2 matrices [1 1] x [f(n-1) f(n-2]?
Very helpful!
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
More to come!
cool, keep going!!
Thank you so much bro
Good Video but you could try speaking a little slow next time. good job,
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
You can then use Cayley's - Hamilton's theorem on exponentiation for a linear solution to any Nth Fibonacci number 😜
yeah but with matrix exponentiation its logarithmic complexity.
Nice Video And good explanation :) liked it a lot :)
Thanks Misu :-)
very nice explanation =))
thanks for the video bro!...nicely done!!!! can you please make a tutorial on bitmask+dp.......it would be greatly appreciated
Hi tanishq, the video for that is already out!
th-cam.com/video/OEthLiejmHk/w-d-xo.html
I suggest you have a look upto the 18th minute. Thats contains the explanation of bitmask and dp.
thanks......to be honest I like your videos very much ,they are way better than tushar roy's ......keep up the good work bro :-).
can u post the link of code??
FIBOSUM on spoj..