Please, keep continuing creating these videos. You will eventually get more subs. And thank you so much for creating these wonderful tutorials keeping competitive programming in mind. We will be waiting for more :-)
Some people have correctly pointed out there is more that can be done on this topic, but I think it is a great first video or introduction. I find a nice balance between geniuses trying to show us things where there are tons of things that are just obvious to them but not to the viewers, and watching regular dummies plod thru something they barely understand. I did need to watch this. I was working on a solution without recursion that saved some stack space (who cares) but was significantly harder to code....
I just got started with CP and before diving directly into pool of codechef question, i needed to get my basics strong. Just a week back LOVE BABBAR uploaded a video describing all necessary maths required before actually solving questions. So he told to checkout fast exponatiation and here i am. It’s really good i must say. I got each and every point clearly. Keep posting good stuff sir. :)
Summary for non-modulo exponentiation x^0 = 1 x^1 = x x^e = ( IF e modulo 2 congurent 0 THEN (x×x)^(e/2) ELSE x × x^(e-1) ) Calculates in less steps than multiplying x*x...*x e-times: e steps vs ~ log 2 e steps Uses: x^e = x^(2*e/2) = (x^2)^(e/2) Since roots are expensive to calculate for either computer or human mind we want the exponent to stay in IN, and do a little if-case instead to keep e divisible by 2.
Summary for modulo exponentiation Term (1) x^e % m Similar idea to half exponent, calculate this instead: Term (2) ((x^(e/2) % m)*(x^(e/2) % m)) % m = (x^(e/2) % m)^2 %m Just have to prove that this is equal to x^e%m. x^(e/2) % m congurent r => x^(e/2) = m * k + r; r 0 x^1 % m -> x%m x^e % m -> ( IF e % 2 congurent 0 THEN (x^(e/2) % m)^2 % m ELSE (x%m)*(x^(e-1)%m) % m ) I'm using this modulo rule for ELSE case a % b congurent c d % b congurent e ad % b congurent ce
There is a more elegant way to calculate power modulo which simply refines the idea: x^e%m := Convert e to binary = list ebin d = 1 FOR (b in ebin) DO ( d = d^2 % m IF (b == 1) THEN d= d*x%m ) RETURN d
Wonderful video sir, but marker wasn't that visible. Good job sir, keep inspiring us and create such beautiful content. CP beginners and curious minds need such videos.
a^n%m = ((a%m)*n)%m Example: 8^8%6 = ((8%6)*8)%6 = (2*8)%6 = 16%6 = 4 Something I got while thinking about this problem statement, didn't really think of all the corner cases though.
You are like a super computer who thinks quickly. (but quiet slow at addition. XD). You explain it to us after number of times of practices so that you may understand the steps you are writing and you can co-relate them easily. But viewers who are new to this concepts are looking for some clear and patient explanation. Please bring that Gaurav. My kind suggestion and request:) Because I find your videos are damn useful and I want you not to lose any fellow students of your teaching.
That was really cool! Maybe a little bit more in depth examples would have guided me (a novice) to better understanding! but I researched into the matter for better understanding! Anyway, Thank you for a great explanation!
For Fast exponentiation mostly used in cryptography with some modulus work. So solving this would depends upon choice of either Fermat , FEMA or Euler is preferable.. Implementation could be like yours with some memoization techniques. You have explained a just small bite of it.
Very Nice Explanation !! Just one doubt when its N is odd , we should take the floor value so i guess the component R which is (N/2) should also demand for a code changes as R is now floor(N/2) ?
i didnt understand one thing.. in that code, you wrote R=pow(a,N/2)... but wouldnt that take the program back to the same function even before the lines that are written below are executed?
Thanks for the feedback Arpit! This approach is pretty efficient, O(log(N)) is the best we can hope for. There is another approach which is more often used, called binary exponentiation. I will get to that soon :-)
Hi Gaurav, For aⁿ%b algo, don't u think this might be faster? 👇 aⁿ%b = (a²%b)ˆn/2 %b This too runs in O(logn), but may return pretty quick sometimes, when 'a' becomes 1 due to the impact of the modulus operator Cud u please comment?
I went through the code and saw that you have used int and long. As you said in video, What happens if a^N crosses the long and int limits.? Can you please make the changes in code or probably make a video on designing a data structure to store data which is of very high precision integer number like 10^10000 or may be more the. That.
Biginteger stores very large values, but the point where this technique is useful is when exponentiating while taking a remainder. Like 10^1000 mod 47.
That might take O(n) time. Internally, the pow(number, n) function is using a slower algorithm to compute the exponent, at least in Java. This method computes in O(log(N)) time.
Can you please explain the iterative version of the code, private static long power(long x, long y, long m) { long ans = 1L; while (y>0) { if ((y&1)==1) { ans = (ans * x) % m; } y = y>>1; x = (x * x) % m; } return ans % m; }
Hey Amit, I just read up quite a bit on the soft heap data structure. And while it has interesting properties, it isn't practically applicable. So, for now, I will keep from making the video :-) If you want some good sources to learn about them, here are a few links: stackoverflow.com/questions/26126170/soft-heaps-what-is-corruption-and-why-is-it-useful www.cs.princeton.edu/~chazelle/pubs/sheap.pdf Cheers!
Hey @Gaurav sen I would be happy if you take some time and reply for this. I have studied Engineering in a local state college. It's been around 2 months I joined in a company, which pays me 7Lpa. I know that this is not a good package but for local college guys its a very good package ( coz avg package in local colleges is 3.5Lpa and I know avg is around 10+ in NIT's, IIT's). Where I'm right now: ---------------- - Coding: Need to learn trees, graphs, Dp and standard/repeated/imp algorithms - Projects: I didn't do any projects till now ( like no development at all). - Technologies: I know java, .net, angular, c# So can someone tell me what are all the required things to learn for getting placed in a Good company ( SDE1,2 role ), How to get Interview calls or Interview chances from good companies. And especially what strategy(like time and hours per day) I should be following to achieve it. I would be thankful for any advice or any video or article link regarding this.
5 лет назад+1
@@chandrahas2567 refer quora for such suggestions . do we development like learn about html +css , js , nodejs, npm , js frameworks, js libraries ,webpack, database (mongodb), docker , etc...
Supriyanta Poddar, you can't. That question is often asked in competitive programming, so the second technique talks about it. If you want a^b, you need to use the first technique.
I think u should learn english 1st thomas if u cant understand such clear english. Pehaps u hv learnt hebrew in place of english . You belong to that class of people who do not hv any work and see videos only to comment rubbish
Please, keep continuing creating these videos. You will eventually get more subs. And thank you so much for creating these wonderful tutorials keeping competitive programming in mind. We will be waiting for more :-)
Thanks!
Now he has pi lakh subscribers
The energy you put in every video is inspiring .
Such creativity in programming with new chef in middle of this competition is worthwhile notation.Thanku Gaurav.
Thanks :-)
This the best explanation of fast exponentiation by far! Thank you.
Some people have correctly pointed out there is more that can be done on this topic, but I think it is a great first video or introduction. I find a nice balance between geniuses trying to show us things where there are tons of things that are just obvious to them but not to the viewers, and watching regular dummies plod thru something they barely understand. I did need to watch this. I was working on a solution without recursion that saved some stack space (who cares) but was significantly harder to code....
Brilliant brother just brilliant your energy, enthusiasm and pedagogy are second to none for DSA on RUclips I love you keep it going 👌❤️
Thank you 😁
I just got started with CP and before diving directly into pool of codechef question, i needed to get my basics strong. Just a week back LOVE BABBAR uploaded a video describing all necessary maths required before actually solving questions. So he told to checkout fast exponatiation and here i am. It’s really good i must say. I got each and every point clearly. Keep posting good stuff sir. :)
I am here fron love babbar vid too although i have been here from a long time too
You have explained this method very nicely and i have understood it in no time
Thank you sir, You are helping me a lot to improve my programming skills.
Thank you, Mr. Sen. Please continue to post more tricks in fast computations.
Thanks!
Watched multiple times but finally got it..thanks Gaurav bhai✌🙂
Please post more videos and we will continue to share so that the channel increases popularity
great explanation for divide and concur algorithm and fast exponent
Summary for non-modulo exponentiation
x^0 = 1
x^1 = x
x^e = (
IF e modulo 2 congurent 0
THEN (x×x)^(e/2)
ELSE x × x^(e-1)
)
Calculates in less steps than multiplying x*x...*x e-times: e steps vs ~ log 2 e steps
Uses: x^e = x^(2*e/2) = (x^2)^(e/2)
Since roots are expensive to calculate for either computer or human mind we want the exponent to stay in IN, and do a little if-case instead to keep e divisible by 2.
Summary for modulo exponentiation
Term (1)
x^e % m
Similar idea to half exponent, calculate this instead:
Term (2)
((x^(e/2) % m)*(x^(e/2) % m)) % m = (x^(e/2) % m)^2 %m
Just have to prove that this is equal to x^e%m.
x^(e/2) % m congurent r => x^(e/2) = m * k + r; r 0
x^1 % m -> x%m
x^e % m -> (
IF e % 2 congurent 0
THEN (x^(e/2) % m)^2 % m
ELSE (x%m)*(x^(e-1)%m) % m
)
I'm using this modulo rule for ELSE case
a % b congurent c
d % b congurent e
ad % b congurent ce
There is a more elegant way to calculate power modulo which simply refines the idea:
x^e%m :=
Convert e to binary = list ebin
d = 1
FOR (b in ebin) DO (
d = d^2 % m
IF (b == 1) THEN d= d*x%m
)
RETURN d
Thank you so much for making this effort and sharing your knowledge with us ,It's of great help
Thank you, Gaurav Sen! A very good tutorial!!
Wonderful video sir, but marker wasn't that visible.
Good job sir, keep inspiring us and create such beautiful content.
CP beginners and curious minds need such videos.
Thanks Samarth!
a^n%m = ((a%m)*n)%m
Example:
8^8%6 = ((8%6)*8)%6 = (2*8)%6 = 16%6 = 4
Something I got while thinking about this problem statement, didn't really think of all the corner cases though.
Yes. We use this to keep the range within 32 bits.
Basically, you have shot this video on different days. By the way Great content
You are like a super computer who thinks quickly. (but quiet slow at addition. XD). You explain it to us after number of times of practices so that you may understand the steps you are writing and you can co-relate them easily. But viewers who are new to this concepts are looking for some clear and patient explanation. Please bring that Gaurav. My kind suggestion and request:) Because I find your videos are damn useful and I want you not to lose any fellow students of your teaching.
I'll try and do that 😛
Thanks! you made it easier to understand
Thanks!
That was really cool! Maybe a little bit more in depth examples would have guided me (a novice) to better understanding! but I researched into the matter for better understanding! Anyway, Thank you for a great explanation!
For Fast exponentiation mostly used in cryptography with some modulus work. So solving this would depends upon choice of either Fermat , FEMA or Euler is preferable.. Implementation could be like yours with some memoization techniques. You have explained a just small bite of it.
Excellent video. Your explanation is on point.
Waao that's awesome guru👍👍👍
Thank you so much for this bro you are such an inspiration
Thank you, very well explained
Very Nice Explanation !! Just one doubt when its N is odd , we should take the floor value so i guess the component R which is (N/2) should also demand for a code changes as R is now floor(N/2) ?
We can do a P*P*x in that case, where x is the base and P the current product.
thanx for the channel sir... helping a lot... keep unloading please....
mayukh Sengupta Thanks!
sir please try to post a video on introduction to dynamic programming in near future... would be gr8 help... :-)
I did understand the logic behind finding subset using bit .Would you make a tutorial on it. Plss
what is the range of M in the % code ???
Your videos are great!!!..I'm a newbie in cp and these are really helpful :-)
If anybody wants a problem on this topic
Here is the link :
www.codechef.com/JUNE19B/problems/RSIGNS
Welcome :)
Sir ,at last why don't you mod a in recursion with m in else case(when N/2 is odd)..15:27
Thank you!, your video helped me a lot to understand better
Thanks!
Very Nice Explanation
i didnt understand one thing.. in that code, you wrote R=pow(a,N/2)... but wouldnt that take the program back to the same function even before the lines that are written below are executed?
Really good explanation
Thanks!
Thank you! I understand!💖
Thanks, keep making videos I am sure you will earn more subscribers gradually.
Thanks Vikram!
Maza aa Gaya..❤️
For Python, what is the time complexity of n**m ?
More efficient approaches please !!!
concept explanation was good.
Thanks for the feedback Arpit!
This approach is pretty efficient, O(log(N)) is the best we can hope for. There is another approach which is more often used, called binary exponentiation. I will get to that soon :-)
The same is given on GFG, but I understood it here.
If power is 50000,, then how u do the such big power though divide by 2,50000/2 can't calculate by power (2,25000)
The value of log 10 base 2 = 3.32.
So log (10^12) base 2 = 12*log (10) base 2
= 12*3.32 = 39.84 ≈ 40
Thank you Gaurav, this helped!
That's a really useful video.
Thanks for the video. It was helpful
while am doing pow(2,1000000005) it is giving me some different number 180942713 ??
can anyone help me out
Hi Gaurav,
For aⁿ%b algo, don't u think this might be faster? 👇
aⁿ%b = (a²%b)ˆn/2 %b
This too runs in O(logn), but may return pretty quick sometimes, when 'a' becomes 1 due to the impact of the modulus operator
Cud u please comment?
Thank you for the explanation of Fast Modulo, really helpful !! It could have been better with an example .
I went through the code and saw that you have used int and long. As you said in video, What happens if a^N crosses the long and int limits.? Can you please make the changes in code or probably make a video on designing a data structure to store data which is of very high precision integer number like 10^10000 or may be more the. That.
Biginteger stores very large values, but the point where this technique is useful is when exponentiating while taking a remainder.
Like 10^1000 mod 47.
Gaurav Sen got you.! appreciate the quick response. Keep up the good work Buddy :)
You sir ,just earned a subscriber
Sometimes students watch in a hurry ,this could be more precise and short
I am interested to know how did you calculate 2 power 30 to be around 1 billion so quick. Is it memory or some trick?
It's memory.
I know that 2^10 is 1000,
Double that exponent and you get a million.
Triple it to get a billion.
how do we find M for a particular 'a' and 'n'
M is part of the problem statement. It is usually a large prime number.
Please post a video solution of COOK-82B.
I am not able to understand how to get such ideas in maths questions.
Please make one :)
Hey Nikhil, will look into it :)
Hey, thanks but I understood the approach.
Not worth making a video :P
Thanks this was quite helpful
very nice explanation thank you!
Thanks Jade!
More problems on dp and graphs bro , Thankyou !
def my_pow(self, x: float, n: int) -> float:
if n < 0: return self.my_pow(1/x, -n)
if n == 0: return 1
half_pow = self.my_pow(x, n // 2)
return half_pow * half_pow * (1 if n % 2 == 0 else x)
Thank you so much brother.. this helped a lot :-)
isn't it the big mod ?? or am I mixing up things ?
What is the complexity of Math.pow(),? Why can't we simply use it in the case when we don't need to perform %M?
Math.pow has a complexity of order n.
@@gkcs it also allow power upto 10^5
@@rohanjain4238 Try it in a contest then 😂
@@gkcs i here to support you man 👍
@@rohanjain4238 Ah, sorry I misunderstood 😛
i didnt get one main thing why do we even need to to split??if we can just use that number raised to the power n.
How will you find it to the power n, first? :)
Gaurav Sen By the use of pow (number,n)function
That might take O(n) time. Internally, the pow(number, n) function is using a slower algorithm to compute the exponent, at least in Java.
This method computes in O(log(N)) time.
Gaurav Sen thank-you Gaurav :) . Just one more question I wanted to know if it makes any difference in c++?
Can you please explain the iterative version of the code,
private static long power(long x, long y, long m) {
long ans = 1L;
while (y>0) {
if ((y&1)==1) {
ans = (ans * x) % m;
}
y = y>>1;
x = (x * x) % m;
}
return ans % m;
}
You are extremely smart
what if N is negative
Thanks Bro, It really help me
helpful video sir
Thanks!
in the proof for the identity with mod ,why u wrote r squared mod m instead of r mod m+r mod m?
We are finding the exponent using multiplication. The identity is ((a+r)*(a+r))%m.
The videos was great but the marker was not visible sometimes and also the lighting issue!! Anyways Keep it up
Hi Harshit!
Thanks for noting that, I will keep that in mind next time!
Can you make a tutorial on soft heap..Please?
+Amit Swami Sure! Will add that to the list :-)
Hey Amit, I just read up quite a bit on the soft heap data structure. And while it has interesting properties, it isn't practically applicable. So, for now, I will keep from making the video :-)
If you want some good sources to learn about them, here are a few links:
stackoverflow.com/questions/26126170/soft-heaps-what-is-corruption-and-why-is-it-useful
www.cs.princeton.edu/~chazelle/pubs/sheap.pdf
Cheers!
Hello sir can u upload a tutorial on FFT??
Hi Kashyap!
FFT looks tough! I am adding that to the list, but I can't promise anything on that soon :-/
it is simply suberb,excellent!!
Thanks Sunil!
Very helpful !
Finally solved like a true engineer : lol
Hey @Gaurav sen I would be happy if you take some time and reply for this.
I have studied Engineering in a local state college. It's been around 2 months I joined in a company, which pays me 7Lpa.
I know that this is not a good package but for local college guys its a very good package ( coz avg package in local colleges is 3.5Lpa and I know avg is around 10+ in NIT's, IIT's).
Where I'm right now:
----------------
- Coding: Need to learn trees, graphs, Dp and standard/repeated/imp algorithms
- Projects: I didn't do any projects till now ( like no development at all).
- Technologies: I know java, .net, angular, c#
So can someone tell me what are all the required things to learn for getting placed in a Good company ( SDE1,2 role ), How to get Interview calls or Interview chances from good companies. And especially what strategy(like time and hours per day) I should be following to achieve it.
I would be thankful for any advice or any video or article link regarding this.
@@chandrahas2567 refer quora for such suggestions . do we development like learn about html +css , js , nodejs, npm , js frameworks, js libraries ,webpack, database (mongodb), docker , etc...
can u plz upload Matrix Exponentiation & CRT ?
Working on Matrix Exponentiation now! Do you mean Chinese Remainder Theorem as CRT?
yes
excellent video
Thanks!
Finally, how could I get the value of a^N from (a^N%M)?????????? (For the last method)
Supriyanta Poddar, you can't. That question is often asked in competitive programming, so the second technique talks about it.
If you want a^b, you need to use the first technique.
okay...thanks....could you please help me find the factorial of nos more than 50 in C++ which are not fit in 8bit...!!!!!!
You could try the BigInteger class in C++. It allows operations on large integers by internally keeping an array of digits.
thanks...lets see... :)
Hi! Are yu wearing contact lens?
Now the question is.... why do I never think of these things?
good one !
Thanks!
Thanks sir
Thanks brother!!!
Awesome bro!!
Perfect!
Thanks Rohit!
Please explain Chinese reminder therom in RSA decryption
thanks
:-)
nice
AMAZING
todd!
Hiii 2**3 please tell me this type of question s
pow() sorry I am noob
Your Indian accent is so strong you should slow down so I can understand your English 🤔
I think u should learn english 1st thomas if u cant understand such clear english. Pehaps u hv learnt hebrew in place
of english . You belong to that class of people who do not hv any work and see videos only to comment rubbish
Thanks this was quite helpful
Thanks