Binary Exponentiation

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.com/ for articles on more advanced algorithms.
Subscribe for more educational videos on algorithms, coding interviews and competitive programming.
- Github repository: github.com/Errichto/youtube
- Live streams on 2nd YT channel and on Twitch: / errichto2 & / errichto
- FB and Twitter: / errichto & / errichto
- Frequently Asked Questions: github.com/Errichto/youtube/w...

Пікірлер: 152

  • @danieldawson8018
    @danieldawson80184 жыл бұрын

    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

    @devendrasingh4776

    4 жыл бұрын

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

  • @marvinlessknown3702

    @marvinlessknown3702

    Жыл бұрын

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

  • @justsvk1500

    @justsvk1500

    Жыл бұрын

    ​@@marvinlessknown3702 polish

  • @jdhp3696
    @jdhp36964 жыл бұрын

    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.

  • @ShubhamGhuleCode
    @ShubhamGhuleCode4 жыл бұрын

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

  • @Errichto

    @Errichto

    4 жыл бұрын

    that's great to hear!

  • @digitalgandu1511

    @digitalgandu1511

    3 жыл бұрын

    Why ?

  • @fahadhos

    @fahadhos

    Жыл бұрын

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

  • @hil449

    @hil449

    6 ай бұрын

    @@fahadhosyes, its lob(b)

  • @tomtan298
    @tomtan2984 жыл бұрын

    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

  • @rakshithdogra793
    @rakshithdogra7934 жыл бұрын

    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

    @Errichto

    4 жыл бұрын

    Cool, good luck!

  • @yeetholmes619
    @yeetholmes6193 жыл бұрын

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

  • @nickheyer
    @nickheyer2 жыл бұрын

    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.

  • @ANKITVERMA-fl1zn
    @ANKITVERMA-fl1zn4 жыл бұрын

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

  • @TyButNowYouDie
    @TyButNowYouDie6 ай бұрын

    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!

  • @manishsharma2211
    @manishsharma22114 жыл бұрын

    Errichto , The picasso of CP👌🔥

  • @hardikupadhyay9837
    @hardikupadhyay98374 жыл бұрын

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

  • @MojahooProducer
    @MojahooProducer4 жыл бұрын

    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

    @Errichto

    4 жыл бұрын

    :3

  • @ritikbaid4318
    @ritikbaid43184 жыл бұрын

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

  • @tonystarc9567
    @tonystarc95674 жыл бұрын

    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...

  • @CarlosMartinez-ed7ey
    @CarlosMartinez-ed7ey11 ай бұрын

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

  • @SebastianTysler
    @SebastianTysler3 жыл бұрын

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

  • @ductran7258
    @ductran72582 жыл бұрын

    Thank you! Your explanation for this algorithm is awesome!

  • @vinitsharma6630
    @vinitsharma663011 ай бұрын

    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

  • @LearnWithAnmolll
    @LearnWithAnmolll3 ай бұрын

    your article is just awesome

  • @ashwinmadke486
    @ashwinmadke4863 жыл бұрын

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

  • @Garentei
    @Garentei4 жыл бұрын

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

  • @vikku_19

    @vikku_19

    3 жыл бұрын

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

  • @Garentei

    @Garentei

    3 жыл бұрын

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

  • @craigmiller9380
    @craigmiller93804 жыл бұрын

    Best videos on youtube, thank you!

  • @shameekagarwal4872
    @shameekagarwal48724 жыл бұрын

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

  • @johnstephen8041
    @johnstephen80413 жыл бұрын

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

  • @dipankarkumarsingh
    @dipankarkumarsingh3 жыл бұрын

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

  • @jonathanparlett1172
    @jonathanparlett11722 жыл бұрын

    This was super helpful for my cryptography class thank you!

  • @thaynaemillycavalcantesant3687
    @thaynaemillycavalcantesant368729 күн бұрын

    Really good explanation. Ty!

  • @Aman_Panchal27
    @Aman_Panchal276 ай бұрын

    This video helped a lot. Thanks Man.

  • @Aditya-fx2tv
    @Aditya-fx2tv4 жыл бұрын

    Love your video errichto ❤

  • @siddharthpanigrahi3855
    @siddharthpanigrahi38553 жыл бұрын

    Thank You, explained really well.

  • @vedshrutisarkar4319
    @vedshrutisarkar43193 жыл бұрын

    Thank you for a perfect and easy explanation😄

  • @rakeshghosh8234
    @rakeshghosh82344 жыл бұрын

    Great way. Its very nice than previous.

  • @arushsaxena1213
    @arushsaxena12134 жыл бұрын

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

  • @sajinamin328
    @sajinamin3284 жыл бұрын

    awesome video bro. take ❤️ from 🇧🇩

  • @AbhishekSingh-ws5rz
    @AbhishekSingh-ws5rz4 жыл бұрын

    Another great video. 😊

  • @sujan_kumar_mitra
    @sujan_kumar_mitra3 жыл бұрын

    Best explanation of binary exponentiation

  • @yashrastogi3726
    @yashrastogi37264 жыл бұрын

    Thanks man. Keep it up

  • @yatharthfrommeerut9006
    @yatharthfrommeerut90064 жыл бұрын

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

  • @w4rd3nclyffe74
    @w4rd3nclyffe744 жыл бұрын

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

  • @souravsaha933
    @souravsaha9332 жыл бұрын

    Fine answer. Thanks ❤️

  • @hackytech7494
    @hackytech74943 жыл бұрын

    Thanks for the explanation

  • @SmartCoder89
    @SmartCoder894 жыл бұрын

    I like the new background 👍

  • @kgCode658
    @kgCode6583 жыл бұрын

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

  • @adityatewary7174
    @adityatewary71744 жыл бұрын

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

  • @parnabghosh7877
    @parnabghosh78773 жыл бұрын

    great explanation !

  • @097kushagrarawat9
    @097kushagrarawat93 жыл бұрын

    really helpful content :)

  • @omaraljarrah5089
    @omaraljarrah50894 жыл бұрын

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

  • @asifanwarsajid8332
    @asifanwarsajid83323 жыл бұрын

    Kamil, we need more videos from you. :D

  • @RamisaAnjum
    @RamisaAnjum2 жыл бұрын

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

  • @carbyte2673
    @carbyte2673Ай бұрын

    Thanks a lot man!

  • @riadhasan9725
    @riadhasan9725 Жыл бұрын

    Very helpful 👍

  • @em_nikhil_007
    @em_nikhil_0074 жыл бұрын

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

  • @Ghayth.Moustpha
    @Ghayth.Moustpha4 жыл бұрын

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

  • @omaraljarrah5089
    @omaraljarrah50894 жыл бұрын

    Thank U, U are awesome 🤘🌨❄

  • @CarrotCakeMake
    @CarrotCakeMake4 жыл бұрын

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

  • @Errichto

    @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.

  • @CodeDecipher
    @CodeDecipher4 жыл бұрын

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

  • @user-ui2qk6jg5n
    @user-ui2qk6jg5n4 жыл бұрын

    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!

  • @preetamvarun9219
    @preetamvarun92193 жыл бұрын

    Thank you

  • @enside8822
    @enside88223 жыл бұрын

    Thank you!!!

  • @amanrazz2091
    @amanrazz20913 жыл бұрын

    GOD level explantation .... 🖤

  • @falseee4445
    @falseee44454 жыл бұрын

    Thanks !

  • @ChandraShekhar-by3cd
    @ChandraShekhar-by3cd4 жыл бұрын

    Errichto Your are the "Einstine of CP".

  • @ChandraShekhar-by3cd

    @ChandraShekhar-by3cd

    4 жыл бұрын

    @@audiogear4412 Yes I do.

  • @rajvijen
    @rajvijen4 жыл бұрын

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

  • @Errichto

    @Errichto

    4 жыл бұрын

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

  • @loneshaan8531

    @loneshaan8531

    4 жыл бұрын

    @@Errichto looking forward

  • @shahbazalam3722

    @shahbazalam3722

    4 жыл бұрын

    @@Errichto Excited to learn Matrix Exponentiation.

  • @Gauravverma-ed7fw

    @Gauravverma-ed7fw

    4 жыл бұрын

    @Errichto please continue the series for mathematics in CP

  • @Gauravverma-ed7fw

    @Gauravverma-ed7fw

    4 жыл бұрын

    @@Errichto please continue series for mathematics in CP

  • @AbhishekKumar-ky3uc
    @AbhishekKumar-ky3uc4 жыл бұрын

    Hi Errichto, I am a subscriber of your KZread 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?

  • @ankitchoudhury9678
    @ankitchoudhury9678 Жыл бұрын

    Damnnn.. love you

  • @diwyanshukanthwal8669
    @diwyanshukanthwal86693 жыл бұрын

    can you tell about left to right binary exponential

  • @ahsanulameensabit
    @ahsanulameensabit4 жыл бұрын

    Waiting for the next one...

  • @rajshubhankar1725
    @rajshubhankar17252 жыл бұрын

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

  • @rujixie9025
    @rujixie90253 жыл бұрын

    So neat

  • @venkatkumar5220
    @venkatkumar52204 жыл бұрын

    Can you do a video on Matrix Exponentiation?

  • @i.anandsingh
    @i.anandsingh4 жыл бұрын

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

  • @rohanprak
    @rohanprak4 жыл бұрын

    @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.

  • @abhudyasingh9109
    @abhudyasingh91094 жыл бұрын

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

  • @amalsakkoumi1392
    @amalsakkoumi13923 жыл бұрын

    If a^-b how we can slove it please

  • @tarsala1995
    @tarsala19954 жыл бұрын

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

  • @hil449
    @hil4496 ай бұрын

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

  • @kakashisenpai99
    @kakashisenpai994 жыл бұрын

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

  • @II_xD_II

    @II_xD_II

    4 жыл бұрын

    respecckt

  • @shoryasinghal5241
    @shoryasinghal5241 Жыл бұрын

    good eric

  • @ShubhamGhuleCode
    @ShubhamGhuleCode4 жыл бұрын

    Missing the teddy 🧸!

  • @climbnexplore1187

    @climbnexplore1187

    4 жыл бұрын

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

  • @ShubhamGhuleCode

    @ShubhamGhuleCode

    4 жыл бұрын

    @@climbnexplore1187 Its carbon bro !

  • @joyo2122
    @joyo21223 жыл бұрын

    🙏

  • @iliavasilenko4961
    @iliavasilenko49614 жыл бұрын

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

  • @VachaspatiMishra99
    @VachaspatiMishra994 жыл бұрын

    Dimitri finds out.

  • @HelloWorld-sy4yc
    @HelloWorld-sy4yc4 жыл бұрын

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

  • @5590priyank
    @5590priyank4 жыл бұрын

    geeky background :)

  • @ujjawal_
    @ujjawal_ Жыл бұрын

    which whiteboard website you are using

  • @MrPatrickbuit
    @MrPatrickbuit6 ай бұрын

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

  • @i_am_wiz
    @i_am_wiz3 жыл бұрын

    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?

  • @node3079
    @node30793 жыл бұрын

    4:57 Can someone please explain ..thanks🙏

  • @aquibansari3941
    @aquibansari39414 жыл бұрын

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

  • @sakshamjain6900

    @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)!

  • @himanshudixit490
    @himanshudixit4903 жыл бұрын

    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 ?

  • @anmol_tomer
    @anmol_tomer4 жыл бұрын

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

  • @tombrady7390
    @tombrady73903 жыл бұрын

    wow 200k kamil take a bow

  • @afeyaraa3490
    @afeyaraa34903 жыл бұрын

    cool

  • @harshamusunuri1924
    @harshamusunuri19242 жыл бұрын

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

  • @dadisuperman3472
    @dadisuperman3472 Жыл бұрын

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

  • @baxi9227
    @baxi92274 жыл бұрын

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

  • @Errichto

    @Errichto

    4 жыл бұрын

    Is it that important though? :D

  • @mksybr

    @mksybr

    4 жыл бұрын

    @@Errichto What video was that?

  • @debadityasutradhar7962
    @debadityasutradhar79623 жыл бұрын

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

  • @sawvikdipto3087
    @sawvikdipto308710 ай бұрын

    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

  • @PankajKumarGladiator
    @PankajKumarGladiator4 жыл бұрын

    10:54 😂That awkward moment 😂 !!

  • @aryanyadav3926
    @aryanyadav3926 Жыл бұрын

    Didn't understand the inverse part. Rest was good