Huge Multiplication
C++, Matlab. This was one of the assignments in the algorithm course I took before. Inputs are two big integers like 60 digits each. I implemented traditional multiplication method into my algorithm. Multiplication stage takes numbers in char format into a cell after each multiplication step. Then, it adds zeros to the end and front of numbers to make them inline before addition stage. Addition stage sums of digits in their vertical line one by one. Finally, it gives the result of product for two inputs as a char output since digit number of the product is too big.
Note: I checked if the inputs are valid or not in a very basic way. Character checking for char inputs could be added.
For example, two numbers (60 digits each):
‘415926535897932384626433832795028841971693993751058209749445’ and
‘182818284590452353602874713526624977572470936999595749669676’
The product (119 digits):
‘76038975808509199752257349866296465506516698245456284965108216281317973662575698005635922472140602306849234781474329820’
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
#include <iostream> #include <deque> #include <cstring> #include <cmath> void multiplication(const char number1[], const char number2[]); int main() { // Main inputs in the format constant char array const char input1[] = "415926535897932384626433832795028841971693993751058209749445"; const char input2[] = "182818284590452353602874713526624977572470936999595749669676"; // when zero is put to the front of any input if (input1[0] == '0' || input2[0] == '0') { std::cout << "Please do not put zero the front of any char input" << std::endl; return 0; } multiplication(input1, input2); return 0; } void multiplication(const char number1[], const char number2[]) { int digit1 = strlen(number1); //size of first number int digit2 = strlen(number2); //size of second number /*MULTIPLICATION STAGE*/ std::deque< std::deque<int> > numbers; //creating a dynamic matrix for numbers for(int i = 0; i < digit2; ++i) //creating empty rows for matrix { std::deque<int> row; numbers.push_back(row); } int row_index = 0; //creating a row index for(int i = digit2 - 1; i >= 0; --i) { int carry = 0; for(int j = digit1 - 1; j >= 0; --j) { int conversion1 = number1[j] - '0'; //converting char number to int int conversion2 = number2[i] - '0'; //converting char number to int int x = conversion1 * conversion2 + carry; int remainder = x % 10; numbers[row_index].push_front(remainder); carry = 0; carry = (int)floor(x / 10); } if(carry > 0) { numbers[row_index].push_front(carry); } row_index = row_index + 1; } //ADDING ZERO STAGE BEFORE FINAL ADDITION //First Step: adding zeros to the end of integers to make them inline for(int i = 1; i < digit2; ++i) { for(int j = 1; j <= i; ++j) { numbers[i].push_back(0); } } //Second Step: adding zeros to the front of integers to make them inline for(int i = 0;i < digit2-1; ++i) { int last_number = numbers[digit2-1].size(); //size of last number int first_number = numbers[i].size(); //size of first number if(last_number > first_number) { for(int j = 1; j <= last_number - first_number; ++j) { numbers[i].push_front(0); } } } //FINAL ADDITION STAGE int n = digit2; //row number int m = numbers[0].size(); //column number std::deque<int> product; //creating a dynamic array for product value digits int sum = 0; int sum_remainder = 0; int sum_carry = 0; for(int i = m-1; i >= 0; --i) { for(int j = 0; j < n; ++j) { sum = sum + numbers[j][i]; } sum = sum + sum_carry; sum_remainder = sum % 10; product.push_front(sum_remainder); sum_carry = 0; sum_carry = (int)floor(sum / 10); sum = 0; } //if the final addition carries a value, it will add it to the front if(sum_carry > 0) { product.push_front(sum_carry); } // final product value int size = product.size(); std::cout << "The answer: " << std::flush; for (int i = 0; i < size; ++i) { std::cout << product[i]; } std::cout << std::endl; } |
MATLAB version;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
function result = multiplication tic %char inputs char1 = '415926535897932384626433832795028841971693993751058209749445'; char2 = '182818284590452353602874713526624977572470936999595749669676'; if char1(1) == '0' || char2(1) == '0' result = 'Please do not put zero the front of any char input'; return end digit1 = length(char1); %size of first number digit2 = length(char2); %size of second number %MULTIPLICATION STAGE numbers = {}; %integers cell after all multiplication steps done for i = digit2:-1:1 integer = []; %integer (char)after each multiplication carry = 0; for j = digit1:-1:1 x = str2num(char1(j)) * str2num(char2(i)) + carry; remainder = mod(x,10); remainder = num2str(remainder); integer = [remainder, integer]; %adding remainder to the end of integer carry = 0; %clearing previous carry carry = floor(x/10); %finding carry end if carry > 0 integer = [num2str(carry), integer]; carry = 0; %clearing last carry for next multiplication end numbers = [numbers, integer]; %creating integer(char) list end %ADDING ZERO STAGE BEFORE FINAL ADDITION %First Step: adding zeros to tne end of integers to make them inline for i = 2:digit2 for j = 1:i-1 numbers(i) = strcat(numbers(i), '0'); end end %Second Step: adding zeros to the front of integers to make them inline for i = 1:digit2-1 last_integer = length(char(numbers(end))); first_integer = length(char(numbers(i))); if last_integer > first_integer for j = 1:last_integer - first_integer numbers(i) = strcat('0', numbers(i)); end end end %FINAL ADDITION STAGE table = char(numbers); %integer table in char format (converting from cell) [n,m] = size(table); %dimensions of the table product = []; %final product in char format sum = 0; %sum of digits in vertical line sum_carry = 0; %carry to next digit addition process for i = m:-1:1 for j = 1:n sum = sum + str2num(table(j,i)); end sum = sum + sum_carry; sum_remainder = mod(sum,10); sum_remainder = num2str(sum_remainder); product = [sum_remainder, product]; sum_carry = 0; %clearing previous carry of addition sum_carry = floor(sum/10); sum = 0; %clearing sum before next iteration end %if the final addition carries a value, it will add it to the front if sum_carry > 0 product = [num2str(sum_carry), product]; end result = product; %final product value toc end |