数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Karatsuba算法用于快速乘法大型十进制数（表示为字符串）
我们无法将大型十进制数存储在普通数据类型（如int或long long）中，因此我们将其存储在字符串中。当我们乘以两个以字符串形式表示的整数时，需要花费大量时间，更具体地说，是N*M，其中N是给定字符串的大小。在本文中，我们将实现Karatsuba算法，用于快速乘法以字符串形式表示的大型十进制数。
输入
string num1 = "34984" string num2 = "937488"
输出
32797080192
解释
我们将了解乘法的算法。
Karatsuba算法
根据该算法，我们将使两个字符串具有相同的长度（在较小数字的前面添加一些额外的零），并且我们需要两个字符串的长度为偶数，因此，如果较大的字符串长度不是偶数，则可以在其前面添加一个额外的零。
现在，我们可以将两个数字分解为
$\mathrm{N_{1}=10^{N/2}*Nl_{1}+Nr_{1}}$ 这里Nl1表示给定数字的前n/2位数字，NR1表示给定数字的后n/2位数字，这意味着我们将当前数字分成了两等份。
例如：1234可以写成$(\mathrm{12\:*10^2\:+\:34})$。
类似地，第二个数字写成
$\mathrm{N_{2}=10^{N/2}*Nl_{2}+Nr_{2}}$
现在，这两个数字的乘积是
$\mathrm{=>N_{1}*N_{2}=(10^{n/2}*Nl_{1}+Nr_{1})*(10^{n/2}*Nl_{2}+Nr_{2})}$
$\mathrm{=(10^{n}*Nl_{1}*Nl_{2})+10^{n/2}((Nl_{2}*Nr_{1})+(Nl_{1}*Nr_{2}))+(Nr_{2}*Nr_{1})}$
$\mathrm{=>(Nl_{2}*Nr_{1})+(Nl_{1}*Nr_{2})}$ 可以写成
$\mathrm{=(Nl_{1}*Nr_{1})*(Nl_{2}*Nr_{2})-(Nl_{1}*Nr_{1})-(Nl_{2}*Nr_{2})}$
因此，我们的最终方程是
$\mathrm{=>N_{1}*N_{2}=(10^{n}*Nl_{1}*Nl_{2})+(Nr_2*Nr_1)+10^{n/2}((Nl_{1}*Nr_{1})*(Nl_{2}*Nr_{2})-(Nl_{1}*Nr_{1})-(Nl_{2}*Nr_{2}))} $
从上面的等式中，我们可以看到我们只需要进行三次乘法，而不是四次乘法，我们只需要进行三次乘法，并且我们需要递归进行，这使得递归方程的形式为
$$\mathrm{=>T(n)=3T(n/2)+O(n)}$$
示例
#include <bits/stdc++.h>
using namespace std;
// creating a function to get the addition of the integers passed as parameters in the form of the string
string Sum(string str1, string str2){
// for easy processing, making second string greater
if (str1.size() > str2.size()){
swap(str2,str1);
}
string sum = ""; // string to store the sum
int len1 = str1.length(); // variable to get the size of the first string
int len2 = str2.length(); // variable to get the size of the second string
// reversing both strings to get the sum
reverse(str1.begin(), str1.end());
reverse(str2.begin(), str2.end());
int carry = 0; // variable to store the carry
// traversing over the first string
for (int i = 0; i< len1; i++){
int temp = ((str1[i] - '0') + (str2[i] - '0') + carry);
sum.push_back(temp % 10 + '0');
carry = temp / 10;
}
// traversing over the second string
for (int i = len1; i< len2; i++){
int temp = ((str2[i] - '0') + carry);
sum.push_back(temp % 10 + '0');
carry = temp / 10;
}
// if carry is not zero
if (carry){
sum.push_back(carry + '0');
}
// reverse the sum string
reverse(sum.begin(), sum.end());
return sum;
}
// create a function to find the difference between the given numbers
string Diff(string str1, string str2){
string ans = ""; // string to store the answer
// getting length of both the strings
int len1 = str1.length();
int len2 = str2.length();
// reversing both the given strings
reverse(str1.begin(), str1.end());
reverse(str2.begin(), str2.end());
int carry = 0;
// traversing over the second string and subtracting the first string
for (int i = 0; i< len2; i++){
int temp = ((str1[i] - '0') - (str2[i] - '0') - carry);
// if the subtraction value is less than 0 then add 10 into the variable sub and mark the carry as 1
if (temp < 0) {
temp = temp + 10;
carry = 1;
} else{
carry = 0;
}
ans.push_back(temp + '0');
}
// subtracting the carry from the greater number
for (int i = len2; i< len1; i++) {
int temp = ((str1[i] - '0') - carry);
// If the sub value is -ve, then make it positive
if (temp < 0) {
temp = temp + 10;
carry = 1;
} else{
carry = 0;
}
ans.push_back(temp + '0');
}
reverse(ans.begin(), ans.end()); // reversing the ans string
return ans; // Return answer
}
// creating the function for removal of the zeroes
string removeZeros(string s){
// using regex pattern to remove the zeroes
const regex pattern("^0+(?!$)");
s = regex_replace(s, pattern, "");
return s;
}
// creating the function to multiply the given numbers
string multiply(string num1, string num2){
if (num1.length() > num2.length()){
swap(num1,num2); // getting the second string with greater size
}
// getting length of the numbers and making their size equal
int len1 = num1.length(), len2 = num2.length();
while (len2 > len1) {
num1 = "0" + num1;
len1++;
}
// if their size is one implement the base condition
if (len1 == 1) {
// converting to numbers and returning the results
int res = stoi(num1) * stoi(num2);
return to_string(res);
}
// makking length odd for the strings
if (len1 % 2 == 1) {
len1++;
num1 = "0" + num1;
num2 = "0" + num2;
}
// defining different types of strings that are needed according to the equaltion
string N1l, N1r, N2l, N2r;
// finding the values of all the above strings
for (int i = 0; i< len1 / 2; i++){
N1l += num1[i];
N2l += num2[i];
N1r += num1[len1 / 2 + i];
N2r += num2[len1 / 2 + i];
}
// recursively calling to the function, to get the required product getting the value of N1l * N2l
string a = multiply(N1l, N2l);
// getting the value of N1r * N2r
string b = multiply(N1r, N2r);
// gettign the value of the third condition
string c = Diff(multiply(Sum(N1l, N1r), Sum(N2l, N2r)),Sum(a, b));
// Multiply a by 10^len1 by adding zeroes in the end of a
for (int i = 0; i< len1; i++){
a = a + "0";
}
// Multiply b by 10^(len1/2) by adding zeroes in the end of b
for (int i = 0; i< len1 / 2; i++){
c = c + "0";
}
// getting sum of all the given strings
string res = Sum(a, Sum(b, c));
// Remove leading zeroes from the result
res = removeZeros(res);
return res;
}
int main(){
string num1 = "34984";
string num2 = "937488";
// calling the function
cout<<"The multiplication value of the given numbers is "
<<multiply(num1,num2)<<endl;
return 0;
}
输出
The multiplication value of the given numbers is 32797080192
结论
在本教程中，我们实现了Karatsuba算法，用于快速乘法以字符串形式表示的大型十进制数。当我们乘以两个以字符串形式表示的整数时，需要花费大量时间，更具体地说，是N*M，其中N是给定字符串的大小。Karatsuba算法需要O(N^(1.59))时间。
327 次浏览
