Karatsuba's Multiplication Trick Summarised in 1 Minute
Вставка
- Опубліковано 11 сер 2021
- #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.
E-Mail address: Nemean_YT@protonmail.com
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
Input is always at least 8 bits anyway, often more like 32.
Its not that complicated. Its easier than the one we are used. The problem here is that we cant try to use It without practice, cos this could take more time than our known method
I'm not too familiar with maths on that level but isn't it just like with most other computational tasks? It's always complexity vs storage.
@@lukasschwab8011 no, not necessarily. here the argument is about an algorythm with time complexity O(N²) vs O(N¹'⁵⁹). O notation is always true with large values of N, but not with small values. space complexity is not a factor here. a good example here are sorting algorythms. some are faster for smaller collections, while others are faster for larger collections.
@Alex Yeah, that's how I do mental math. Like 27 x 66 could seem "hard" to do efficiently in your head, but when you round just one of the numbers (whichever seems easiest to you) it becomes so much simpler.
I'd probably figure it in my head with these steps:
_Problem:_ 27 x 66 = ?
- 27 rounded to 30
- [Amount rounded = 3]
- (30 x 60 = 1800) + (30 x 6 = 180) = *(30 x 66 = 1980)*
- 66 x 3 _[amount rounded]_ = *198*
- 198 rounded to 200
- [Amount rounded = 2]
- 1980 - 200 = *1780*
- 1780 + 2 _[amount rounded]_ = *1782*
_Final answer:_ *27 x 66 = 1782*
When the world needed him most.. he returned
@@zappz8858 the UA-camr hasnt uploaded in 8 months
@LTrain45 45 not really going for originality
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.
EDIT: The video is out! Check it out at: ua-cam.com/video/cCKOl5li6YM/v-deo.html
@@prashant974 It's the $10,000 he won in a bet against the professor.
Ll
@Nemean You say the new algorithm uses three multiplications and then at 40" you show explicitly that it requires four multiplications!
@@gilbertanderson3456 The whole idea is that you don't have to calculate those four products explicitly. Only the sum is needed and that one, again, is calculated with one multiplication: (2+0)*(3+1).
@@gilbertanderson3456It only needs 3 *unique* multiplications: (labeling left parts a and c, and right parts b and d, the multiplications are- and you can see this by expanding (b+a*10^n)(d+c*10^n)= ac*10^2n+(ad+bc)*10^n+bd, where [and this was what makes his algorithm more efficient] Karatsuba rewrote the middle term as (a+b)(c+d) minus the other multiplications)
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.
makes sense
Thanks, this clarifies a lot. The "by subtracting both from the sum" part was not obvious in the vid.
This only made it harder
The only think I don't get is why (ad + bc) is one multiplication.
@@farrongoth6712
Because ac and bd can be stored after having calculated them in previous steps.
the legend is back
Your work is duly appreciated! Please make more videos!
He's back! More algorithmic optimisation, please!
I love that you wrote his name in his native language
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”.
I am a simple man. I see Nemean upload, I click!
I guess you didn't click that often in the last months
This channel never disappoints. But it's not clear to me how would this escalate to bigger numbers , with more digits.
If you start with 2 n-digit numbers, using this you can do 3 multiplications of size n/2 which requires 3(n/2)^2=3/4n^2 multiplications, but you can then use it on the numbers of size n/2 as well to get 9/16n^2, and keep repeating the process until the numbers become very small. So, if a number has size 2^n, using this we'll do 3^n multiplications instead of 4^n multiplications.
Somewhat similar logic was later followed by Volker Strassen to optimize matrix multiplication.
Hey happy you’re back!
It's just fascinating how such simple computations can be optimized further
We need more videos of this type
I knew that i've got the right decision to subscribe! This video appeared next day after that. Hope you'll make more content like the first one
finally, the legend has uploaded another video
if you're looking for exact values, Karatsuba multiplication is O(n^log2(3))
Your video about fast square root is sooooo good.
Wonderful explanation
I knew it was worth subscribing
I understand it now, u saw the og vid and got confused but i understand it now, tysm, ima use this FOREVER
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.
Brilliant video.
Wtf is this channel. I love it (even though only 2 Videos). Waited long for you to upload again
THE LEGEND IS BACK
Really cool!
I literally subscribed 8 hours ago, nice
If I am not wrong, this method of multiplication is also used in vedic arithmetic. I remember learning this.
Just... thank you
Legend is back
ah yes thanks. I um totally surely understand this now.
dude please keep uploading
Interesting fact!
Never thought multiplication could be done fast!
This really help for sure for programming...
another heavy process is division and root square...
Nemean's first video is about the Quake source code and its ingenious Fast Inverse Square Root calculations. Cool stuff! It addresses this by essentially calculating the square root to about a 1% margin of error using no division or built-in, slow square root calculations.
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!
he's taking the sum of the digits into the first multiplication. the expansion of (3+1)(2+0) in the animation is just so you realize that the remainder is actually also the sum of the products of the digits diagonally accross from each other. he doesn't actually do 2*3 + 2*1 + 3*0 + 0*1, he just does 2*4, then removes 2*3 and 0*1, so he ends up withthe result of 2*1 + 3*0, without having to do either multiplication (but of course he needs the first multiplication and an additional 2 additions and subtrations each)
It works because for really big numbers(which have hundreds of digits) multiplication takes much more time than adddition/subtraction (because to multiply you have to do much more operations) so doing 2 multiplications will be slower than doing 1 multiplication and 4 additions/subtractions.
Speed difference is just not that significant for little numbers, that's why you probably didn't understand
As others said, it's basically only good when that small speed difference can grow into significance. Not worth to use for high school, 5-8 digit multiplications.
@@CjqNslXUcM I think it was him showing the 2*3 + 2*1 + 3*0 + 0*1 that confused me. Ignoring that part made this method make a lot more sense, thanks!
The thing is, you only do 3 multiplications instead of 4. You get a few extra additions, but if you go to bigger numbers and apply this again, and again, and again, you end up with strictly fewer than N^2 operations on digits.
Thank you
yeaaaaaaahhhhh new video!!!!!!
How did I not see this
he is back
now im big brain
The teacher would probably give you an F since you didn’t use “Their Way” lmao
IKR! that's so damn annoying like their way is always longer sillier
keep the moronic "new math" slams to yourself. alternative ways of looking at problems, which is all 'new math' is, is exactly what this video is about. It just shows you don't know what you're talking about.
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!
Yes, it is said that on modern hardware it is more efficient for numbers around 300~400 bits, so it happens to be a good use-case for cryptography, where such numbers are common. Also I too am happy to be back and see my subscribers again.
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.:
635*121=(6*10^2+3*10^1+5*10^0)*(1*10^2+2*10^1+1*10^0) => [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
Legend
I've been staring at this for five minutes and I'm still utterly confused. I think the problem is this is not a good example problem, especially because both numbers are the same number of digits.
You pad them out to be the same number of digits. Put some extra zeros there. So 5 * 13 would be done as 05 * 13.
You uploaded again great! I have two questions for you:1. what program do you use to make these videos 2. why would you want to make these video? Just to share some interesting facts?
1.: Adobe After Effects & 2.: I'm searching for something great to do in my life, something that makes me stand out, something that I'll look back at and be proud. I don't know yet if starting a UA-cam channel is the right answer but I'm having fun so far. Hope that answers your question ;)
@@Nemean im pretty sure you are on your way to nail #2
Yes! Thank you for the answer!
Yooo he'a back
HES BACK!!!
Depending on what is the numbers I use different ways to calculate. And I count every single action in the calculus as one step.
lets take 21 x 32
21 x 30 = 630
21 x 2 = 42
630 + 42 = 672
That is a total of 3 steps.
Since you do 2 Multiplications, and 1 Additions.
Where the "normal" way, would be 4 Multiplications and 1 Additions (As in 1 x 2 = 2, 2 x 2 = 4 (Since you go from the back forward), gives 42, 3 x 1 = 30 (Since you jump one zero to make it the 10th), 3 x 2 = 600 (Because two 0s from the 20 and 30), giving 630. Then add them up 630 + 42 = 672).
So if we use this lets see.
21 x 32
2 x 3 + 2 x 2 + 3 x 1 + 1 x 2 (4 Multiplications)
6 + 7 + 2 (Remove additions)
672.
Like it works, but I find it to have the same amount technically to the old system, it is just a different process.
The method I tend to use;
You take the zeroes out of one side, then multiply with the remainder, then take the single integer to multiply with the other.
Like 120 x 35
1200 x 3 = 3600
120 x 5 = 600
3600 + 600 = 4200.
Of course, the larger the number, and the more zeroes there are, it becomes trickier, specially when doing it mentally.
your example for 21*32 is still 4 multiplications:
21*30 = 630 (2 multiplications, 2*3 and 1*3)
21*2 = 42 (2 multiplications, 2*2 and 1*2)
Karatsuba's algorithm uses only 3 multiplications:
2*3 = 6
1*2 = 2
(2 + 1)(3 + 2) - 6 - 2 = 7
600 + 70 + 2 = 672
Sr. You have a new suscriber
Please post more algorithm related content like the quake III algorithm
I don't understand how you get the middle digit? What does "subtract both from the sum" mean? Both what? Sum of what?
It's another way of saying sum the middle products. The full version of his sentence is: "subtract both (the first and last products, ie. [2×3 + 0×1] ) from the sum (ie. the whole line [2×3 + 2×1 + 3×0 + 0×1])" -- which leaves you with the sum of the middle products.
The quicker way to do this is, for any 2-digit by 2-digit multiplication, the product of the first/last digits = the first/last digit of the answer, and the sum of the cross products gives you the middle
@@DrRiq could you write out the sum and the subtractions with equations? I still don't understand. Also, if you need to calculate the four products (2x3, 2x1, 3x0, 0x1) then you are doing 4 multiplications, not 3. So I don't see where the speed up comes from.
@@aspuzling
The sum is equal to (2+0)×(3+1).
first = 2×3
last = 0×1
middle = (2+0)×(3+1) - first - last
You need 3 (single digit) multiplications.
@@aspuzling
. (2 + 0)
. | |
. V V
. × ×
. (3 + 1)
. | |
. V V
-> (2×3) _____ (0×1)
then for the middle, you do the cross multiplication, ie. (2×1)+(0×3)=2
So you get
. (2×3) _____ (0×1)
-> 6 _____ 0
-> 6 (2×1)+(0×3) 0
-> 6 2 0
@@RecursiveTriforce thanks! That's very cool. It really has no correlation to the words and images in this video as far as I can tell though.
I have a dislike in mathematics but this looks interesting!
I always use this trick when multiple by 11. 11*34=374=3 (3+4) 4. Didn’t know that it is also work with other numbers.
he lives!
i like this channel
ooh damn I come up with a similar process back high school.
yeah I guess for larger numbers its utility start to add up.
You... Uploaded???
More videos plss
Quick question about the runtime - does this mean that coding languages use this algorithm to compute multiplication when you ask it to do something like 12*13?
No. In practice (i.e. on computers) it becomes more efficient than the standard method for numbers around 300~400 bits, which just happens to be the kind of numbers used in cryptography. So there you can actually find Karatsuba's algorithm.
@@Nemean Super interesting. Thanks for the quick reply and I look forward to the longer vid! Your Quake algorithm video got me hooked
Coding languages don't do multiplications like 12*13 anyway, that's done directly by the CPU. You give the CPU the number 12, the number 13, call "MUL", and the CPU returns 156. Coding languages are used when multiplying 128-bit numbers, or larger, since the CPU can't easily do that. The CPU's MUL will often only work on 32-bit or 64-bit integers, depending on the CPU.
doesnt getting the first digit depend on carry though?
It does! If the middle "digit" turns out to be 14, you have to fix it by setting the middle digit to 4 and adding a carry to the first digit.
It's literally a visual of factoring done with numbers rather than variables.
how for 3 numbers?
Holy fuck! He made 2 videos in a row! Subscribe and wait, do more videos, you have good voice and montage skills bro! Dont stop!
My problem is at the thumbnail just ends at 273
Is this the same principle used by the Volker-Strasse matrix multiplication algorithm?
"Same" is maybe too strong, but yes, it's similar.
Buen video
What tool do you use for the animations?
Adobe After Effects
sickkkk
my 7th grade math teacher taught us this in middle school
Can anyone tell me what software is used in making this video
Adobe After Effects
@@Nemean thank you so much.
Basically like foil method
👍
0:45 where did the 2 come from I'm confused
After the subraction only 2*1 + 3*0 remains, which is just 2.
@@Nemean ok thx
MOOOOORRREEE!!
✅
Ya ya, ya ya, ya ya ya, I got it.
I hope I can be as smart as him
Tried the method in my brain for a simple 2 digit multiplication and wow the order of operation is indeed easier to picture.
Let's assume 23 x 42
The result will then be:
(2.4) (2.2 + 3.4) (3.2)
= 8 (16) 6
= 966
Let's try another 35 x 27
= (3.2) (5.2 + 3.7) (5.7)
= 6 (31) (35)
= 945
WHAAAT I DON'T NEED CALCULATOR NOW! 😭
that's the normal method, not Karatsuba's algorithm. You're still doing 4 multiplications
35*27 in Karatsuba's algorithm:
3*2 (3 + 5)(2 + 7) - 3*2 - 5*7 5*7
6 72 - 6 - 35 35
6 31 35
945
Sounds similar
Ah..
Konosuba 🙂
I'm confused. How is it only 3 multiplications? First Digit is one, last is one, middle is two?
You can get the middle digit "for free", as it comes from the big sum (1 multiplication) minus the two digits before (2 multiplications).
Ah now I get it I think.
(2+0)*(3+1)=8
8-6-0=2
But for carry digits it gets complicated:
64 x 13 =
First Digit: 6*1 = 6
Last digit: 3*4 = 12
Middle digit: (6+4)*(1+3) - 6 - 12 = 22
6 22 12; move carry digits (6+2) (2+1) 2 =
832
How would this work with larger numbers?
@@MatthiasFasching How this works for larger numbers would need to be explained in a longer video... *hint hint*
@@Nemean looking forward to it 😉
@@Nemean can't wait! Loved your Fast Inverse Square Root vid
This is in vedic math already!
From Wikipedia:
"Vedic Mathematics is a book written by the Indian monk Bharati Krishna Tirtha, and first published in 1965. It contains a list of mathematical techniques, which were falsely claimed to have been retrieved from the Vedas[1] and containing mathematical knowledge.[2]
Krishna Tirtha failed to produce the sources, and scholars unanimously note it to be a mere compendium of tricks for increasing the speed of elementary mathematical calculations sharing no overlap with historical mathematical developments during the Vedic period."
The book was published after Karatsuba invented the method.
When the harder is simpler for you.
someone needed to figure that elephant dung comes out at 6cm
This explanation is very confusing, I still don’t understand how you get the middle ‘2’
This is just supposed to be a summary/teaser of the main video. I recommend watching that one instead: ua-cam.com/video/cCKOl5li6YM/v-deo.html
Fastest algorithm: Calculator no jutsu
fast inverse square root
why does this seem similar to vedic multiplication to me?... hmm
Edit: anyone else feeling the same?
my eyes are blind
For (2+1)(1+3) can’t you use polynomial expansion, (a1*b1*100 + a1*b2*10 + a2*b1*10 + a2*b2*1)=273 to teach students to do it in their head. May not be efficient, but it’s intuitive.
Why so convoluted? 21x13 = 2*1+2*3+1*1+1*3. Do the first and last. 2 and 3. Do the two middle and add them. 6+1. Put that in between the numbers from before. 2 7 3
@@Paultimate7 Oh, that’s exactly what I did, I just used variables so you could use any two digit numbers, but yes that’s the trick: (2*1)*100 = 200, (2*3+1)*10 = 70, (1*3)*1 = 3. 200+70+3=273. Hmmm… I guess if you’re doing it in your head (not writing a computer program) you don’t have to think about using the 100 and 10 multipliers, so yeah, you’re right.
Doesn't seem to work.
Try 18 x 20
That's because I've glossed over the part where you have to carry.
The first digit is 1*2 = 2.
The last digit is 8*0 = 0.
The sum is (1+8)*(2+0) = 18 and subtracting both digits gives 16.
Now "16" is not a digit, 6 is. You just have to carry into the next, i.e. the first digit, so it becomes 3.
So therefore the digits are 3, 6 & 0. And indeed 18*20 = 360.
This video is just supposed to be a quick summary. I recommend you watch the full video (ua-cam.com/video/cCKOl5li6YM/v-deo.html) if you want a clearer explanation.
@@Nemean Thanks for the answering. I thought it is only useful in limited ways. 😅
where my fellow jp2gmd enjoyers at
For those who struggled like me maybe this will simplify (I had to re-watch many times);
Begin by finding the first and last digit, then find the middle digit. Our answer will be 620. How?
First digit: (a*c)=(2*3)=6
Last digit: (b*d)=(0*1)=0
So we have 6 ? 0
To find the middle digit: (a*d)-(b*c)=(2-0)=2
Therefor we have 6 2 0!
But this method is at least 400 years old. Google : vedic math.
From Wikipedia:
"Vedic Mathematics is a book written by the Indian monk Bharati Krishna Tirtha, and first published in 1965. It contains a list of mathematical techniques, which were falsely claimed to have been retrieved from the Vedas[1] and containing mathematical knowledge.[2]
Krishna Tirtha failed to produce the sources, and scholars unanimously note it to be a mere compendium of tricks for increasing the speed of elementary mathematical calculations sharing no overlap with historical mathematical developments during the Vedic period."
So no, it probably is not 400 years old. The book was published after Karatsuba invented the method.
normies when 0:35 becomes 0:37:
💗🌈💗🌈💗
160 +13 do it easier....