Karatsuba algorithm
When we need to multiply 2 huge numbers, like 12093 * 23801, we can use the normal way we learned in school, which will cost nearly O(n^2), because each number should multiply with the other numbers. So if you have two big integers with a length of 100, it will cost you 10000 multiplication operations. Karatsuba algorithm is more optimizer because it cost O(n^1.58).
The logic behaind the Karastuba Algorithm
- Let's imagine we have a number with 2 digits like "23".
- We split the number into 2 parts: 2 and 3, we will call them a AND b.
- Now a = 2 and b = 3, and the original number = a * 10 + b;
- If we say that n is the length of the digit, then our original number is: a * 10^n/2 + b;
- If you confused you can calculate: a = 2, b = 3, n = 2 (the integer length) so 2 * 10^1 + 3 = 23.
- If we call our "23" number with x, we need to multibly it with another number y = 59.
- We will split y also so: c = 5, and d = 9; and y = c * 10^n/2 + d
- so now we can say: x x y = (a * 10^n/2 + b) . (c * 10^n/2 + d)
- When distributing the equation, we get: (a * 10^n/2 + b). (c * 10^n/2 + d) = (a*10^n/2).(c*10^n/2) + ad * 10^n/2 + bc * 10^n/2 + bd
- Now I want you to know that (a*10^n/2). (c*10^n/2) is the same as: a * 10^n/2 * c * 10^n/2; because we don't need priority for multiplication operations if the part just contains multiplication. so we can say: a * 10^n/2 * c * 10^n/2 = ac * 10^(2(n/2)).
- Also for this part: ad * 10^n/2 + bc * 10^n/2, we can devide the equation by 10^n/2 so it will be: 10^n/2(ad+bc).
- Let's improve the equation now, with the last 2 steps: ac * 10^(2(n/2))+ 10^(n/2). (ad+bc) + bd
- Now x.**y** = ac * 10^(2(n/2))+ 10^(n/2) . (ad+bc) + bd
- You cee that we need 3 important values: ac & db & (ad+bc). And the gift here is that we can do that by just 3 multiplication operations:
ac = karatsuba(a, c)//You can see that we will recursively use the Karatsuba algorithm.bd = karatsuba(b, d)ad_plus_bc = karatsuba(a+b, c+d) - ac - db// This looks strange, but you can see we multiply (a+b) with (c+d), then we subtract (ac) and (db), so why!!- Lets try to go throw the operation: (a+b) * (c+d) — ac — db = ac + ad + bc + bd — ac — db = ad + bc.
- So you can find that when we solve the operation we get the sum of the ad and bc in one step, and this makes our algorithm effective, because we replace 2 multiply operations a * d and b * c and then adding both with just one multiply operation.
Example
- x = 23 | y = 59
- a = 2 & b = 3
- c = 5 & d = 9
- ac = 10
- bd = 27
- a+b * c+d = 5 * 14
- Note that because the operation of a+b * c+d is not between numbers under than 10 (cause 14), we need to treat it as a separate multiply operation:
- x_ = 5 | y_ = 14
- a_ = 0 & b_ = 5
- c_ = 1 & d_ = 4
- a_ * c_ = 0
- b_ * d_ = 20
- a_ + b_ * c_ + d_ = 5 * 5 = 25
- a_ * d_ + b_ * c_ = (a_ + b_ * c_ + d_ ) — a_ * c — b_ * d_ = 25 — 0 — 20 = 5
- Apply the results in the equation: x_ * y_ = a_ * c_ * 10^(2(n/2)) + 10^(n/2) * (a_ * d_ + b_ * c_) + b_ * d_
- a_ * c_ * 10^(2(n/2))+ 10^(n/2) * (a_* d_ + b_ * c_) + b_ * d_ = 0 * 10^(2(2/2)) + 10^(2/2) * 5 + 20 = 50 + 20 = 70
- So now a+b * c+d = 70
- ad+bc = (a+b * c+d) — ac — bd = 70 — 10 — 27 = 33
- Apply the results in the equations: x.**y** = ac * 10^(2(n/2))+ 10^(n/2) . (ad+bc) + bd
- 10 * 10^(2(2/2)) + 10^(2/2) * 33 + 27 = 10 * 100 + 10 * 33 + 27 = 1000 + 330 + 27 = 1330 + 27 = 1357
- And yeah, this is the right answer: 1357.



