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 implementation.

Functions
std::string	divide_and_conquer::karatsuba_algorithm::add_strings (std::string first, std::string second)
	Binary addition.
std::string	divide_and_conquer::karatsuba_algorithm::safe_substr (const std::string &str, int64_t x1, int64_t x2, int64_t n)
	Wrapper function for substr that considers leading zeros.
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.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

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

Ameer Carlo Lubang

Function Documentation

add_strings()

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

Binary addition.

Parameters

first,the	input string 1
second,the	input string 2

Returns

the sum binary string

                                                         {
    std::string result;  // to store the resulting sum bits
 
    // make the string lengths equal
    int64_t len1 = first.size();
    int64_t len2 = second.size();
    std::string zero = "0";
    if (len1 < len2) {
        for (int64_t i = 0; i < len2 - len1; i++) {
            zero += first;
            first = zero;
            zero = "0"; // Prevents CI from failing
        }
    } else if (len1 > len2) {
        for (int64_t i = 0; i < len1 - len2; i++) {
            zero += second;
            second = zero;
            zero = "0"; // Prevents CI from failing
        }
    }
 
    int64_t length = std::max(len1, len2);
    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 = (char(firstBit ^ secondBit ^ carry)) + '0';  // sum of 3 bits
        result.insert(result.begin(), sum);
 
        carry = char((firstBit & secondBit) | (secondBit & carry) |
                (firstBit & carry));  // sum of 3 bits
    }
 
    if (carry) {
        result.insert(result.begin(), '1');  // 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 product number value

                                                            {
    int64_t len1 = str1.size();
    int64_t len2 = str2.size();
    int64_t n = std::max(len1, len2);
 
    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 = divide_and_conquer::karatsuba_algorithm::safe_substr(str1, 0, fh, n);   // first half of first string
    std::string Xr = divide_and_conquer::karatsuba_algorithm::safe_substr(str1, fh, sh, n);  // second half of first string
 
    std::string Yl = divide_and_conquer::karatsuba_algorithm::safe_substr(str2, 0, fh, n);   // first half of second string
    std::string Yr = divide_and_conquer::karatsuba_algorithm::safe_substr(str2, fh, sh, n);  // 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::add_strings(Xl, Xr),
        divide_and_conquer::karatsuba_algorithm::add_strings(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:

safe_substr()

std::string divide_and_conquer::karatsuba_algorithm::safe_substr	(	const std::string &	str,
		int64_t	x1,
		int64_t	x2,
		int64_t	n )

Wrapper function for substr that considers leading zeros.

Parameters

str,the	binary input string.
x1,the	substr parameter integer 1
x2,the	substr parameter integer 2
n,is	the length of the "whole" string: leading zeros + str

Returns

the "safe" substring for the algorithm without leading zeros

"0" if substring spans to leading zeros only

                                                                               {
    int64_t len = str.size();
 
    if (len >= n) {
        return str.substr(x1, x2);
    }
 
    int64_t y1 = x1 - (n - len);  // index in str of first char of substring of "whole" string
    int64_t y2 = (x1 + x2 - 1) - (n - len);  // index in str of last char of substring of "whole" string
 
    if (y2 < 0) {
        return "0";
    } else if (y1 < 0) {
        return str.substr(0, y2 + 1);
    } else {
        return str.substr(y1, x2);
    }
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

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

Here is the call graph for this function: