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
*/
[wpedon id=”461″ align=”center”]
No, it doesn’t.