Обычно умножение двух 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
Теперь дело в том, что 11 * 15 — это снова умножение двухзначных чисел, но, к счастью, мы можем применить те же правила к двум из них. Это делает алгоритм Карацубы прекрасным примером алгоритма «разделяй и властвуй».
Реализация
Стандартное Умножение
Обычно стандартная реализация умножения n-значных чисел требует n 2 умножений, как вы можете видеть из следующей реализации PHP .
$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);
Каратсуба Умножение
Карацуба заменяет два умножения — это x1 * y2 + x2 * y1 только одним — (x1 + x2) (y1 + y2), и это делает алгоритм быстрее.
$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);
сложность
Предполагая, что мы заменим два умножения только одним, программа будет работать быстрее. Вопрос в том, насколько быстро. Каратсуба улучшает процесс умножения, заменяя начальную сложность O (n 2 ) на O (n lg3 ), которая, как вы можете видеть на диаграмме ниже, намного быстрее для больших n.
O (n ^ 2) растет намного быстрее, чем O (n ^ lg3)
заявка
Очевидно, где можно использовать алгоритм Карацубы. Это очень эффективно, когда дело доходит до целочисленного умножения, но это не единственное его преимущество. Это часто используется для полиномиальных умножений.
Похожие сообщения: