# Karatsuba Multiplication in C++

###### Code for ADSA Assignment1

Don’t copy it, or I can ensure you that you’ll get caught.

Change some variable names ,swap order of some codes won’t help.

I wrote two version just hope these will inspire your own coding.

This program is designed for digits longer than what  uint128_t can handle. (In this case, 100 digits, but can be extended easily).

### Requirement:

Your submission should contain exactly one file: main.cpp. You do not need to submit a design.

Your program takes one line as input. The input line contains three integers separated by spaces. Let the three integers be I1, I2, and B. I1 and I2 are both nonnegative integers up to 100 digits long (there are no leading 0s, except when the value itself is 0). B is I1 and I2’s base (B is from 2 to 10).

Your program should output the sum of I1 and I2, using the school method, then the product of I1 and I2, using the Karatsuba algorithm.

The results should still use base B. Please separate the results using one space.

Sample input 1: 101 5 10
Sample output 1: 106 505
Sample input 2: 10 111 2
Sample output 2: 1001 1110
Sample input 3: 111 10 2
Sample output 2: 1001 1110

updated on March 2020
requested by a junior student
Static Array version (with adjustable input size)

```#include
#include

//Static Array size
#define MAX_LENGTH 100
#define ARR_MAX_SIZE MAX_LENGTH*MAX_LENGTH
#define ARR_IDX(arr,n) (&arr[n*ARR_MAX_SIZE])

void school_add(int* arr1, int* arr2, int* result, int base);
void school_sub(int* arr1, int* arr2, int* result, int base);
void leftshift(int* arr);
void copy_arr(int* arr1, int* arr2);
void school_mul(int* arr1, int* arr2, int* result, int base);
void stringtoarray(std::string str, int* arr);
void print_arr(int* arr);
long long int slice(int* arr1, int* arr2, int* high_1, int* low_1, int* high_2, int* low_2);
void Karatsuba_Multiplication(int* arr1, int* arr2, int* result, int base);

int main()
{
std::string I1, I2, base_str;
std::cin >> I1 >> I2 >> base_str;
auto base = std::stoi(base_str);

int arr[ARR_MAX_SIZE << 1] = { 0 };
auto arr1 = ARR_IDX(arr, 0);
auto arr2 = ARR_IDX(arr, 1);

stringtoarray(I1, arr1);
stringtoarray(I2, arr2);

int result[ARR_MAX_SIZE << 1] = { 0 };
auto result_add = ARR_IDX(result, 0);
auto result_mul = ARR_IDX(result, 0);

school_add(arr1, arr2, result_add, base);
print_arr(result_add);
std::cout << " ";
Karatsuba_Multiplication(arr1, arr2, result_mul, base);
print_arr(result_mul);
std::cout << " ";
return 0;
}

void school_add(int* arr1, int* arr2, int* result, int base)
{
int carry = 0, bit = 0;
for (auto i = ARR_MAX_SIZE - 1; i > -1; i--)
{
*(result + i) = (*(arr1 + i) + *(arr2 + i) + carry >= base) ? *(arr1 + i) + *(arr2 + i) + carry - base : *(arr1 + i) + *(arr2 + i) + carry;
carry = !!(*(arr1 + i) + *(arr2 + i) + carry >= base);
}
}

void school_sub(int* arr1, int* arr2, int* result, int base)
{
int carry = 0, bit = 0;
for (auto i = ARR_MAX_SIZE - 1; i > -1; i--)
{
*(result + i) = (*(arr1 + i) - *(arr2 + i) - carry < 0) ? *(arr1 + i) - *(arr2 + i) - carry + base : *(arr1 + i) - *(arr2 + i) - carry;
carry = !!(*(arr1 + i) - *(arr2 + i) - carry < 0);
}
}

void leftshift(int* arr)
{
for (auto i = 0; i < ARR_MAX_SIZE - 1; i++)
*(arr + i) = *(arr + i + 1);
*(arr + ARR_MAX_SIZE - 1) = 0;
}

void copy_arr(int* arr1, int* arr2)
{
for (auto i = 0; i < ARR_MAX_SIZE; i++)
*(arr1 + i) = *(arr2 + i);
}

void school_mul(int* arr1, int* arr2, int* result, int base)
{
int last_result[ARR_MAX_SIZE] = { 0 };
int this_result[ARR_MAX_SIZE] = { 0 };
int sum_result[ARR_MAX_SIZE] = { 0 };
int carry = 0;
for (auto j = ARR_MAX_SIZE - 1; j > ARR_MAX_SIZE - MAX_LENGTH - 1; j--)
{
memset(this_result, 0, sizeof(this_result));
memset(sum_result, 0, sizeof(sum_result));
for (auto i = ARR_MAX_SIZE - 1; i > ARR_MAX_SIZE - MAX_LENGTH - 1; i--)
if (carry != 0 || *(arr1 + i) != 0 || *(arr2 + j) != 0)
{
*(this_result + i) = (*(arr1 + i) * *(arr2 + j) + carry >= base) ? (*(arr1 + i) * *(arr2 + j) + carry) % base : *(arr1 + i) * *(arr2 + j) + carry;
carry = (*(arr1 + i) * *(arr2 + j) + carry >= base) ? ((*(arr1 + i) * *(arr2 + j) + carry - ((*(arr1 + i) * *(arr2 + j) + carry) % base)) / base) : 0;
}
for(auto k=0;k ARR_MAX_SIZE - MAX_LENGTH - 1; i--)
*(high_1 + iter--) = *(arr1 + i);
//low_1
iter = ARR_MAX_SIZE - 1;
for (auto i = ARR_MAX_SIZE - 1; i > ARR_MAX_SIZE - 1-bit; i--)
*(low_1 + iter--) = *(arr1 + i);
//high_2
iter = ARR_MAX_SIZE - 1;
for (auto i = ARR_MAX_SIZE - 1 - bit; i > ARR_MAX_SIZE - MAX_LENGTH - 1; i--)
*(high_2 + iter--) = *(arr2 + i);
//low_2
iter = ARR_MAX_SIZE - 1;
for (auto i = ARR_MAX_SIZE - 1; i > ARR_MAX_SIZE - 1 - bit; i--)
*(low_2 + iter--) = *(arr2 + i);
return bit;
}

void Karatsuba_Multiplication(int* arr1, int* arr2, int* result, int base)
{
int high_1[ARR_MAX_SIZE] = { 0 };
int low_1[ARR_MAX_SIZE] = { 0 };
int high_2[ARR_MAX_SIZE] = { 0 };
int low_2[ARR_MAX_SIZE] = { 0 };
long long int m = slice(arr1, arr2, high_1, low_1, high_2, low_2);
if (m <= 10)
school_mul(arr1, arr2, result, base);

int z2[ARR_MAX_SIZE] = { 0 };
int z1[ARR_MAX_SIZE] = { 0 };
int z0[ARR_MAX_SIZE] = { 0 };
int temp_1[ARR_MAX_SIZE] = { 0 };
int temp_2[ARR_MAX_SIZE] = { 0 };
int temp_3[ARR_MAX_SIZE] = { 0 };
int temp_4[ARR_MAX_SIZE] = { 0 };
int temp_5[ARR_MAX_SIZE] = { 0 };
int final[ARR_MAX_SIZE] = { 0 };
//z2 = high_1 * high_2
school_mul(high_1, high_2, z2, base);

//z0 = low_1 * low_2
school_mul(low_1, low_2, z0, base);

//z1 = (high_1 + low_1) * (high_2 + low_2) - z2 - z0
school_add(high_1, low_1, temp_1, base);
school_add(high_2, low_2, temp_2, base);
school_mul(temp_1, temp_2, temp_3, base);
school_sub(temp_3, z2, temp_4,base);
school_sub(temp_4, z0, z1, base);

//（xy = z2 * base^(2m) + z1 * base^(m) + z0）
for (long long int i = 0; i < 2 * m; i++)
leftshift(z2);
for (long long int i = 0; i < m; i++)
leftshift(z1);
school_add(z2, z1, temp_5, base);
school_add(temp_5, z0, final, base);
copy_arr(result, final);
}

void stringtoarray(std::string str, int* arr)
{
long long int iter = 0;
for (long long int i = str.size() - 1; i > -1; i--)
*(arr + ARR_MAX_SIZE - 1 - iter++) = int(str[i]) - 48;
}

void print_arr(int* arr)
{
bool digit_start = false;
for (auto i = 0; i < ARR_MAX_SIZE; i++)
{
if (*(arr + i))
digit_start = true;
if (digit_start)
std::cout << *(arr + i);
}
}```

Original vector version in 2017 (code works but not elegant)

```#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include <algorithm>
#include <math.h>

using namespace std;

void printvector(vector<int> vec)
{
for (int i = 0;i < vec.size();i++)
{
cout << vec[i];
}
//cout << endl;
}

vector<int> school_type_addition(vector<int> vec1, vector<int> vec2, int *base)
{
vector<int> carry,result;
reverse(vec1.begin(), vec1.end());
reverse(vec2.begin(), vec2.end());
carry.push_back(0);
for (int i = 0;i < max(vec1.size(), vec2.size());i++)
{
//In the bounders of vector
if (i < min(vec1.size(), vec2.size()))
{

if (vec1[i] + vec2[i] + carry[i] >= *base)
{
result.push_back(vec1[i] + vec2[i] - *base + carry[i]);
carry.push_back(1);
}
else
{
result.push_back(vec1[i] + vec2[i] + carry[i]);
carry.push_back(0);
}

}
if (i >= min(vec1.size(), vec2.size()))
{
if (vec1.size() < vec2.size())
{
if (vec2[i] + carry[i] >= *base)
{
result.push_back(vec2[i] - *base + carry[i]);
carry.push_back(1);
}
else
{
result.push_back(vec2[i] + carry[i]);
carry.push_back(0);
}
}
else
{
if (vec1[i] + carry[i] >= *base)
{
result.push_back(vec1[i] - *base + carry[i]);
carry.push_back(1);
}
else
{
result.push_back(vec1[i] + carry[i]);
carry.push_back(0);
}
}
}
}
if (carry.back() != 0)
result.push_back(carry.back());
reverse(result.begin(), result.end());
return result;
}

vector<int> school_type_subtraction(vector<int> vec1, vector<int> vec2, int *base)
{
vector<int> carry, result;
reverse(vec1.begin(), vec1.end());
reverse(vec2.begin(), vec2.end());
carry.push_back(0);
for (int i = 0;i < max(vec1.size(), vec2.size());i++)
{
//In the bounders of vector
if (i < min(vec1.size(), vec2.size()))
{

if (vec1[i] - vec2[i] - carry[i] < 0)
{
result.push_back(vec1[i] - vec2[i] + *base - carry[i]);
carry.push_back(1);
}
else
{
result.push_back(vec1[i] - vec2[i] - carry[i]);
carry.push_back(0);
}

}
if (i >= min(vec1.size(), vec2.size()))
{

if (vec1[i] - carry[i] < 0)
{
result.push_back(vec1[i] + *base - carry[i]);
carry.push_back(1);
}
else
{
result.push_back(vec1[i] - carry[i]);
carry.push_back(0);
}
}
}
reverse(result.begin(), result.end());
return result;
}

vector<int> school_type_Multiplication(vector<int> vec1, vector<int> vec2, int *base)
{
vector<int> carry, result,temp;
reverse(vec1.begin(), vec1.end());
reverse(vec2.begin(), vec2.end());

if (vec2.size() > vec1.size())
{
vec1.swap(vec2);
}
for (int i = 0; i < vec2.size();i++)
{
carry.clear();
carry.push_back(0);
for (int j = 0; j < vec1.size();j++)
{
if (vec1[j] * vec2[i] + carry[j] >= *base)
{
temp.push_back((vec1[j] * vec2[i] + carry[j]) % *base);
carry.push_back((vec1[j] * vec2[i] + carry[j] - ((vec1[j] * vec2[i] + carry[j]) % *base)) / *base);
}
else
{
temp.push_back(vec1[j] * vec2[i] + carry[j]);
carry.push_back(0);
}
}
if (carry.back() != 0)
temp.push_back(carry.back());
for (int k = 0; k < i;k++)
{
temp.insert(temp.begin(), 0);
}
reverse(temp.begin(), temp.end());
result = school_type_addition(temp, result, base);
temp.clear();
}
return result;
}

int vector_to_int(vector<int> vec, int *base)
{
// square root of 2147483647 (size of int)
if (vec.size() > 46340)
return -1;
int intvalue = 0;
for (int i = 0;i < vec.size();i++)
{
intvalue = intvalue + int(pow(*base, (vec.size() - 1 - i)))*vec[i];
}
}

vector<int> int_to_vector(int value, int *base)
{
vector<int> vec;
for (; value > 0; value /= *base)
vec.push_back(value % *base);
reverse(vec.begin(), vec.end());
return vec;
}

vector<int> Karatsuba_Multiplication(vector<int> vec1, vector<int> vec2,int *base)
{
vector<int> a1,a0,b1,b0,c0,c1,c2,d;
int n = max(vec1.size(),vec2.size());

if (n = 1)
{
return school_type_Multiplication(vec1, vec2, base);
}

//Separation point
if (n % 2 == 1)
{
n = (n + 1) / 2;
}
else
n = n / 2;

//Vec1 Separation
if (vec1.size() <= n)
{
a1.push_back(0);
a0 = vec1;
}
else
{
for (int i = 0;i < vec1.size() - n;i++)
{
a1.push_back(vec1[i]);
reverse(a1.begin(), a1.end());
}
for (int i = vec1.size();i < n;i++)
{
a0.push_back(vec1[i]);
reverse(a0.begin(), a0.end());
}
}
//Vec2 Separation
if (vec2.size() <= n)
{
b1.push_back(0);
b0 = vec2;
}
else
{
for (int i = 0;i < vec2.size() - n;i++)
{
b1.push_back(vec2[i]);
reverse(b1.begin(), b1.end());
}
for (int i = vec2.size();i < n;i++)
{
b0.push_back(vec2[i]);
reverse(b0.begin(), b0.end());
}
}

c0 = school_type_Multiplication(a0, b0, base);
c1 = school_type_Multiplication(a1, b1, base);
c2 = school_type_Multiplication(school_type_subtraction(a0, a1, base), school_type_subtraction(b0, b1, base), base);

//(c1*base^2n)+((c1-c2-c0)*base^(n))+(c0)
return school_type_addition(school_type_Multiplication(school_type_subtraction(school_type_addition(school_type_addition(school_type_Multiplication(c1, int_to_vector(int(pow(*base, 2 * n)), base), base), c0, base), c1, base), c2, base), int_to_vector(int(pow(*base, n)), base), base), c0, base);

}

int main()
{
int base, numbers = 0;
vector<int> digit_1, digit_2;
string input, temp;

getline(cin, temp);
stringstream ss(temp);
while (ss >> input)
{
//I1 into vector
if (numbers == 0)
{

if (input.size() > 100)
{
//digits over 100
cout << "Error. Over 100 digits." << endl;
exit(1);
}

for (int i = 0; i < input.size(); i++)
{
digit_1.push_back(input[i] - 48);
}
}

//I2 into vector
if (numbers == 1)
{

if (input.size() > 100)
{
//digits over 100
cout << "Error. Over 100 digits." << endl;
exit(1);
}

for (int i = 0; i < input.size(); i++)
{
digit_2.push_back(input[i] - '0');
}
}

//Base
if (numbers == 2)
{
istringstream buffer(input);
buffer >> base;

//Error check

if (base > 10 || base < 2)
{
cout << "Error. Base should be between 2 and 10." << endl;
exit(1);
}

}

//loop progrress
numbers++;
}

if (numbers != 3)
{
cout << "Error. You should input 3 digits." << endl;
exit(1);
}
printvector(school_type_addition(digit_1, digit_2, &base));
cout << " ";
printvector(Karatsuba_Multiplication(digit_1, digit_2, &base));
cout << " ";
cout << "0";
//DEBUG
/*
cout << endl;
cout << "Karatsuba_Multiplication:" << endl;
printvector(Karatsuba_Multiplication(digit_1, digit_2, &base));
cout << "------------CROSS CHECK------------" << endl;
cout << "School_Type_Multiplication:" << endl;
printvector(school_type_Multiplication(digit_1, digit_2, &base));
*/
return 0;
}

/*
References:
http://www.cplusplus.com/reference/string/stoi/
https://stackoverflow.com/questions/439573/how-to-convert-a-single-char-into-an-int
https://en.wikipedia.org/wiki/Karatsuba_algorithm
http://www.cplusplus.com/reference/vector/vector/swap/
http://media.henanliren.com/upload/pdf/20150227/20153427093441_648.pdf
*/```

## 4 thoughts on “Karatsuba Multiplication in C++”

1. Dheeraj says:

this program is not working for division.

2. Mooning69420 says:

The original 2017 code has an error on line 189
if (n = 1) should be either if (n == 1) or if (n <=1)
if this is fixed then the code does not work, it will segfault
I've attempted to remedy this but my code does not output the correct answer

3. Mooning69420 says:

I solved the 2017 one, I can confirmed this now works, here is the code
#include
#include
#include
#include
#include
#include

void printvector(std::vector vec){
for (int i = 0;i < vec.size();i++){
std::cout << vec[i];
}
}
std::vector school_addition(std::vector number_1, std::vector number_2, int base){
int sum = 0;
int carry = 0;
std::vector answer_addition;
reverse(number_1.begin(), number_1.end());
reverse(number_2.begin(), number_2.end());
if(number_1.size()<number_2.size()){
for(int i = 0;i =base){
answer_addition.push_back(sum-base);
carry = 1;
}
else{
answer_addition.push_back(sum);
carry = 0;
}
}
for(int i = number_1.size();i=base){
answer_addition.push_back(sum-base);
carry = 1;
}
else{
answer_addition.push_back(sum);
carry = 0;
}
}
if(carry==1){
answer_addition.push_back(carry);
}
}
else if(number_1.size()>number_2.size()){
for(int i = 0;i =base){
answer_addition.push_back(sum-base);
carry = 1;
}
else{
answer_addition.push_back(sum);
carry = 0;
}
}
for(int i = number_2.size();i=base){
answer_addition.push_back(sum-base);
carry = 1;
}
else{
answer_addition.push_back(sum);
carry = 0;
}
}
if(carry==1){
answer_addition.push_back(carry);
}
}
else if(number_1.size()==number_2.size()){
for(int i = 0;i =base){
answer_addition.push_back(sum-base);
carry = 1;
}
else{
answer_addition.push_back(sum);
carry = 0;
}
}
if(carry==1){
answer_addition.push_back(carry);
}
}
while((answer_addition.size()>1)&&(answer_addition.back()==0)){
answer_addition.pop_back();
}
reverse(answer_addition.begin(), answer_addition.end());
return answer_addition;
}
std::vector school_subtraction(std::vector number_1, std::vector number_2, int base){
int sum = 0;
int carry = 0;
std::vector answer_subtraction;
reverse(number_1.begin(), number_1.end());
reverse(number_2.begin(), number_2.end());
if(number_1.size()<number_2.size()){
for(int i = 0;i < number_1.size();i++){
sum = number_2[i]-number_1[i]-carry;
if(sum<0){
answer_subtraction.push_back(sum+base);
carry = 1;
}
else{
answer_subtraction.push_back(sum);
carry = 0;
}
}
for(int i = number_1.size();i<number_2.size();i++){
sum=number_2[i]-carry;
if(sumnumber_2.size()){
for(int i = 0;i<number_2.size();i++){
sum = number_1[i]-number_2[i]-carry;
if(sum<0){
answer_subtraction.push_back(sum+base);
carry = 1;
}
else{
answer_subtraction.push_back(sum);
carry = 0;
}
}
for(int i = number_2.size();i<number_1.size();i++){
sum=number_1[i]-carry;
if(sum<0){
answer_subtraction.push_back(sum+base);
carry = 1;
}
else{
answer_subtraction.push_back(sum);
carry = 0;
}
}
}
else if(number_1.size()==number_2.size()){
for(int i = 0;i < number_2.size();i++){
sum = number_1[i]-number_2[i]-carry;
if(sum1)&&(answer_subtraction.back()==0)){
answer_subtraction.pop_back();
}
reverse(answer_subtraction.begin(), answer_subtraction.end());
if(number_1.size()<number_2.size()){
answer_subtraction.front() = (-1)*(answer_subtraction.front());
return answer_subtraction;
}
else{
return answer_subtraction;
}
}
std::vector school_multiplication(std::vector number_1, std::vector number_2, int base){
std::vector result;
std::vector sum;
int carry = 0;
reverse(number_1.begin(), number_1.end());
reverse(number_2.begin(), number_2.end());
if (number_2.size() > number_1.size()){
number_1.swap(number_2);
}
for(int i=0;i<number_2.size();i++){
carry = 0;
for (int j=0;j=base){
sum.push_back((number_1[j]*number_2[i]+carry)%base);
carry = (number_1[j]*number_2[i]+carry-((number_1[j]*number_2[i]+carry)%base))/base;
}
else{
sum.push_back(number_1[j]*number_2[i]+carry);
carry = 0;
}
}
if (carry != 0){
sum.push_back(carry);
}
for (int k = 0; k 1)&&(result.back()==0)){
result.pop_back();
}
reverse(result.begin(), result.end());
return result;
}
std::vector Karatsuba_multiplication(std::vector number_1,std::vector number_2,int base){
std::vector low_1;
std::vector low_2;
std::vector high_1;
std::vector high_2;
std::vector z0;
std::vector z1;
std::vector z2;
std::vector first;
std::vector second;
std::vector third;
std::vector subtraction_1;
std::vector subtraction_2;
std::vector power_1;
std::vector power_2;
std::vector base_1;
base_1.push_back(base);
power_1.push_back(base);
power_2.push_back(base);
int n = std::max(number_1.size(),number_2.size());
if(n<4){
return school_multiplication(number_1,number_2,base);
}
if(number_1.size()<number_2.size()){
reverse(number_1.begin(),number_1.end());
while(number_1.size()number_2.size()){
reverse(number_2.begin(),number_2.end());
while(number_1.size()>number_2.size()){
number_2.push_back(0);
}
reverse(number_2.begin(),number_2.end());
}
if(n%2==1){
n=(n+1)/2;
}
else{
n=n/2;
}
for(int i=0;i<number_1.size()-n;i++){
high_1.push_back(number_1[i]);
}
for(int j=number_1.size()-n;j<number_1.size();j++){
low_1.push_back(number_1[j]);
}
for(int k=0;k<number_2.size()-n;k++){
high_2.push_back(number_2[k]);
}
for(int l=number_2.size()-n;l<number_2.size();l++){
low_2.push_back(number_2[l]);
}
z0 = Karatsuba_multiplication(low_1,low_2,base);
z1 = Karatsuba_multiplication(school_addition(high_1,low_1,base), school_addition(high_2,low_2,base),base);
z2 = Karatsuba_multiplication(high_1,high_2,base);
for(int i=0;i<2*n-1;i++){
power_1 = school_multiplication(power_1,base_1,base);
}
for(int i=0;i<n-1;i++){
power_2 = school_multiplication(power_2,base_1,base);
}
first = school_multiplication(z2,power_1,base);
subtraction_1 = school_subtraction(z1,z2,base);
subtraction_2 = school_subtraction(subtraction_1,z0,base);
second = school_multiplication(subtraction_2,power_2,base);
third = school_addition(second,z0,base);
return school_addition(first,third,base);
}
int main(){
int base = 0;
int numbers = 0;
std::vector number_1;
std::vector number_2;
std::string input, word;
getline(std::cin, word);
std::stringstream split(word);
while(split >> input){
if(numbers == 0){
for(int i = 0; i < input.size(); i++){
number_1.push_back(input[i] – '0');
}
}
else if(numbers == 1){
for (int i = 0; i > base;
}
numbers++;
}
printvector(school_addition(number_1, number_2, base));
std::cout << " ";
printvector(Karatsuba_multiplication(number_1, number_2, base));
std::cout << std::endl;
return 0;
}