Binary Exponentiation

Подписаться 306 тыс.

Просмотров 101 тыс.

50% 1

Binary exponentiation (or exponentiation by squaring) is an algorithm that quickly computes a big power a^b in O(log(b)). This tutorial for beginners includes the intuition, examples, and two C++ implementations: recursive and iterative. Check out cp-algorithms.... for articles on more advanced algorithms.
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
Github repository: github.com/Err...
Live streams on 2nd YT channel and on Twitch: / errichto2 & / errichto
FB and Twitter: / errichto & / errichto
Frequently Asked Questions: github.com/Err...

Опубликовано:

14 окт 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 155

@danieldawson8018 4 года назад

It's cool to see you get better and better at explaining as time goes on, and you were already good to begin with. Thank you, and keep it up!

@devendrasingh4776 4 года назад

Quite obvious as he is a fighter and he knows it.

@marvinlessknown3702 2 года назад

He really is very good. Is he russian?? They're the best teachers / mathematicians I've ever. kantorovich being maybe the greatest??

@justsvk1500 Год назад

@@marvinlessknown3702 polish

@ShubhamGhuleCodes 4 года назад

Your videos are the reason I started competitive programming 🙌 thanks a lot!

@Errichto 4 года назад

that's great to hear!

@digitalgandu1511 3 года назад

Why ?

@fahadhos 2 года назад

@@Errichto so your code will support this 5^(10^5)?

@hil449 9 месяцев назад

@@fahadhosyes, its lob(b)

@rakshithdogra793 4 года назад

Hey Errichto i saw your video and got motivated towards CP and today only i solved my first problem on codeforces thank you bro

@Errichto 4 года назад

Cool, good luck!

@jdhp3696 4 года назад

Errichto, when you first released it, I didn't understand the concept of it, but decided to save it in my playlist to watch it later. Today, I was solving the daily challenge on Leetcode and suddenly remembered your video. Watching it now, things start clicking for me. Thank you so much. Please make more videos like these.

@azazel-oss 13 дней назад

Hi Errichto, I hope you are doing great, just wanted to let you know that you are the reason I got into competitive programming and now I am addicted to it. Cheers

@nickheyer 2 года назад

I truly appreciate the "over-explanation" of even the more simple concepts. If anything it is a reinforcement that helps drive the concept home, instead of just skimming over it without any actual absorption.

@manishsharma2211 4 года назад

Errichto , The picasso of CP👌🔥

@MojahooProducer 4 года назад

wow another video, i thought your stream was planning a lot. thanks for your dedication, remember not to push so hard that you burn out! youre perhaps even the best educational channel i've seen, the way you explain things helps you understand how to get there too.

@Errichto 4 года назад

@yeetholmes619 3 года назад

I like how you smile when you explain the concept, shows your deep love for the art! A pleasure to learn from you !

@ANKITVERMA-fl1zn 4 года назад

The Overall Quality of videos are getting better great work indeed! waiting eagerly for Gaussian Elimination.

@Garentei 4 года назад

Best channel ever. This was actually my Facebook interview question.

@vikku_19 4 года назад

Really? Or They asked about of digits? Generally, we're asked about digits of big powers.

@Garentei 4 года назад

@@vikku_19 No, it was binary exponentiation. But he didn't explicitly ask me to do so, he asked me to optimize a^b.

@LearnWithAnmolll 5 месяцев назад

your article is just awesome

@vinitsharma6630 Год назад

i wasted my time in another video watching it again & again trying to figure this out this made it crystal clear covering every doubt the previous video created like the shift and mod ones

@CarlosMartinez-ed7ey Год назад

Thank you very much, you have a natural talent to explain clearly and make it easy.

@tonystarc9567 4 года назад

Errichto you are a savior.... Please keep up doing this good work ... This matters a lot specially in the countries with small per capita income...

@tomtan298 4 года назад

Your videos are the reason I started competitive programming ! Thanks so much for the contribution to this community,keep up the great effort and keep on pumping out more videos for the beginner series :D

@CarrotCakeMake 4 года назад

It amazing how there exists and algorithm to create an output of size B*log(A) in time log(B).

@Errichto 4 года назад

The complexity O(log(B)) assumes that multiplication is done in O(1). This makes sense because we mainly compute a huge power modulo P.

@rajvijen 4 года назад

Just Watching A.B%N and this one pop out. Seems like whole series on NUMBER Theory coming out.😎

@Errichto 4 года назад

As some people might know from my recent stream, next is matrix exponentiation and gaussian elimination ;) then more advanced topics

@loneshaan8531 4 года назад

@@Errichto looking forward

@shahbazalam3722 4 года назад

@@Errichto Excited to learn Matrix Exponentiation.

@Gauravverma-ed7fw 4 года назад

@Errichto please continue the series for mathematics in CP

@Gauravverma-ed7fw 4 года назад

@@Errichto please continue series for mathematics in CP

@ritikbaid4318 4 года назад

Great content Erricto!.would be great to see some videos in the future on segment trees as well!

@sujan_kumar_mitra 3 года назад

Best explanation of binary exponentiation

@SebastianTysler 3 года назад

Thanks Errichto! This is good and easy explanation for fast-power (Binary Exponentiation)

@AbhishekKumar-ky3uc 4 года назад

Hi Errichto, I am a subscriber of your RU-vid channel and admire your work alot.Wanted to ask for an advice , how to learn solution of a problem when it's solution is not present anywhere on internet. Even if I get a hint it's easier. But there are some problems like asked on an interview whose solution afterwards I get nowhere in internet. How to learns solutions of such problems?

@TyButNowYouDie 9 месяцев назад

I had already solved this problem recursively before but I didn't understand the iterative solution until watching this video. Your explanation and visualization was really helpful. Thanks!

@em_nikhil_007 4 года назад

Are you kidding me ERRICHTO!! How can you read my mind for what topics i need????

@yatharthfrommeerut9006 4 года назад

I always thought why we studied this multiplication in principle of programming language. Now I know. Thanks

@ductran7258 2 года назад

Thank you! Your explanation for this algorithm is awesome!

@hackytech7494 3 года назад

Thanks for the explanation

@hardikupadhyay9837 4 года назад

Waiting for some more advanced stuff to come :) This videos are really great

@thaynaemillycavalcantesant3687 3 месяца назад

Really good explanation. Ty!

@CodeDecipher 4 года назад

Great video you upload 👌 I myself make computer science videos . Can you tell me which mic do you use ?

@jonathanparlett1172 2 года назад

This was super helpful for my cryptography class thank you!

@Aman_Panchal27 9 месяцев назад

This video helped a lot. Thanks Man.

@shameekagarwal4872 4 года назад

thats very good!! please do cover diophantine equations, fft etc as well...and in such topics maybe include popular question and variations thanks!!

@dadisuperman3472 Год назад

Did you added the tag "Easy" on the thumbnail of the video? It was not there before.

@RamisaAnjum 2 года назад

12:10 Thanks, man :D I thought I was the only one.

@ashwinmadke486 3 года назад

Wonderful explanation ❤️! Understood every little thing. Thankyou 🙏

@johnstephen8041 4 года назад

Thanks much... keep doing these kind of videos.. really helps!

@dipankarkumarsingh 3 года назад

thank you for your wonderful explanation... you are an amazing teacher .

@craigmiller9380 4 года назад

Best videos on youtube, thank you!

@adityatewary7174 4 года назад

Hey, Errichto thanks for the video. Can you also put some questions link in your description box?

@vedshrutisarkar4319 3 года назад

Thank you for a perfect and easy explanation😄

@ChandraShekhar-by3cd 4 года назад

Errichto Your are the "Einstine of CP".

@ChandraShekhar-by3cd 4 года назад

@@audiogear4412 Yes I do.

@rakeshghosh8234 4 года назад

Great way. Its very nice than previous.

@ujjawal_ Год назад

which whiteboard website you are using

@ShubhamGhuleCodes 4 года назад

Missing the teddy 🧸!

@climbnexplore1187 4 года назад

But instead we have alcohol left of errichtos shoulder... wait why does Oxygen have three connections ?

@ShubhamGhuleCodes 4 года назад

@@climbnexplore1187 Its carbon bro !

@arushsaxena1213 4 года назад

great video. It would be awesome if you could make a video on Merge sort tree.

@siddharthpanigrahi3855 3 года назад

Thank You, explained really well.

@tarsala1995 4 года назад

You can calculate 9^9 I remember that it's 387420489 But it doesn't really matter

@souravsaha933 2 года назад

Fine answer. Thanks ❤️

@Ghayth.Moustpha 4 года назад

Thank you a lot ❤ Can you please recommend some problems to implemented as a training... Thanks again ❤❤💙💙💙

@amanrazz2091 4 года назад

GOD level explantation .... 🖤

@rohanprak 4 года назад

@errichto *please* make a video on Segment tree *iterative* with *lazy propagation* , everyone teaches recursive one, with memory 4*n and 5 arguments !! non recursive if okay till point updates, but range updates ( lazy propagation ) seems way too complicated. please make a video on *lazy update* on *non recursive segment* tree, we belief you will make it simpler, and also no video on you-tube exists on it.

@asifanwarsajid8332 3 года назад

Kamil, we need more videos from you. :D

@kgCode658 3 года назад

wow u also have great teaching skills ..Thanks for helping

@Aditya-fx2tv 4 года назад

Love your video errichto ❤

@winterSweet-k4m 4 года назад

can you make some videos about fractals in action? also, you're videos are *CRAZYYY* you're so good at explaining stuff

@איתיאוטולנגי 4 года назад

can u please make a video abot how to setup your cp setup - how to download and use yor ide? would also like to see some c++ toturials tank you very nuch!

@rajshubhankar1725 2 года назад

Hey what if I remove the 0 condition instead of 1. why just if(b==1) return a is not correct ?

@VachaspatiMishra99 4 года назад

Dimitri finds out.

@Jinsama_01 4 года назад

awesome video bro. take ❤️ from 🇧🇩

@SmartCoder89 4 года назад

I like the new background 👍

@baxi9227 4 года назад

don't forget to flex how you came up with matrix expo yourself

@Errichto 4 года назад

Is it that important though? :D

@mksybr 4 года назад

@@Errichto What video was that?

@parnabghosh7877 3 года назад

great explanation !

@omaraljarrah5089 4 года назад

When the Matrix expo is coming? We have been waiting for a long time now, looking forward to the new video

@sawvikdipto3087 Год назад

Only for My help. Please ignore. def p(a,b): res=1 while b>0: if b%2==1: res=res*a a=a*a b=b//2 return res

@carbyte2673 4 месяца назад

Thanks a lot man!

@PankajKumarGladiator 4 года назад

10:54 😂That awkward moment 😂 !!

@riadhasan9725 Год назад

Very helpful 👍

@yashrastogi3726 4 года назад

Thanks man. Keep it up

@venkatkumar5220 4 года назад

Can you do a video on Matrix Exponentiation?

@kakashisenpai99 4 года назад

Bro post your Hackerrank problem , 'Lisa's Workbook' approach and solution!

@II_xD_II 4 года назад

respecckt

@mdfahad2726 4 года назад

I love your background 😍. Any specific reason why it contains High school physics, chemistry, maths equations?

@Errichto 4 года назад

All science is beautiful, isn't it?

@hil449 9 месяцев назад

didnt understand a single thing from the inverse part but ok, great video

@AbhishekSingh-ws5rz 4 года назад

Another great video. 😊

@preetamvarun9219 3 года назад

Thank you

@ahsanulameensabit 4 года назад

Waiting for the next one...

@097kushagrarawat9 3 года назад

really helpful content :)

@vetiarvind 2 года назад

6:45 - no need to check for odd in the while loop. just do int result = b&1 ? a : 1; //in the init. This is because b can only be odd once in the loop.

@diwyanshukanthwal8669 4 года назад

can you tell about left to right binary exponential

@HelloWorld-sy4yc 4 года назад

Do u have a blog or channel in telegram for instance?

@himanshudixit490 3 года назад

Problem: You are given a sequence of length n. Apply to it a given permutation k times. Solution: Simply raise the permutation to k-th power using binary exponentiation, and then apply it to the sequence. This will give you a time complexity of O(nlogk) Can anybody explain what its talking about ?

@i.anandsingh 4 года назад

can you please explain how to find PRIMITIVE ROOTS,? and EULER'S TOTIENT FUNCTION.

@harshamusunuri1924 2 года назад

I don't understand the iterative part, is there any other simpler way to understand this?

@MrPatrickbuit 8 месяцев назад

I understand it completely but it’s another one of those things I would not have come up with

@anmol_tomer 4 года назад

I am a simple man, if(Errichto uploads) { make notes && like the video} # :D

@enside8822 3 года назад

Thank you!!!

@shoryasinghal5241 Год назад

good eric

@omaraljarrah5089 4 года назад

Thank U, U are awesome 🤘🌨❄

@joyo2122 3 года назад

🙏

@i_am_wiz 3 года назад

I didn’t understand how 0th bit contributes to a....1st bit to a^2.....2nd bit to a^4.....and so on.....can anyone please help?

@falseee4445 4 года назад

Thanks !

@tombrady7390 3 года назад

wow 200k kamil take a bow

@rujixie9025 4 года назад

So neat

@debadityasutradhar7962 4 года назад

why cant we just use pow(a,b) by taking a & b as input

@iliavasilenko4961 4 года назад

Is it normal when somebody uses ints instead of long long?

@amalsakkoumi1392 4 года назад

If a^-b how we can slove it please

@abhudyasingh9109 4 года назад

How to calculate pow(a,pow(b,c)) under modulo

@aquibansari3941 4 года назад

can anyone please tell which tool is he using to draw and sketch

@sakshamjain6900 4 года назад

software is ONE NOTE available on windows 10 and he is using graphic tablet to draw on screen (a board and a pen)!

@ankitchoudhury9678 2 года назад

Damnnn.. love you

@hamzakhiar3636 3 года назад

you said recurssive programs are slower than iterative programs why

@SanjeevKumar-tk4xd Месяц назад

Because recursion uses stack data structure to hold these functions and it takes mounting and unmounting time to switch between functions. But iterative keeps running in one go. Slightly faster. Use javas currunt time millis and run a big test case you might see some milliseconds difference