Implementation of the Karatsuba algorithm for fast multiplication
More...
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
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
◆ add_strings()
Binary addition.
- Parameters
-
first,the | input string 1 |
second,the | input string 2 |
- Returns
- the sum binary string
37 {
39
40
41 int64_t len1 = first.
size();
42 int64_t len2 = second.
size();
44 if (len1 < len2) {
45 for (int64_t i = 0; i < len2 - len1; i++) {
46 zero += first;
47 first = zero;
48 zero = "0";
49 }
50 } else if (len1 > len2) {
51 for (int64_t i = 0; i < len1 - len2; i++) {
52 zero += second;
53 second = zero;
54 zero = "0";
55 }
56 }
57
58 int64_t length =
std::max(len1, len2);
59 int64_t carry = 0;
60 for (int64_t i = length - 1; i >= 0; i--) {
61 int64_t firstBit = first.
at(i) -
'0';
62 int64_t secondBit = second.
at(i) -
'0';
63
64 int64_t
sum = (char(firstBit ^ secondBit ^ carry)) +
'0';
66
67 carry = char((firstBit & secondBit) | (secondBit & carry) |
68 (firstBit & carry));
69 }
70
71 if (carry) {
73 }
75}
uint64_t result(uint64_t n)
Definition fibonacci_sum.cpp:76
T sum(const std::vector< std::valarray< T > > &A)
Definition vector_ops.hpp:232
◆ karatsuba_algorithm()
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
112 {
113 int64_t len1 = str1.
size();
114 int64_t len2 = str2.
size();
116
117 if (n == 0) {
118 return 0;
119 }
120 if (n == 1) {
121 return (str1[0] - '0') * (str2[0] - '0');
122 }
123
124 int64_t fh = n / 2;
125 int64_t sh = n - fh;
126
129
132
133
137 divide_and_conquer::karatsuba_algorithm::add_strings(Xl, Xr),
138 divide_and_conquer::karatsuba_algorithm::add_strings(Yl, Yr));
139
140 return product1 * (1 << (2 * sh)) +
141 (product3 - product1 - product2) * (1 << sh) +
142 product2;
143}
std::string safe_substr(const std::string &str, int64_t x1, int64_t x2, int64_t n)
Wrapper function for substr that considers leading zeros.
Definition karatsuba_algorithm_for_fast_multiplication.cpp:86
Functions for the Karatsuba algorithm for fast multiplication implementation.
◆ main()
Main function.
- Returns
- 0 on exit
181 {
183 return 0;
184}
static void test()
Self-test implementations.
Definition karatsuba_algorithm_for_fast_multiplication.cpp:151
◆ 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
86 {
87 int64_t len = str.
size();
88
89 if (len >= n) {
91 }
92
93 int64_t y1 = x1 - (n - len);
94 int64_t y2 = (x1 + x2 - 1) - (n - len);
95
96 if (y2 < 0) {
97 return "0";
98 } else if (y1 < 0) {
99 return str.
substr(0, y2 + 1);
100 } else {
101 return str.
substr(y1, x2);
102 }
103}
◆ test()
Self-test implementations.
- Returns
- void
151 {
152
156 assert(divide_and_conquer::karatsuba_algorithm::karatsuba_algorithm(
157 s11, s12) == 10);
159
160
164 assert(divide_and_conquer::karatsuba_algorithm::karatsuba_algorithm(
165 s21, s22) == 30);
167
168
172 assert(divide_and_conquer::karatsuba_algorithm::karatsuba_algorithm(
173 s31, s32) == 60);
175}