karatsuba_algorithm_for_fast_multiplication.cpp File Reference

Implementation of the Karatsuba algorithm for fast multiplication More...

#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

Include dependency graph for karatsuba_algorithm_for_fast_multiplication.cpp:

Namespaces
namespace	divide_and_conquer
	for std::vector
namespace	karatsuba_algorithm
	Functions for the Karatsuba algorithm for fast multiplication

Functions
std::string	divide_and_conquer::karatsuba_algorithm::addStrings (std::string first, std::string second)
	Helper function for the main function, that implements Karatsuba's algorithm for fast multiplication. More...
int64_t	divide_and_conquer::karatsuba_algorithm::karatsuba_algorithm (std::string str1, std::string str2)
	The main function implements Karatsuba's algorithm for fast multiplication. More...
static void	test ()
	Self-test implementations. More...
int	main ()
	Main function. More...

Detailed Description

Implementation of the Karatsuba algorithm for fast multiplication

Given two strings in binary notation we want to multiply them and return the value Simple approach is to multiply bits one by one which will give the time complexity of around O(n^2). To make it more efficient we will be using Karatsuba' algorithm to find the product which will solve the problem O(nlogn) of time.

Author

Swastika Gupta

Function Documentation

addStrings()

std::string divide_and_conquer::karatsuba_algorithm::addStrings	(	std::string	first,
		std::string	second
	)

Helper function for the main function, that implements Karatsuba's algorithm for fast multiplication.

Parameters

first	the input string 1
second	the input string 2

Returns

the concatenated string

                                                        {
    std::string result;  // To store the resulting sum bits
 
    int64_t len1 = first.size();
    int64_t len2 = second.size();
    int64_t length = std::max(len1, len2);
    std::string zero = "0";
    if (len1 < len2)  // make the string lengths equal
    {
        for (int64_t i = 0; i < len2 - len1; i++) {
            zero += first;
            first = zero;
        }
    } else if (len1 > len2) {
        zero = "0";
        for (int64_t i = 0; i < len1 - len2; i++) {
            zero += second;
            second = zero;
        }
    }
    int64_t carry = 0;
    for (int64_t i = length - 1; i >= 0; i--) {
        int64_t firstBit = first.at(i) - '0';
        int64_t secondBit = second.at(i) - '0';
 
        int64_t sum = (firstBit ^ secondBit ^ carry) + '0';  // sum of 3 bits
        std::string temp;
        temp = std::to_string(sum);
        temp += result;
        result = temp;
 
        carry = (firstBit & secondBit) | (secondBit & carry) |
                (firstBit & carry);  // sum of 3 bits
    }
 
    if (carry) {
        result = '1' + result;  // adding 1 incase of overflow
    }
    return result;
}

Here is the call graph for this function:

karatsuba_algorithm()

int64_t divide_and_conquer::karatsuba_algorithm::karatsuba_algorithm	(	std::string	str1,
		std::string	str2
	)

The main function implements Karatsuba's algorithm for fast multiplication.

Parameters

str1	the input string 1
str2	the input string 2

Returns

the multiplicative number value

                                                            {
    int64_t len1 = str1.size();
    int64_t len2 = str2.size();
    int64_t n = std::max(len1, len2);
    std::string zero = "0";
    if (len1 < len2) {
        for (int64_t i = 0; i < len2 - len1; i++) {
            zero += str1;
            str1 = zero;
        }
    } else if (len1 > len2) {
        zero = "0";
        for (int64_t i = 0; i < len1 - len2; i++) {
            zero += str2;
            str2 = zero;
        }
    }
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return (str1[0] - '0') * (str2[0] - '0');
    }
    int64_t fh = n / 2;     // first half of string
    int64_t sh = (n - fh);  // second half of string
 
    std::string Xl = str1.substr(0, fh);   // first half of first string
    std::string Xr = str1.substr(fh, sh);  // second half of first string
 
    std::string Yl = str2.substr(0, fh);   // first half of second string
    std::string Yr = str2.substr(fh, sh);  // second half of second string
 
    // Calculating the three products of inputs of size n/2 recursively
    int64_t product1 = karatsuba_algorithm(Xl, Yl);
    int64_t product2 = karatsuba_algorithm(Xr, Yr);
    int64_t product3 = karatsuba_algorithm(
        divide_and_conquer::karatsuba_algorithm::addStrings(Xl, Xr),
        divide_and_conquer::karatsuba_algorithm::addStrings(Yl, Yr));
 
    return product1 * (1 << (2 * sh)) +
           (product3 - product1 - product2) * (1 << sh) +
           product2;  // combining the three products to get the final result.
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    // 1st test
    std::string s11 = "1";
    std::string s12 = "1010";
    std::cout << "1st test... ";
    assert(divide_and_conquer::karatsuba_algorithm::karatsuba_algorithm(
               s11, s12) == 10);  // here the multiplication is 10
    std::cout << "passed" << std::endl;
 
    // 2nd test
    std::string s21 = "11";
    std::string s22 = "1010";
    std::cout << "2nd test... ";
    assert(divide_and_conquer::karatsuba_algorithm::karatsuba_algorithm(
               s21, s22) == 30);  // here the multiplication is 30
    std::cout << "passed" << std::endl;
 
    // 3rd test
    std::string s31 = "110";
    std::string s32 = "1010";
    std::cout << "3rd test... ";
    assert(divide_and_conquer::karatsuba_algorithm::karatsuba_algorithm(
               s31, s32) == 60);  // here the multiplication is 60
    std::cout << "passed" << std::endl;
}

Here is the call graph for this function: