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’

#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;
	
}

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;

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

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

%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

%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