Статьи

Алгоритм недели: быстрое умножение Карацубы

Октябрь 23, 2018

Вступление

Обычно умножение двух n-значных чисел требует n 2 умножений. Вот как мы, люди, умножаем числа. Давайте рассмотрим пример на случай, если нам нужно умножить два двузначных числа.

12 x 15 = ?

Хорошо, мы знаем, что ответ — 180, и есть много интуитивных методов, которые помогают нам получить правильный ответ. Действительно, 12 x 15 вычислить немного сложнее, чем 10 x 15, потому что умножить на 10 очень просто — мы просто добавляем один 0 в конце числа. Таким образом, 15 x 10 равняется 150. Но теперь снова 12 x 15 — мы знаем, что это равняется 10 x 15 (что составляет 150) и 2 x 15, что также очень легко вычислить, и оно равно 30. Результат 12 × 15 будет 150 + 30, что, к счастью, не сложно получить и равняется 180.

Это было легко, но в некоторых случаях вычисления немного сложнее, и нам нужен структурированный алгоритм, чтобы получить правильный ответ. Как насчет 65 х 97? Это не так просто, как 12 х 15, верно?

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

Типичное Умножение

Мы видим, что даже для двузначных чисел это довольно сложно — у нас есть 4 умножения и несколько сложений.

Количество умножений

Нам нужно 4 умножения, чтобы вычислить произведение двух двузначных чисел!

Однако пока мы знаем, как умножать числа, единственная проблема состоит в том, что наша задача становится очень трудной по мере роста чисел. Если умножить 65 на 97 было как-то легко, как насчет

374773294776321
x
222384759707982

Это кажется почти невозможным.

история

Андрей Колмогоров — один из самых ярких русских математиков 20-го века. В 1960 году во время семинара Колмогоров заявил, что два n-значных числа не могут быть умножены менее чем на n 2 умножений!
Только через неделю 23-летний молодой студент по имени Анатолий Алексеевич Карацуба доказал, что умножение двух n-значных чисел может быть вычислено с умножением n * lg (3) с изобретательным подходом «разделяй и властвуй».

обзор

По сути, Карацуба заявил, что если нам нужно умножить два n-значных числа x и y, это можно сделать с помощью следующих операций, предполагая, что B является основанием, а m <n.

Сначала оба числа x и y могут быть представлены как x1, x2 и y1, y2 по следующей формуле.

x = x1 * B^m + x2 
y = y1 * B^m + y2

Очевидно, что теперь xy станет следующим продуктом.

xy = (x1 * B^m + x2)(y1 * B^m + y2) =>
 
a = x1 * y1
b = x1 * y2 + x2 * y1
c = x2 * y2

В итоге xy станет:

xy = a * B^2m + b * B^m + c

Однако a, b и c могут быть вычислены по крайней мере с четырьмя умножениями, что не является большой оптимизацией. Вот почему у Карацубы возникла блестящая идея вычислить b по следующей формуле:

b = (x1 + x2)(y1 + y2) - a - c

Это использует только три умножения, чтобы получить ху.

Давайте посмотрим эту формулу на примере.

47 x 78
 
x = 47
x = 4 * 10 + 7
 
x1 = 4
x2 = 7
 
y = 78
y = 7 * 10 + 8
 
y1 = 7
y2 = 8
 
a = x1 * y1 = 4 * 7 = 28
c = x2 * y2 = 7 * 8 = 56
b = (x1 + x2)(y1 + y2) - a - b = 11 * 15 - 28 - 56

 

Now the thing is that 11 * 15 it’s again a multiplication between 2-digit numbers, but fortunately we can apply the same rules two them. This makes the algorithm of Karatsuba a perfect example of the “divide and conquer” algorithm.

Implementation

Standard Multiplication

Typically the standard implementation of multiplication of n-digit numbers require n2 multiplications as you can see from the following PHP implementation.

$x = array(1,2,3,4);
$y = array(5,6,7,8);
 
function multiply($x, $y)
{	
	$len_x = count($x);
	$len_y = count($y);
	$half_x = ceil($len_x / 2);
	$half_y = ceil($len_y / 2);
	$base = 10;
 
	// bottom of the recursion
	if ($len_x == 1 && $len_y == 1) {
		return $x[0] * $y[0];
	}
 
	$x_chunks = array_chunk($x, $half_x);
	$y_chunks = array_chunk($y, $half_y);
 
	// predefine aliases
	$x1 = $x_chunks[0];
	$x2 = $x_chunks[1];
	$y1 = $y_chunks[0];
	$y2 = $y_chunks[1];
 
	return  multiply($x1, $y1) * pow($base, $half_x * 2) 					// a
		 	+ (multiply($x1, $y2) + multiply($x2, $y1)) * pow($base, $half_x) 	// b
		 	+ multiply($x2, $y2);							// c
}
 
// 7 006 652
echo multiply($x, $y);

Karatsuba Multiplication

Karatsuba replaces two of the multiplications – this of x1 * y2 + x2 * y1 with only one – (x1 + x2)(y1 + y2) and this makes the algorithm faster.

$x = array(1,2,3,4);
$y = array(5,6,7,8);
 
function karatsuba($x, $y) 
{
	$len_x = count($x);
	$len_y = count($y);
 
	// bottom of the recursion
	if ($len_x == 1 && $len_y == 1) {
		return $x[0] * $y[0];
	} 
	if ($len_x == 1 || $len_y == 1) {
		$t1 = implode('', $x);
		$t2 = implode('', $y);
		return (int)$t1 * $t2;
	}
 
	$a = array_chunk($x, ceil($len_x/2));
	$b = array_chunk($y, ceil($len_y/2));
 
	$deg = floor($len_x/2);
 
	$x1 = $a[0];	// 1
	$x2 = $a[1];	// 2
	$y1 = $b[0];	// 1
	$y2 = $b[1];	// 2
 
	return  ($a = karatsuba($x1, $y1)) * pow(10, 2 * $deg)
			+ ($c = karatsuba($x2, $y2))
			+ (karatsuba(sum($x1, $x2), sum($y1, $y2)) - $a - $c) * pow(10, $deg);
}
 
// 7 006 652
echo karatsuba($x, $y);

 

Complexity

Assuming that we replace two of the multiplications with only one makes the program faster. The question is how fast. Karatsuba improves the multiplication process by replacing the initial complexity of O(n2) by O(nlg3), which as you can see on the diagram below is much faster for big n.

Сложность Карацубы

O(n^2) grows much faster than O(n^lg3)

Application

It’s obvious where the Karatsuba algorithm can be used. It is very efficient when it comes to integer multiplication, but that isn’t its only advantage. It is often used for polynomial multiplications.

Related posts:

  1. Computer Algorithms: Determine if a Number is Prime
  2. Computer Algorithms: Linear Search in Sorted Lists
  3. Computer Algorithms: Binary Search

You are a GREAT developer? Click here to answer the weekly quiz!

42
Share: