Efficient Exponentiation

How many multiplys does it take to compute x^n?

It may be fewer than you think! Worried that calling x ** 15 "slow" is not correct? Don't worry, I tested!

Out[4]: 0.3686526000000043
Out[5]: 0.3275107000000048

SUPPORT ME ⭐
---------------------------------------------------

BE ACTIVE IN MY COMMUNITY 😄
---------------------------------------------------

[maroonshaded]

I've never seen this channel and it appeared in my recommendation within 43 minutes of publishing... So this the start of everything...

[gardnmi]

You should rename this channel to "reality check". You put my programming knowledge to shambles.

[WysockiD]

i laughed when he said "and im not even going to get into that" as he is giving me the deepest look into such code that ive ever seen.. and to know this man is just scratching the surface humored me. well done man, i see the channel is climbing significantly with every video, you deserve it.

[DatNguyen-vjro]

8:52 I just finished my Discrete Math Homework on Modular Arithmetics, my last question was 600 ^ 251 mod 1457, so jokes on you

[HackerTypeZ]

"slap the sub button an odd number of times" got me good 😂

[AristAristA]

Loved the conclusion on how this trick applies to matrix exponentiation. Simulated markov chains or random walks must benefit so much from this.

[mustafamotiwala]

Seeing a new mCoding video has come out is always a delight. Thank you for what you do!

[ulilulable]

Thanks for the "compiler explorer" tip! Now I finally understand Duff's device!

[aryanparekh]

This channel WILL blow up, your videos are top notch

[calculateddegenerate]

I consider myself a expert Python developer. Still I always learn something new about the beautiful language from your videos.

[jameleddinelassoued]

I got this in my recommended out of nowhere and I gotta say the algorithm is doing its work! I love this thank you! Subscribed.

[Ensivion]

I ran into this problem when I did my implementation of the newton fractal that 3Blue1Brown made two videos on. My naive approach made it so that it took like 20 seconds to compute ONE FRAME of an animation I was doing with not that great error bounds. I quickly
found out that the solution was more along the lines of what you finished this video on, you kinda have to take a different approach to exponentiation, if one is available, which for computing polynomials (of even non-integer powers) there are some already done methods that speed this up significantly. So really this complex problem generally has solutions in many different ways. Also you don't go into complex numbers, which for those fractals I had to take powers of complex numbers, which in its own right also is a big problem to be optimized.

[erumabo]

When I need efficient exponents I go with a recursive strategy: if exponent is even return x^floor(exponent/2) * x^floor(exponent/2), if odd multiply that times x.

[glob]

There are of course ways to make a general exponentiation algorithm even more efficient by checking if the number to be exponentiated is a power of two. Then you just use bitwise shift left instead of multiplication.
For example 2<<14 should be more efficient than 2**15

[amaarquadri]

I thought this video was going to end with binary numbers and repeated squaring... but that's where it started 😂. Great video!

[xbarbz]

Thanks YouTube algorithm for recommending this, I am hooked. Subbed and looking forward to going through all your other videos

[klimenkor]

nice!
a good example that shows that most efficient code doesn't mean the most elegant code :)

[mikono]

shhhh, He's staring into your soul

[pezus]

this channel will definetly grow a lot

[gregorymorse]

x^15=x^(16-1)=x^16×x^(-1) so 4 squarings and a division or multiplication by inverse modulo if doing modular exponentiation. Finding addition chains that are optimal has been proven NP hard so it's not trivial with large exponents.