Karatsuba's Multiplication Trick Summarised in 1 Minute

#VeritasiumContest

When soviet mathematician Kolmogorov set out to prove that there exists no faster multiplication method than the standard one we learn in elementary school, a young student by the name of Karatsuba, also trying to find a proof, managed to find a trick that beats the standard method. This video explains the high-level idea and the insight of Karatsuba's multiplication algorithm.

[Nemean]

This is just a cute, shareable summary of the main video that also happens to be a submission to Veritasium's contest. The full explanation of Karatuba's multiplication algorithm will be released in the upcoming days.

[Lemon_Inspector]

This can be used to illustrate two important points about program optimization.
1. Faster algorithms tend to be more complicated,
2. Unless the input is very large, the complicated algorithms aren't worth the effort

[SanoKei]

When the world needed him most.. he returned

[RecursiveTriforce]

STEP-BY-STEP

Here's a step-by-step for why this works and why there are only 3 multiplications if you too are still a bit confused or want detail.


(10a+b) × (10c+d)
= 100(ac) + 10(ad) + 10(bc) + (bd)
= 100(ac) + 10(ad + bc) + (bd)


(ad + bc) can now be replaced with ( (a+b) × (c+d) - ac - bd ). To see why this is possible look below at [Derivation].

But this leads us to the final form of
100(ac) + 10((a+b) × (c+d) - ac - bd) + (bd)
which uses only 3 unique multiplications with numbers that aren't a power of the base (1, 10, 100, ...). The values of a×c and b×d can be reused.


Derivation:

(a+b) × (c+d)
= (ac) + (ad) + (bc) + (bd)

| - ac | - bd
on both sides

(a+b) × (c+d) - ac - bd
= (ad + bc)


I hope this clears it up a bit.

[sm]

He's back! More algorithmic optimisation, please!

[cafebrasileiro]

This channel never disappoints. But it's not clear to me how would this escalate to bigger numbers, with more digits.

[GetPastTheMonkey]

I am a simple man. I see Nemean upload, I click!

[ruzgar]

I love how small fundamental optimizations like this are what's required for computers to thrive

[shritishaw]

this is my first video in order to understand Karatsuba's multiplication algorithm, and this is also my last video on this algorithm. Thanks a lot for this lucid explanation.

[esepecesito]

Somewhat similar logic was later followed by Volker Strassen to optimize matrix multiplication.

[uberfella]

I love that you wrote his name in his native language

[imsamuka]

Very cool! I wonder if i can use it daily, but appears a little harder, maybe with more digits it is more effective. Congrats for the return!

[kernelx]

Your work is duly appreciated! Please make more videos!

[nihalbhandary]

If I am not wrong, this method of multiplication is also used in vedic arithmetic. I remember learning this.

[not_herobrine]

finally, the legend has uploaded another video

[DaggerMan-ovvf]

The teacher would probably give you an F since you didn’t use “Their Way” lmao

[sargentscythe]

The way this explained it is unclear to me where the difference in speed comes from between the first and second method. I'm excited for the full video!

Edit: New video was great and made a lot of sense, go check it out!

[NonTwinBrothers]

I literally subscribed 8 hours ago, nice

[jakoblenke]

This is essentially the algorithm for convolution, where the coeffitients of a resulting polynomial, where the basis is 10 HERE but arbitrary, is just the convolution of thes coeffitients of the two polinomials to be multiplied e.g.:
=> [6, 3, 5]*[1, 2, 1]=[6, 15, 17, 13, 5]=>(6*10^4+15*10^3+17*10^2+13*10^1+5*10^0)=(7*10^4+6*10^3+8*10^2+3*10^1+5*10^0)=76835

[abhishekprakash]

Actual there is nothing fancy about this method .This method has been derived in Ancient India as part of vedic mathematics . Each of this algorithm is referred as sutras, using the sutras you can perform any computation in fraction of sec ...which is in a way same as karatsuba's multiplication. Btw this Karatsuba's Multiplication is known as "Urdhva-Tiryagbhyam" which means “vertically and crosswise”.