.jpg) |
| Анатолий Карацуба |
В данном топике изложу, как можно проще, суть метода быстрого умножения Карацубы и постараюсь объяснить, чем он лучше.
name='more'>
Для начала рассмотрим, как выполняется обычное умножение "столбиком". Пусть необходимо перемножить числа Xи Y. Представим их в виде:
- X = aT + b
- Y = cT + d
- X = 12 = 10 + 2
- Y = 34 = 30 + 4
XY = (aT + b)(cT + d) = acT2 + (ad + bc)T + bd
Таким образом мы выполняем 4 операции умножения. Для числе из нашего примера:
XY = acT2 + (ad + bc)T + bd = 1х3х102 + (1x4 + 2x3)x10 + 2x4 = 300 + 100 + 8 = 408
Теперь рассмотрим умножение методом Карацубы:
XY = acT2 + (ad + bc)T + bd = acT2 + ((a+b)(c+d) - ac - bd)T + bd
Заметим, что выполняются три операции умножения, вместо четырех. Таким образом сложность вычислений снижается с N2до Nlog(3). (Имеется ввиду двоичный логарифм).
Для чисел из примера:
XY = acT2 + ((a+b)(c+d) - ac - bd)T + bd = 1х3х102 +((1 + 2)(3 +4) - 1x3 - 2x4)x10 + 2x4 = 300 + (3x7 - 3 - 8)x10 + 8 = 300 + 100 + 8 = 408
Естественно, для числе малой разрядности метод Карацубы выглядит более громоздким и неудобным. Более того, для менее чем 32-разрядных (на 32-разрядной архитектуре) и менее 64-х разрядных (на 64-разрядной архитектуре) метод Карацубы, согласно моим опытам, проигрывает во времени умножению "в столбик". Но после этого порога наблюдается обратная тенденция. А с учетом того, что результаты разложения чисел, мы также можем перемножать методом Карацубы (до тех пор, пока их разрядность не опустится ниже разрядности архитектуры), то при переходе разрядности чисел в следующую степень двойки мы получаем скачок в разности скорости работы алгоритмов.
