Binary Exponentiation

Sdílet
Vložit
  • čas přidán 28. 08. 2024
  • 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...

Komentáře • 154

  • @danieldawson8018
    @danieldawson8018 Před 4 lety +128

    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 Před 4 lety

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

    • @marvinlessknown3702
      @marvinlessknown3702 Před rokem

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

    • @justsvk1500
      @justsvk1500 Před rokem

      ​@@marvinlessknown3702 polish

  • @ShubhamGhuleCodes
    @ShubhamGhuleCodes Před 4 lety +95

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

  • @rakshithdogra793
    @rakshithdogra793 Před 4 lety +40

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

  • @jdhp3696
    @jdhp3696 Před 4 lety +11

    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.

  • @nickheyer
    @nickheyer Před 2 lety

    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
    @manishsharma2211 Před 4 lety +13

    Errichto , The picasso of CP👌🔥

  • @TyButNowYouDie
    @TyButNowYouDie Před 7 měsíci

    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!

  • @MojahooProducer
    @MojahooProducer Před 4 lety +27

    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.

  • @yeetholmes619
    @yeetholmes619 Před 3 lety

    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
    @ANKITVERMA-fl1zn Před 4 lety +3

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

  • @Garentei
    @Garentei Před 4 lety +3

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

    • @vikku_19
      @vikku_19 Před 4 lety

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

    • @Garentei
      @Garentei Před 4 lety

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

  • @tonystarc9567
    @tonystarc9567 Před 4 lety +1

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

  • @LearnWithAnmolll
    @LearnWithAnmolll Před 4 měsíci +1

    your article is just awesome

  • @tomtan298
    @tomtan298 Před 4 lety

    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

  • @vinitsharma6630
    @vinitsharma6630 Před rokem

    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
    @CarlosMartinez-ed7ey Před rokem

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

  • @rajvijen
    @rajvijen Před 4 lety +13

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

    • @Errichto
      @Errichto  Před 4 lety +47

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

    • @loneshaan8531
      @loneshaan8531 Před 4 lety

      @@Errichto looking forward

    • @shahbazalam3722
      @shahbazalam3722 Před 4 lety

      @@Errichto Excited to learn Matrix Exponentiation.

    • @Gauravverma-ed7fw
      @Gauravverma-ed7fw Před 4 lety

      @Errichto please continue the series for mathematics in CP

    • @Gauravverma-ed7fw
      @Gauravverma-ed7fw Před 4 lety

      @@Errichto please continue series for mathematics in CP

  • @SebastianTysler
    @SebastianTysler Před 3 lety

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

  • @em_nikhil_007
    @em_nikhil_007 Před 4 lety +3

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

  • @sujan_kumar_mitra
    @sujan_kumar_mitra Před 3 lety

    Best explanation of binary exponentiation

  • @ritikbaid4318
    @ritikbaid4318 Před 4 lety +1

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

  • @CarrotCakeMake
    @CarrotCakeMake Před 4 lety +2

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

    • @Errichto
      @Errichto  Před 4 lety +1

      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.

  • @hardikupadhyay9837
    @hardikupadhyay9837 Před 4 lety

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

  • @ductran7258
    @ductran7258 Před 2 lety

    Thank you! Your explanation for this algorithm is awesome!

  • @thaynaemillycavalcantesant3687

    Really good explanation. Ty!

  • @yatharthfrommeerut9006

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

  • @RamisaAnjum
    @RamisaAnjum Před 2 lety

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

  • @jonathanparlett1172
    @jonathanparlett1172 Před 2 lety

    This was super helpful for my cryptography class thank you!

  • @Aman_Panchal27
    @Aman_Panchal27 Před 7 měsíci

    This video helped a lot. Thanks Man.

  • @ashwinmadke486
    @ashwinmadke486 Před 3 lety

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

  • @johnstephen8041
    @johnstephen8041 Před 4 lety

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

  • @craigmiller9380
    @craigmiller9380 Před 4 lety

    Best videos on youtube, thank you!

  • @dipankarkumarsingh
    @dipankarkumarsingh Před 3 lety

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

  • @shameekagarwal4872
    @shameekagarwal4872 Před 4 lety +1

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

  • @mdfahad2726
    @mdfahad2726 Před 4 lety +5

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

    • @Errichto
      @Errichto  Před 4 lety +2

      All science is beautiful, isn't it?

  • @hackytech7494
    @hackytech7494 Před 3 lety +1

    Thanks for the explanation

  • @ChandraShekhar-by3cd
    @ChandraShekhar-by3cd Před 4 lety +1

    Errichto Your are the "Einstine of CP".

  • @AbhishekKumar-ky3uc
    @AbhishekKumar-ky3uc Před 4 lety +1

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

  • @vedshrutisarkar4319
    @vedshrutisarkar4319 Před 3 lety

    Thank you for a perfect and easy explanation😄

  • @dadisuperman3472
    @dadisuperman3472 Před rokem

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

  • @amanrazz2091
    @amanrazz2091 Před 3 lety +2

    GOD level explantation .... 🖤

  • @souravsaha933
    @souravsaha933 Před 2 lety

    Fine answer. Thanks ❤️

  • @ShubhamGhuleCodes
    @ShubhamGhuleCodes Před 4 lety +14

    Missing the teddy 🧸!

    • @climbnexplore1187
      @climbnexplore1187 Před 4 lety +1

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

    • @ShubhamGhuleCodes
      @ShubhamGhuleCodes Před 4 lety

      @@climbnexplore1187 Its carbon bro !

  • @sajinamin328
    @sajinamin328 Před 4 lety

    awesome video bro. take ❤️ from 🇧🇩

  • @kgCode658
    @kgCode658 Před 3 lety

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

  • @Aditya-fx2tv
    @Aditya-fx2tv Před 4 lety

    Love your video errichto ❤

  • @SmartCoder89
    @SmartCoder89 Před 4 lety

    I like the new background 👍

  • @PankajKumarGladiator
    @PankajKumarGladiator Před 4 lety +7

    10:54 😂That awkward moment 😂 !!

  • @siddharthpanigrahi3855

    Thank You, explained really well.

  • @rakeshghosh8234
    @rakeshghosh8234 Před 4 lety

    Great way.
    Its very nice than previous.

  • @carbyte2673
    @carbyte2673 Před 2 měsíci

    Thanks a lot man!

  • @CodeDecipher
    @CodeDecipher Před 4 lety

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

  • @riadhasan9725
    @riadhasan9725 Před rokem

    Very helpful 👍

  • @winterSweet-k4m
    @winterSweet-k4m Před 4 lety

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

  • @asifanwarsajid8332
    @asifanwarsajid8332 Před 3 lety

    Kamil, we need more videos from you. :D

  • @rohanprak
    @rohanprak Před 4 lety +1

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

  • @tarsala1995
    @tarsala1995 Před 4 lety +1

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

  • @adityatewary7174
    @adityatewary7174 Před 4 lety

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

  • @parnabghosh7877
    @parnabghosh7877 Před 3 lety

    great explanation !

  • @arushsaxena1213
    @arushsaxena1213 Před 4 lety

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

  • @ujjawal_
    @ujjawal_ Před rokem +1

    which whiteboard website you are using

  • @yashrastogi3726
    @yashrastogi3726 Před 4 lety

    Thanks man. Keep it up

  • @Ghayth.Moustpha
    @Ghayth.Moustpha Před 4 lety

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

  • @harshamusunuri1924
    @harshamusunuri1924 Před 2 lety

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

  • @AbhishekSingh-ws5rz
    @AbhishekSingh-ws5rz Před 4 lety

    Another great video. 😊

  • @hil449
    @hil449 Před 7 měsíci

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

  • @anmol_tomer
    @anmol_tomer Před 4 lety +1

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

  • @omaraljarrah5089
    @omaraljarrah5089 Před 4 lety

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

  • @rajshubhankar1725
    @rajshubhankar1725 Před 2 lety

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

  • @himanshudixit490
    @himanshudixit490 Před 3 lety

    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 ?

  • @baxi9227
    @baxi9227 Před 4 lety +4

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

    • @Errichto
      @Errichto  Před 4 lety +5

      Is it that important though? :D

    • @mksybr
      @mksybr Před 4 lety +1

      @@Errichto What video was that?

  • @097kushagrarawat9
    @097kushagrarawat9 Před 3 lety

    really helpful content :)

  • @sawvikdipto3087
    @sawvikdipto3087 Před 11 měsíci

    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

  • @VachaspatiMishra99
    @VachaspatiMishra99 Před 4 lety +4

    Dimitri finds out.

  • @preetamvarun9219
    @preetamvarun9219 Před 3 lety

    Thank you

  • @kakashisenpai99
    @kakashisenpai99 Před 4 lety +1

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

  • @i_am_wiz
    @i_am_wiz Před 3 lety

    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?

  • @user-ui2qk6jg5n
    @user-ui2qk6jg5n Před 4 lety

    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!

  • @omaraljarrah5089
    @omaraljarrah5089 Před 4 lety

    Thank U, U are awesome 🤘🌨❄

  • @ankitchoudhury9678
    @ankitchoudhury9678 Před 2 lety

    Damnnn.. love you

  • @hamzakhiar3636
    @hamzakhiar3636 Před 3 lety

    you said recurssive programs are slower than iterative programs why

    • @SanjeevKumar-tk4xd
      @SanjeevKumar-tk4xd Před 4 dny +1

      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

  • @diwyanshukanthwal8669
    @diwyanshukanthwal8669 Před 4 lety

    can you tell about left to right binary exponential

  • @rujixie9025
    @rujixie9025 Před 4 lety

    So neat

  • @iliavasilenko4961
    @iliavasilenko4961 Před 4 lety

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

  • @enside8822
    @enside8822 Před 3 lety

    Thank you!!!

  • @venkatkumar5220
    @venkatkumar5220 Před 4 lety

    Can you do a video on Matrix Exponentiation?

  • @debadityasutradhar7962

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

  • @shoryasinghal5241
    @shoryasinghal5241 Před rokem

    good eric

  • @i.anandsingh
    @i.anandsingh Před 4 lety

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

  • @amalsakkoumi1392
    @amalsakkoumi1392 Před 4 lety

    If a^-b how we can slove it please

  • @HelloWorld-sy4yc
    @HelloWorld-sy4yc Před 4 lety

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

  • @ahsanulameensabit
    @ahsanulameensabit Před 4 lety

    Waiting for the next one...

  • @joyo2122
    @joyo2122 Před 3 lety

    🙏

  • @falseee4445
    @falseee4445 Před 4 lety

    Thanks !

  • @abhudyasingh9109
    @abhudyasingh9109 Před 4 lety

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

  • @vetiarvind
    @vetiarvind Před 2 lety

    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.

  • @MrPatrickbuit
    @MrPatrickbuit Před 7 měsíci

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

  • @aquibansari3941
    @aquibansari3941 Před 4 lety

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

    • @sakshamjain6900
      @sakshamjain6900 Před 4 lety

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

  • @tombrady7390
    @tombrady7390 Před 3 lety

    wow 200k kamil take a bow

  • @yashagarwal3999
    @yashagarwal3999 Před 4 lety

    it is not at all working in python please help simebody