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
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
@@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*
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: th-cam.com/video/cCKOl5li6YM/w-d-xo.html
@@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.
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.
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.
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
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.
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 TH-cam channel is the right answer but I'm having fun so far. Hope that answers your question ;)
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.
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.
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.
@@aspzx . (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
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.
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.
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.
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.
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”.
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.
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?
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 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 (th-cam.com/video/cCKOl5li6YM/w-d-xo.html) if you want a clearer explanation.
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.
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.
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.
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!
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*
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: th-cam.com/video/cCKOl5li6YM/w-d-xo.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)
When the world needed him most.. he returned
@Andrew Ramshaw the TH-camr hasnt uploaded in 8 months
@LTrain45 45 not really going for originality
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
He's back! More algorithmic optimisation, please!
I am a simple man. I see Nemean upload, I click!
I guess you didn't click that often in the last months
Your work is duly appreciated! Please make more videos!
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.
Hey happy you’re back!
I love that you wrote his name in his native language
I love how small fundamental optimizations like this are what's required for computers to thrive
I knew it was worth subscribing
finally, the legend has uploaded another video
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.
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.
Somewhat similar logic was later followed by Volker Strassen to optimize matrix multiplication.
We need more videos of this type
I understand it now, u saw the og vid and got confused but i understand it now, tysm, ima use this FOREVER
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.
Wtf is this channel. I love it (even though only 2 Videos). Waited long for you to upload again
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
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
It's just fascinating how such simple computations can be optimized further
Your video about fast square root is sooooo good.
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 LEGEND IS BACK
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 TH-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!
ah yes thanks. I um totally surely understand this now.
Really cool!
Wonderful explanation
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.
Legend is back
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.
@@aspzx
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.
@@aspzx
. (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.
yeaaaaaaahhhhh new video!!!!!!
Just... thank you
Brilliant video.
dude please keep uploading
Yooo he'a 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
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.
i like this channel
Sr. You have a new suscriber
You... Uploaded???
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.
I have a dislike in mathematics but this looks interesting!
he is back
you're multiplying by 20.
JUST INCREMENT AND MULTIPLY BY TWO- (internal anger)
HES BACK!!!
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!
Never thought multiplication could be done fast!
My problem is at the thumbnail just ends at 273
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.
Thank you
Interesting fact!
Please post more algorithm related content like the quake III algorithm
which program did u use for visualizing the content?
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”.
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.
now im big brain
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.
How did I not see this
if you're looking for exact values, Karatsuba multiplication is O(n^log2(3))
Cgnh
Legend
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
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
Is this the same principle used by the Volker-Strasse matrix multiplication algorithm?
"Same" is maybe too strong, but yes, it's similar.
my eyes are blind
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
yeah I guess for larger numbers its utility start to add up.
It's literally a visual of factoring done with numbers rather than variables.
More videos plss
Sounds similar
Ah..
Konosuba 🙂
how for 3 numbers?
ooh damn I come up with a similar process back high school.
he lives!
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: th-cam.com/video/cCKOl5li6YM/w-d-xo.html
Can anyone tell me what software is used in making this video
Adobe After Effects
@@Nemean thank you so much.
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 (th-cam.com/video/cCKOl5li6YM/w-d-xo.html) if you want a clearer explanation.
@@Nemean Thanks for the answering. I thought it is only useful in limited ways. 😅
Basically like foil method
Ya ya, ya ya, ya ya ya, I got it.
When the harder is simpler for you.
Fastest algorithm: Calculator no jutsu
someone needed to figure that elephant dung comes out at 6cm
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.
Buen video
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.
MOOOOORRREEE!!
my 7th grade math teacher taught us this in middle school
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.
why does this seem similar to vedic multiplication to me?... hmm
Edit: anyone else feeling the same?
I hope I can be as smart as him
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!
sickkkk
middle digit was poorly explained
345 x 18 = 690 x 9 = 6210
.
345 x 18 =
(345 x 20) - (345 x 2) =
6900 - 690 = 6210
.
345 x 18 =
(345 x 10) + (345 x 8) =
3450 + 2760 = 6210
.
5. 1
4. 5 8
3. 4. 40
3. 32
24
3. 28. 37 40
V V V
6 2 1 0
160 +13 do it easier....
fast inverse square root
✅