Блог пользователя Ahmed_Mohamed_Al3adl

Автор Ahmed_Mohamed_Al3adl, история, 19 месяцев назад, По-английски

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.
  • Проголосовать: нравится
  • -28
  • Проголосовать: не нравится