資料結構
網路
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 次瀏覽
