الگوریتم کاراتسوبا برای ضرب سریع — راهنمای کاربردی
در این مطلب، الگوریتم کاراتسوبا برای ضرب سریع اعداد آموزش داده شده است. دو رشته دودویی داده شده که مقدار دو عدد صحیح را نشان می‌دهند. هدف، پیدا کردن حاصل ضرب دو رشته است. برای مثال، اگر رشته بیتی اول «۱۱۰۰» و رشته بیتی دوم «۱۰۱۰» باشد، خروجی باید ۱۲۰ باشد. برای سادگی بیشتر، طول هر دو رشته برابر و مساوی ۱۲۰ در نظر گرفته می‌شود.
یک روش استفاده، راهکاری است که در دوران مدرسه نیز به بسیاری از افراد آموزش داده شده است. یعنی، یکی یکی همه بیت‌های عدد دوم گرفته می‌شود و با همه بیت‌های عدد اول ضرب می‌شوند. در نهایت، حاصل ضرب‌ها با یکدیگر جمع می‌شود. این الگوریتم از درجه O(n^2) است.
با استفاده از روش «تقسیم و حل» (Divide and Conquer)، می‌توان دو عدد صحیح را با پیچیدگی زمانی کمتری ضرب کرد. اعداد داده شده به دو نیمه تقسیم می‌شوند. فرض می‌شود که اعداد داده شده، X و Y باشند. برای سادگی بیشتر، فرض می‌شود که n عددی زوج است.
X = Xl*2n/2 + Xr [Xl and Xr contain leftmost and rightmost n/2 bits of X] Y = Yl*2n/2 + Yr [Yl and Yr contain leftmost and rightmost n/2 bits of Y]
حاصل ضرب XY را می‌توان به صورت زیر نوشت.
XY = (Xl*2n/2 + Xr)(Yl*2n/2 + Yr) = ۲n XlYl + 2n/2(XlYr + XrYl) + XrYr
اگر نگاهی به رابطه بالا انداخته شود، می‌توان دید که ۴ ضرب از اندازه n/2 انجام می‌شود. بنابراین، اساسا مساله‌ای با اندازه n به چهار زیر مسئله با اندازه n/2 تقسیم می‌شود. اما این موضوع کمکی نمی‌کند، زیرا راهکار بازگشتی، T(n) = 4T(n/2) + O(n) و از درجه O(n^2) است. بخش جالب این الگوریتم، تغییر دادن دو عبارت میانی به اشکال دیگری است که با استفاده از آن و تنها با یک ضرب بیشتر، روش موثر واقع خواهد شد. در ادامه، عبارت جالب مورد استفاده برای میانه دو عبارت، آورده شده است.
XlYr + XrYl = (Xl + Xr)(Yl + Yr) – XlYl- XrYr
بنابراین، مقدار نهایی XY به صورت زیر خواهد بود.
XY = 2n XlYl + 2n/2 * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr
با استفاده از ترفند بالا، تکرار به صورت T(n) = 3T(n/2) + O(n) خواهد بود و راهکار این تکرار به صورت O(n1.59) است. اما اگر طول رشته‌های ورودی متفاوت و زوج نباشد چه می‌شود؟ برای مدیریت بحث تفاوت طول، oها به ابتدا الحاق می‌شود. برای مدیریت طول فرد، بیت‌های floor(n/2) در نیمه سمت چپ و بیت‌های ceil(n/2) در نیمه سمت راست قرار داده می‌شود. بنابراین، عبارت XY به صورت زیر تغییر می‌کند.
XY = 22ceil(n/2) XlYl + 2ceil(n/2) * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr
الگوریتم ارائه شده در بالا، الگوریتم کاراتسوبا است و کاربردهای گوناگونی دارد. در ادامه، پیاده‌سازی ++C الگوریتم بالا، ارائه شده است
// C++ implementation of Karatsuba algorithm for bit string multiplication.
#include<iostream>
#include<stdio.h>
using namespace std;
// FOLLOWING TWO FUNCTIONS ARE COPIED FROM http://goo.gl/q0OhZ
// Helper method: given two unequal sized bit strings, converts them to
// same length by adding leading 0s in the smaller string. Returns the
// the new length
int makeEqualLength(string &str1, string &str2)
{
int len1 = str1.size();
int len2 = str2.size();
if (len1 < len2)
{
for (int i = 0 ; i < len2 - len1 ; i++)
str1 = '0' + str1;
return len2;
}
else if (len1 > len2)
{
for (int i = 0 ; i < len1 - len2 ; i++)
str2 = '0' + str2;
}
return len1; // If len1 >= len2
}
// The main function that adds two bit sequences and returns the addition
string addBitStrings( string first, string second )
{
string result; // To store the sum bits
// make the lengths same before adding
int length = makeEqualLength(first, second);
int carry = 0; // Initialize carry
// Add all bits one by one
for (int i = length-1 ; i >= 0 ; i--)
{
int firstBit = first.at(i) - '0';
int secondBit = second.at(i) - '0';
// boolean expression for sum of 3 bits
int sum = (firstBit ^ secondBit ^ carry)+'0';
result = (char)sum + result;
// boolean expression for 3-bit addition
carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry);
}
// if overflow, then add a leading 1
if (carry) result = '1' + result;
return result;
}
// A utility function to multiply single bits of strings a and b
int multiplyiSingleBit(string a, string b)
{ return (a[0] - '0')*(b[0] - '0'); }
// The main function that multiplies two bit strings X and Y and returns
// result as long integer
long int multiply(string X, string Y)
{
// Find the maximum of lengths of x and Y and make length
// of smaller string same as that of larger string
int n = makeEqualLength(X, Y);
// Base cases
if (n == 0) return 0;
if (n == 1) return multiplyiSingleBit(X, Y);
int fh = n/2; // First half of string, floor(n/2)
int sh = (n-fh); // Second half of string, ceil(n/2)
// Find the first half and second half of first string.
// Refer http://goo.gl/lLmgn for substr method
string Xl = X.substr(0, fh);
string Xr = X.substr(fh, sh);
// Find the first half and second half of second string
string Yl = Y.substr(0, fh);
string Yr = Y.substr(fh, sh);
// Recursively calculate the three products of inputs of size n/2
long int P1 = multiply(Xl, Yl);
long int P2 = multiply(Xr, Yr);
long int P3 = multiply(addBitStrings(Xl, Xr), addBitStrings(Yl, Yr));
// Combine the three products to get the final result.
return P1*(1<<(2*sh)) + (P3 - P1 - P2)*(1<<sh) + P2;
}
// Driver program to test above functions
int main()
{
printf ("%ld\n", multiply("1100", "1010"));
printf ("%ld\n", multiply("110", "1010"));
printf ("%ld\n", multiply("11", "1010"));
printf ("%ld\n", multiply("1", "1010"));
printf ("%ld\n", multiply("0", "1010"));
printf ("%ld\n", multiply("111", "111"));
printf ("%ld\n", multiply("11", "11"));
}خروجی قطعه کد بالا، به صورت زیر است.
۱۲۰ ۶۰ ۳۰ ۱۰ ۰ ۴۹ ۹
پیچیدگی زمانی این روش از درجه O(nlog23) = O(n1.59) است. پیچیدگی زمان را می‌توان با استفاده از الگوریتم تقسیم و حل دیگری، یعنی «تبدیل فوریه سریع» (Fast Fourier Transform)، بهبود بخشید.
تمرین با جواب
الگوریتم بالا یک مقدار long int باز می‌گرداند و برای رشته‌های بزرگ کارآمد نیست. هدف، بسط دادن الگوریتم بالا به گونه‌ای است که یک رشته را به جای مقدار long int باز گرداند.
پاسخ: فرایند ضرب برای اعداد بزرگ مسئله مهمی در علم کامپیوتر است. در ادامه، رویکردی ارائه شده است که از متدولوژی تقسیم و حل استفاده می‌کند. برای درک بهتر تفاوت پیچیدگی زمانی ضرب دودویی معمولی و الگوریتم کاراتسوبا، می‌توان کد کامل موجود در مخزن را اجرا کرد.
مثال:
Fist Binary Input : 101001010101010010101001010100101010010101010010101 Second Binary Input : 101001010101010010101001010100101010010101010010101 Decimal Output : Not Representable Output : 2.1148846e+30
Fist Binary Input : 1011 Second Binary Input : 1000 Decimal Output : 88 Output : 5e-05
پیاده‌سازی روش دوم در ++C
#include <iostream>
#include <ctime>
#include <fstream>
#include <string.h>
#include <cmath>
#include <sstream>
using namespace std;
// classical method class
class BinaryMultiplier
{
public:
string MakeMultiplication(string,string);
string MakeShifting(string,int);
string addBinary(string,string);
void BinaryStringToDecimal(string);
};
// karatsuba method class
class Karatsuba
{
public:
int lengthController(string &,string &);
string addStrings(string,string);
string multiply(string,string);
string DecimalToBinary(long long int);
string Subtraction(string,string);
string MakeShifting(string,int);
};
// this function get strings and go over str2 bit bit
// if it sees 1 it calculates the shifted version according to position bit
// Makes add operation for binary strings
// returns result string
string BinaryMultiplier::MakeMultiplication(string str1, string str2)
{
string allSum = "";
for (int j = 0 ; j<str2.length(); j++)
{
int secondDigit = str2[j] - '0';
if (secondDigit == 1)
{
string shifted = MakeShifting(str1,str2.size()-(j+1));
allSum = addBinary(shifted, allSum);
}
else
{
continue;
}
}
return allSum;
}
// this function adds binary strings with carry
string BinaryMultiplier::addBinary(string a, string b)
{
string result = "";
int s = 0;
int i = a.size() - 1;
int j = b.size() - 1;
while (i >= 0 || j >= 0 || s == 1)
{
s += ((i >= 0)? a[i] - '0': 0);
s += ((j >= 0)? b[j] - '0': 0);
result = char(s % 2 + '0') + result;
s /= 2;
i--;
j--;
}
return result;
}
// this function shifts the given string according to given number
// returns shifted version
string BinaryMultiplier::MakeShifting(string str, int stepnum)
{
string shifted = str;
for (int i = 0 ; i < stepnum ; i++)
shifted = shifted + '0';
return shifted;
}
// this function converts Binary String Number to Decimal Number
// After 32 bits it gives 0 because it overflows the size of int
void BinaryMultiplier::BinaryStringToDecimal(string result)
{
cout<<"Binary Result : "<<result<<endl;
unsigned long long int val = 0;
for (int i = result.length()-1; i >= 0; i--)
{
if (result[i] == '1')
{
val += pow(2,(result.length()-1)-i);
}
}
cout<<"Decimal Result (Not proper for Large Binary Numbers):" <<val<<endl;
}
// this function controls lengths of strings and make their lengths equal
// returns the maximum length
int Karatsuba::lengthController(string &str1, string &str2)
{
int len1 = str1.size();
int len2 = str2.size();
if (len1 < len2)
{
for (int i = 0 ; i < len2 - len1 ; i++)
str1 = '0' + str1;
return len2;
}
else if (len1 > len2)
{
for (int i = 0 ; i < len1 - len2 ; i++)
str2 = '0' + str2;
}
return len1;
}
// this function add strings with carry
// uses one by one bit addition methodology
// returns result string
string Karatsuba::addStrings(string first, string second)
{
string result; // To store the sum bits
// make the lengths same before adding
int length = lengthController(first, second);
int carry = 0; // Initialize carry
// Add all bits one by one
for (int i = length-1 ; i >= 0 ; i--)
{
int firstBit = first.at(i) - '0';
int secondBit = second.at(i) - '0';
// boolean expression for sum of 3 bits
int sum = (firstBit ^ secondBit ^ carry)+'0';
result = (char)sum + result;
// Boolean expression for 3-bit addition
carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry);
}
// if overflow, then add a leading 1
if (carry)
{
result = '1' + result;
}
return result;
}
// this function converts decimal number to binary string
string Karatsuba::DecimalToBinary(long long int number)
{
string result = "";
if (number <= 0)
{
return "0";
}
else
{
int i = 0;
while (number > 0)
{
long long int num= number % 2;
stringstream ss;
ss<<num;
result = ss.str() + result;
number = number / 2;
i++;
}
return result;
}
}
// this function makes binary string subtraction with overflow
string Karatsuba::Subtraction(string lhs, string rhs)
{
int length = lengthController(lhs, rhs);
int diff;
string result;
for (int i = length-1; i >= 0; i--)
{
diff = (lhs[i]-'0') - (rhs[i]-'0');
if (diff >= 0)
{
result = DecimalToBinary(diff) + result;
}
else
{
for (int j = i-1; j>=0; j--)
{
lhs[j] = ((lhs[j]-'0') - 1) % 10 + '0';
if (lhs[j] != '1')
{
break;
}
}
result = DecimalToBinary(diff+2) + result;
}
}
return result;
}
// this function makes shifting
string Karatsuba::MakeShifting(string str, int stepnum)
{
string shifted = str;
for (int i = 0 ; i < stepnum ; i++)
shifted = shifted + '0';
return shifted;
}
// this function is the core of the Karatsuba
// divides problem into 4 subproblems
// recursively multiplies them
// returns the result string
string Karatsuba::multiply(string X, string Y)
{
int n = lengthController(X, Y);
if (n == 1) return ((Y[0]-'0' == 1) && (X[0]-'0' == 1)) ? "1" : "0";
int fh = n/2; // First half of string, floor(n/2)
int sh = (n-fh); // Second half of string, ceil(n/2)
// Find the first half and second half of first string.
string Xl = X.substr(0, fh);
string Xr = X.substr(fh, sh);
// Find the first half and second half of second string
string Yl = Y.substr(0, fh);
string Yr = Y.substr(fh, sh);
// Recursively calculate the three products of inputs of size n/2
string P1 = multiply(Xl, Yl);
string P2 = multiply(Xr, Yr);
string P3 = multiply(addStrings(Xl, Xr), addStrings(Yl, Yr));
// return added string version
return addStrings(addStrings(MakeShifting(P1, 2*(n-n/2)),P2),MakeShifting(Subtraction(P3,addStrings(P1,P2)), n-(n/2)));
}
int main(int argc, const char * argv[])
{
// get the binary numbers as strings
string firstNumber,secondNumber;
cout<<"Please give the First Binary number : ";
cin>>firstNumber;
cout<<endl<<"Please give the Second Binary number : ";
cin>>secondNumber;
cout << endl;
// make the initial lengths equal by adding zeros
int len1 = firstNumber.size();
int len2 = secondNumber.size();
int general_len = firstNumber.size();
if (len1 < len2)
{
for (int i = 0 ; i < len2 - len1 ; i++)
firstNumber = '0' + firstNumber;
general_len = firstNumber.size();
}
else if (len1 > len2)
{
for (int i = 0 ; i < len1 - len2 ; i++)
secondNumber = '0' + secondNumber;
general_len = secondNumber.size();
}
// In classical methodology Binary String Multiplication
cout<<"Classical Algorithm : "<<endl;
BinaryMultiplier newobj;
const clock_t classical_time = clock();
string classic = newobj.MakeMultiplication(firstNumber, secondNumber);
cout << float( clock () - classical_time ) / CLOCKS_PER_SEC<<endl<<endl;
float c_time = float( clock () - classical_time ) / CLOCKS_PER_SEC;
newobj.BinaryStringToDecimal(classic);
// Using Karatsuba Multiplication Algorithm Binary String Multiplication
cout<<endl<<"Karatsuba Algorithm : "<<endl;
Karatsuba obj;
const clock_t karatsuba_time = clock();
string karatsuba = obj.multiply(firstNumber, secondNumber);
cout << float( clock () - karatsuba_time ) / CLOCKS_PER_SEC<<endl<<endl;
float k_time = float( clock () - classical_time ) / CLOCKS_PER_SEC;
newobj.BinaryStringToDecimal(karatsuba);
return 0;
}
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان داده‌ها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
- متن کاوی (Text Mining) — به زبان ساده
منبع [+]
مجموعه: برنامه نویسی, ریاضیات کاربردی, مهندسی کامپیوتر
Loading...