Dadas dos strings binarias que representan el valor de dos enteros, encuentre el producto de dos strings. Por ejemplo, si la primera string de bits es «1100» y la segunda string de bits es «1010», la salida debe ser 120.
Para simplificar, deje que la longitud de dos strings sea la misma y sea n.
Un enfoque ingenuo es seguir el proceso que estudiamos en la escuela. Uno por uno, tome todos los bits del segundo número y multiplíquelo con todos los bits del primer número. Finalmente suma todas las multiplicaciones. Este algoritmo toma O(n^2) tiempo.
Usando Divide and Conquer , podemos multiplicar dos números enteros en menos complejidad de tiempo. Dividimos los números dados en dos mitades. Sean los números dados X e Y.
Por simplicidad supongamos que n es par
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]
El producto XY se puede escribir de la siguiente manera.
XY = (Xl*2n/2 + Xr)(Yl*2n/2 + Yr) = 2n XlYl + 2n/2(XlYr + XrYl) + XrYr
Si echamos un vistazo a la fórmula anterior, hay cuatro multiplicaciones de tamaño n/2, por lo que básicamente dividimos el problema de tamaño n en cuatro subproblemas de tamaño n/2. Pero eso no ayuda porque la solución de recurrencia T(n) = 4T(n/2) + O(n) es O(n^2). La parte complicada de este algoritmo es cambiar los dos términos del medio a alguna otra forma para que solo una multiplicación adicional sea suficiente. La siguiente es una expresión engañosa para los dos términos centrales.
XlYr + XrYl = (Xl + Xr)(Yl + Yr) - XlYl- XrYr
Entonces el valor final de XY se convierte en
XY = 2n XlYl + 2n/2 * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr
Con el truco anterior, la recurrencia se convierte en T(n) = 3T(n/2) + O(n) y la solución de esta recurrencia es O(n 1.59 ).
¿Qué sucede si las longitudes de las strings de entrada son diferentes y no son pares? Para manejar el caso de diferente longitud, agregamos 0 al principio. Para manejar la longitud impar, colocamos los bits Floor(n/2) en la mitad izquierda y los bits Ceil(n/2) en la mitad derecha. Entonces la expresión para XY cambia a siguiente.
XY = 22ceil(n/2) XlYl + 2ceil(n/2) * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr
El algoritmo anterior se llama algoritmo de Karatsuba y puede usarse para cualquier base.
A continuación se muestra la implementación en C++ del algoritmo anterior.
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"));
}
120 60 30 10 0 49 9
Complejidad de tiempo: La complejidad de tiempo de la solución anterior es O(n log 2 3 ) = O(n 1.59 ).
La complejidad temporal de la multiplicación se puede mejorar aún más utilizando otro algoritmo Divide and Conquer, la transformada rápida de Fourier. Pronto discutiremos la transformada rápida de Fourier en una publicación separada.
Ejercicio:
El programa anterior devuelve un valor int largo y no funcionará para strings grandes. Extienda el programa anterior para devolver una string en lugar de un valor int largo.
Solución:
El proceso de multiplicación de números grandes es un problema importante en Ciencias de la Computación. El enfoque dado utiliza la metodología Divide and Conquer.
Ejecute el código para ver la comparación de la complejidad del tiempo para la multiplicación binaria normal y el algoritmo de Karatsuba.
Puedes ver el código completo en este repositorio
Ejemplos:
First Binary Input : 101001010101010010101001010100101010010101010010101 Second Binary Input : 101001010101010010101001010100101010010101010010101 Decimal Output : Not Representable Output : 2.1148846e+30
First 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
// 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;
}
Please give the First Binary number : Please give the Second Binary number : Classical Algorithm : 7e-06 Binary Result : Decimal Result (Not proper for Large Binary Numbers):0 Karatsuba Algorithm : 1e-06 Binary Result : 0 Decimal Result (Not proper for Large Binary Numbers):0
Artículo relacionado:
Multiplica números grandes representados como strings
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA