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

Учитывая две числовые строки A и B , задача состоит в том, чтобы эффективно найти произведение двух числовых строк.

Пример:

Input: A = 5678, B = 1234
Output: 7006652

Input: A = 74638463789, B = 35284567382
Output: 2633585904851937530398

Подход: данная проблема может быть решена с помощью алгоритма быстрого умножения Карастубы, идея состоит в том, чтобы добавить нули перед целыми числами так, чтобы оба целых числа имели равное и четное количество цифр n . После этого разделите числа следующим образом:

A =  Al * 10^n/2 + Ar    [Al and Ar contain leftmost and rightmost n/2 digits of A] 
B =  Bl * 10^n/2 + Br    [Bl and Br contain leftmost and rightmost n/2 digits of B]

• Следовательно, произведение А*В также можно представить следующим образом:

A * B = (Al * 10^n/2 + Ar) * (Bl * 10^n/2 + Br)
=> A * B = 10ⁿ*Al*Bl + 10^n/2*(Al*Br + Bl*Ar) + Ar*Br
=> A * B = 10ⁿ*Al*Bl + 10^n/2*((Al + Ar)*(Bl + Br) – Al*Bl – Ar*Br) + Ar*Br  [since Al*Br + Bl*Ar = (Al + Ar)*(Bl + Br) – Al*Bl – Ar*Br]

Обратите внимание, что приведенное выше выражение требует только трех умножений Al*Bl , Ar*Br и (Al + Ar)*(Bl + Br) вместо стандартных четырех. Следовательно, рекуррентность становится T(n) = 3T(n/2) + O(n) , а решение этой рекуррентности равно O(n ^1,59 ) . Эта идея более подробно обсуждалась в этой статье. Таким образом, вышеуказанная проблема может быть решена с помощью следующих шагов:

• Создайте функцию findSum() , которая находит сумму двух больших чисел, представленных в виде строк. Аналогичным образом создайте функцию findDiff() , которая находит разницу между двумя большими числами, представленными в виде строк.
• В рекурсивной функцииmulti(A,B) , которая умножает числа с использованием алгоритма Карацубы, сначала добавляются нули перед A и B , чтобы их цифры считались равными и четными.
• Затем вычислите значения Al , Ar , Bl и Br , как определено выше, и рекурсивно найдите значения умножения (Al, Bl) , умножения (Ar, Br) и умножения ((Al + Ar), (Bl + Br) ) и подставьте их значения в полученное выше уравнение.
• Выведите ответ на уравнение, удалив из него лидирующие нули.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ^{log 3} ) или O(N ^1,59 ), где N — максимальная длина заданных строк A и B.
Вспомогательное пространство: O(N ² )