Рубрики

Алгоритм Карацубы для быстрого умножения с использованием алгоритма «Разделяй и властвуй»

Если даны две двоичные строки, представляющие значение двух целых чисел, найдите произведение двух строк. Например, если первая битовая строка равна «1100», а вторая битовая строка — «1010», вывод должен быть равен 120.

Для простоты, пусть длина двух строк одинакова и равна n.

Наивный подход заключается в том, чтобы следовать процессу, который мы изучаем в школе. Один за другим берут все биты второго числа и умножают его на все биты первого числа. Наконец добавьте все умножения. Этот алгоритм занимает O (n ^ 2) времени.

Используя Divide и 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)
   = 2n 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 (n 1,59 ).

Что если длина входных строк различна и не является четной? Чтобы обработать регистр различной длины, мы добавляем нули в начале. Для обработки нечетной длины мы помещаем биты пола (n / 2) в левую половину и биты ceil (n / 2) в правую половину. Таким образом, выражение для XY меняется на следующее.

XY = 22ceil(n/2) XlYl + 2ceil(n/2) * [(Xl + Xr)(Yl + Yr) - XlYl - XrYr] + XrYr

Вышеуказанный алгоритм называется алгоритмом Карацубы, и его можно использовать для любой базы.

Следующее — реализация C ++ вышеупомянутого алгоритма.

// C ++ реализация алгоритма Карацубы для умножения битовых строк.
#include<iostream>
#include<stdio.h>

  

using namespace std;

  
// СО СЛЕДУЮЩИМИ ДВУМИ ФУНКЦИЯМИ http://goo.gl/q0OhZ
// Вспомогательный метод: учитывая две битовые строки неравного размера, преобразует их в
// той же длины, добавляя начальные 0 в меньшую строку. Возвращает
// новая длина

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; // Если len1> = len2

}

  
// Основная функция, которая добавляет две битовые последовательности и возвращает сложение
string addBitStrings( string first, string second )
{

    string result;  // Для хранения битов суммы

  

    // сделать одинаковые длины перед добавлением

    int length = makeEqualLength(first, second);

    int carry = 0;  // Инициализируем перенос

  

    // Добавить все биты один за другим

    for (int i = length-1 ; i >= 0 ; i--)

    {

        int firstBit = first.at(i) - '0';

        int secondBit = second.at(i) - '0';

  

        // логическое выражение для суммы 3 бит

        int sum = (firstBit ^ secondBit ^ carry)+'0';

  

        result = (char)sum + result;

  

        // логическое выражение для 3-битного сложения

        carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry);

    }

  

    // если переполнить, то добавить ведущий 1

    if (carry)  result = '1' + result;

  

    return result;

}

  
// Вспомогательная функция для умножения отдельных битов строк a и b

int multiplyiSingleBit(string a, string b)

return (a[0] - '0')*(b[0] - '0');  }

  
// Основная функция, которая умножает две битовые строки X и Y и возвращает
// результат как длинное целое

long int multiply(string X, string Y)

{

    // Находим максимальную длину x и Y и делаем длину

    // меньшая строка такая же как и большая строка

    int n = makeEqualLength(X, Y);

  

    // Базовые случаи

    if (n == 0) return 0;

    if (n == 1) return multiplyiSingleBit(X, Y);

  

    int fh = n/2;   // Первая половина строки, пол (n / 2)

    int sh = (n-fh); // Вторая половина строки, ceil (n / 2)

  

    // Находим первую половину и вторую половину первой строки.

    // См. Http://goo.gl/lLmgn для метода substr

    string Xl = X.substr(0, fh);

    string Xr = X.substr(fh, sh);

  

    // Находим первую половину и вторую половину второй строки

    string Yl = Y.substr(0, fh);

    string Yr = Y.substr(fh, sh);

  

    // Рекурсивно вычисляем три произведения входов размера n / 2

    long int P1 = multiply(Xl, Yl);

    long int P2 = multiply(Xr, Yr);

    long int P3 = multiply(addBitStrings(Xl, Xr), addBitStrings(Yl, Yr));

  

    // Объединяем три продукта, чтобы получить окончательный результат.

    return P1*(1<<(2*sh)) + (P3 - P1 - P2)*(1<<sh) + P2;

}

  
// Программа драйвера для проверки вышеуказанных функций

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

Сложность времени: временная сложность вышеупомянутого решения O (n log 2 3 ) = O (n 1,59 ).

Временная сложность умножения может быть дополнительно улучшена с помощью другого алгоритма «Разделяй и властвуй», быстрого преобразования Фурье. Скоро мы обсудим быстрое преобразование Фурье отдельным постом.

Упражнение
Вышеприведенная программа возвращает длинное значение типа int и не будет работать для больших строк. Расширьте вышеприведенную программу, чтобы она возвращала строку вместо длинного значения типа 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

#include <iostream>
#include <ctime>
#include <fstream>
#include <string.h>
#include <cmath>
#include <sstream>

  

using namespace std;

  
// Классический метод класса

class BinaryMultiplier

{

public:

    string MakeMultiplication(string,string);      

    string MakeShifting(string,int);               

    string addBinary(string,string);

    void BinaryStringToDecimal(string);

};

  
// метод класса каратсуба

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);

};

  
// эта функция получает строки и перебирает бит str2
// если он видит 1, он вычисляет сдвинутую версию в соответствии с битом позиции
// Делает операцию добавления для двоичных строк
// возвращает строку результата
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;

}

  

  
// эта функция добавляет двоичные строки с переносом
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;

}

  
// эта функция сдвигает заданную строку в соответствии с заданным числом
// возвращает сдвинутую версию

string BinaryMultiplier::MakeShifting(string str, int stepnum)

{

    string shifted = str;

    for (int i = 0 ; i < stepnum ; i++)

        shifted = shifted + '0';

    return shifted;

}

  
// эта функция преобразует двоичное число в десятичное число
// После 32 битов он дает 0, потому что он переполняет размер 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;

}

  
// эта функция контролирует длины строк и делает их равными
// возвращает максимальную длину

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;

}

  
// эта функция добавляет строки с переносом
// используется методология сложения битов
// возвращает строку результата
string Karatsuba::addStrings(string first, string second)
{

    string result;  // Для хранения битов суммы

      

    // сделать одинаковые длины перед добавлением

    int length = lengthController(first, second);

    int carry = 0;  // Инициализируем перенос

      

    // Добавить все биты один за другим

    for (int i = length-1 ; i >= 0 ; i--)

    {

        int firstBit = first.at(i) - '0';

        int secondBit = second.at(i) - '0';

          

        // логическое выражение для суммы 3 бит

        int sum = (firstBit ^ secondBit ^ carry)+'0';

          

        result = (char)sum + result;

          

        // логическое выражение для 3-битного сложения

        carry = (firstBit&secondBit) | (secondBit&carry) | (firstBit&carry);

    }

      

    // если переполнить, то добавить ведущий 1

    if (carry)

    {

        result = '1' + result;

    }

      

    return result;

}

  
// эта функция преобразует десятичное число в двоичную строку

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;

          

    }

}

  
// эта функция выполняет вычитание двоичной строки с переполнением
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;

}

  
// эта функция делает сдвиг

string Karatsuba::MakeShifting(string str, int stepnum)

{

    string shifted = str;

    for (int i = 0 ; i < stepnum ; i++)

        shifted = shifted + '0';

    return shifted;

}

  
// эта функция является ядром Карацубы
// делит проблему на 4 подзадачи
// рекурсивно умножаем их
// возвращает строку результата
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;   // Первая половина строки, пол (n / 2)

    int sh = (n-fh); // Вторая половина строки, ceil (n / 2)

      

    // Находим первую половину и вторую половину первой строки.

    string Xl = X.substr(0, fh);

    string Xr = X.substr(fh, sh);

      

    // Находим первую половину и вторую половину второй строки

    string Yl = Y.substr(0, fh);

    string Yr = Y.substr(fh, sh);

      

    // Рекурсивно вычисляем три произведения входов размера n / 2

    string P1 = multiply(Xl, Yl);

    string P2 = multiply(Xr, Yr);

    string P3 = multiply(addStrings(Xl, Xr), addStrings(Yl, Yr));

      

    // возвращаем добавленную строковую версию

    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[])

{

    // получаем двоичные числа в виде строк

    string firstNumber,secondNumber;

    

    cout<<"Please give the First Binary number : ";

    cin>>firstNumber;

    cout<<endl<<"Please give the Second Binary number : ";

    cin>>secondNumber;

    cout << endl;

      

  

    // сделать начальные длины равными, добавив нули

    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();

    }

      

    // В классической методологии умножения двоичных строк

    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);

      

    // Использование алгоритма умножения Карацубы Умножение двоичных строк

    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;

}

Связанная статья:
Умножение больших чисел, представленных в виде строк

Ссылки:
Страница Википедии для алгоритма Карацубы
Алгоритмы, 1-е издание, Санжой Дасгупта, Христос Пападимитриу и Умеш Вазирани
http://courses.csail.mit.edu/6.006/spring11/exams/notes3-karatsuba
http://www.cc.gatech.edu/~ninamf/Algos11/lectures/lect0131.pdf

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Алгоритм Карацубы для быстрого умножения с использованием алгоритма «Разделяй и властвуй»

0.00 (0%) 0 votes