Тег «математика»

Алгоритм произведения Карацубы

Один из самых простых алгоритмов для перемножения тебе рассказали ещё в школе: перемножать в столбик.

А я сегодня хочу рассказать про алгоритм Карацубы, который немного сложнее, зато быстрее для компьютеров.

Дело в том, что складывать гораздо проще чем умножать.

Задача: перемножить два числа

На вход приходит два числа, $x$ и $y$, каждое из $n$ цифр. Случай, где надо перемножить числа с $n = 1$ тривиален, поэтому предположим $n >= 2$.

Как это сделать

Разобьём два этих числа пополам поциферно и назовём $a$, $b$, $c$, $d$. Это выглядит нагляднее на примере, перемножим $12$ и $34$: $12 \implies a=1, b=2$, а $34 \implies c=3, d=4$.

Из $a$ и $b$ легко собрать обратно $x$: $10^{n/2}a + b$.

Давайте запишем произведение $x$ и $y$ в этом виде, получим:

$$ x \times y = (10^{n/2}a + b) \times (10^{n/2}c + d) $$

И развернём скобки:

$$ (10^{n/2}a + b) \times (10^{n/2}c + d) = 10^{n}ac + 10^{n/2}bc + 10^{n/2}ad + bd $$

Вынесем $10^{n/2}$ за скобки:

$$ 10^{n}ac + 10^{n/2}bc + 10^{n/2}ad + bd = 10^{n}ac + 10^{n/2}(bc + ad) + bd $$

Пока всё хорошо и довольно понятно: чтобы получить результат, нужно посчитать $ac$, $bd$, $bc + ad$, подвигать разрядами ($10^{n}a$ — это $a$ с дополнительными $n$ нулями) и сложить.

Но дальше идёт то, в чём и заключается «фишка» алгоритма, мы не будем считать $bc + ad$ (это ещё две операции умножения!), давайте посчитаем $(a+b)\times(c+d)$ — это же всего одна операция умножения (и две операции сложения, но складывать «дешевле», чем перемножать). ($ac$ и $bd$ всё же придётся посчитать честно.)

Теперь развернём скобки у $(a+b)\times(c+d)$:

$$ (a+b)\times(c+d) = ac + bc + ad + bd $$

И вычтем $ac$ и $bd$ — тогда у нас останется $bc + ad$, что нам и нужно, и мы сможем дописать нужные нули и сложить все три величины, чтобы получить результат.

Таким образом, чтобы посчитать $xy$, нужно:

  1. Разбить $x$ на $a$ и $b$, $y$ — на $c$ и $d$.
  2. Посчитать $ac$.
  3. Посчитать $bd$
  4. Посчитать $(a+b)\times(c+d)$
  5. Посчитать $(4) - (3) - (2)$
  6. Сложить $10^{n}ac + 10^{n/2}((4) - (3) - (2)) + bd$

Пример: $60403122 \times 23224568$

Чтобы было нагляднее, давайте перемножим два числа, например, $60403122 \times 23224568$ (получается, что $n = 8$):

  1. Разобьём поциферно: $a = 6040, b = 3122; c = 2322, d = 4568$.
  2. $ac = 6040 \times 2322 = 14024880$
  3. $bd = 3122 \times 4568 = 14261296$
  4. $a+b = 9162; c+d = 6890; (a+b)*(c+d) = 63126180;$
  5. $$(a+b)*(c+d) - bd - ac = 63126180 - 14261296 - 14024880 = 34840004$$
  6. Сдвигаем и складываем:
  7. $10^{8}14024880=1402488000000000$.
  8. $10^{4}34840004=348400040000$
  9. $6.1 + 6.2 + bd = 1402836414301296$

Если удобнее в столбик, то вот:

  1402488000000000 (6.1 + 6.2)
+ 0000348400040000
------------------
  1402836400040000

  1402836400040000 ((6.1 + 6.2) + bd)
+ 0000000014261296
-------------------
  1402836414301296

И $1402836414301296$ и будет нашим результатом.