Addition of Large Numbers using strings in C++

The logic behind this is to store the large number as string and operate on each character as string is an array of characters each digit of the number is stored as a character. In order to work with characters there are two ways to do:

1.To write our own arithmetic operators to work with characters (overloading of operators)
2.Convert a character into an integer, work on integers and convert back to a character.  

How to convert a character into an integer?

Method 1:
If we have a character c='10'.We can follow  one of these steps:

int a                                

                                          a=(int)c                      //a has ascii value of 'c' i.e 58

             c=c-48                       //58-48=10

Ascii value of the digit can be obtained by adding 48 to the digit.


Method 2:

            int a                                                            

                    a=c-'0'               // i.e 58-48=10&a contains 10 

The character '0' means 48

Note: To convert from char to integer subtract ‘0’ and to convert from an integer to char add ‘0’

Here is the program to add two large numbers

	#include <iostream>
	#include <cstdlib>
	#include <string>
	using namespace std;
	int main()
	{
	string str1="1234567891011121314151617181920", str2="1234567891011121314151617181920" ;
	string rev_str1, rev_str2;
	string final; //Final product string
	int carry = 0;
	rev_str1 = string(str1.rbegin(), str1.rend());
	rev_str2 = string(str2.rbegin(), str2.rend());
	for (int i = 0; i <rev_str1.length() ; i++)
	{
	int x=rev_str1[i]-'0'; //converting into integer
	int y=rev_str2[i]-'0';
	int z=x+y+carry;
	final+=('0'+z%10); //converting into character
	carry=z/10;
	}
	if(carry>0) //final carry
	final+='0'+carry;
	final = string(final.rbegin(), final.rend());
	cout << "final = " << final << endl;
	}

This numerical example gives better understanding of the program.

  

str1="129" str2="234"

rev_str1="921".rev_str2="432"

carry=0

i=0 to 2

i=0

  

x='9'-'0'=57-48=9

y='4'-'0'=52-48=4

z=9+4+0 //carry=0 for 1st iteration

final +='0'+13%10='3'

carry=13/10=1

i=1

x='2'-'0'=50-48=2

y='3'-'0'=51-48=3

z=2+3+1 //carry=1 

final +='0'+5%10='6'  //final="3"

carry=5/10=0

i=2

x='1'-'0'=59-48=1

y='2'-'0'=50-48=2

z=1+2+0 //carry=0 

final +='0'+3%10='3'  //final="36"

carry=3/10=0

final="363"

Multiplication of two large numbers by storing intermediate values in C++

If we are asked to multiply two numbers of hundred digits each, how we are going to solve this problem?

One approach to solve this kind of problems is to store intermediate values and compute the final result using this. The intermediate values will not be as large as the number with hundred digits, therefore the computation becomes easy.
The idea of this approach is taken from the basic multiplication that we were taught during school days. This naive approach i.e. write one number above the other, then do long multiplication helps us to know the intermediate values which is used to compute the final result.

Let's go back to naive method where we used to do multiplication in this way

    9999

x      19

     -----

                                  89991                  // array1

                             + 99990                 //array2

 ---------

 189981

If we multiply the first two digits of this example i.e 9*9 the intermediate value is 81 where 8 is carry and 1 is stored in a temporary array. In the next step we multiply next digit of multiplicand i.e 9*9 Similarly we repeat this process and store each intermediate digit at each index in an array. Here we can use two arrays for storing the entire intermediate values. Adding both arrays will give the result.


Here is an example program for multiplying two large numbers.

	#include <string>
	#include <vector>
	#include <iostream>
	#include <stdio.h>
	using namespace std;
	void product(string a, string b) {
	vector<int> result(a.size() + b.size(), 0);
	for( int i = a.size() - 1; i >= 0; i-- ){
	for( int j = b.size() - 1; j >= 0; j-- ){
	result[ i + j + 1 ] += ( b[ j ] - '0') * ( a[ i ] - '0' ); //single array to store intermediate values
	}
	}
	for( int i = a.size() + b.size(); i >= 0; i-- ){
	if( result[ i ] >= 10 ){
	result[ i - 1 ] +=result[ i ] / 10;
	result[ i ] %= 10;
	}
	}
	cout << a << " * " << b << " = ";
	for( int i = 0; i < a.size() + b.size(); i++ ){
	cout << result[ i ];
	}
	cout << endl;
	}
	int main( void ){
	string str1, str2 ;
	str1 = "99999999999999999999";
	str2 = "9985995948565498566";
	product( str1, str2 );
	return 0;
	}

Dynamic Memory allocation in C and C++

Dynamic Memory allocation in C

   First let us look into how the memory is organized. The memory is mainly divided into stack, heap and permanent storage area. The Stack is used to store local variables. Global variables, program instructions and static variables are stored in the permanent storage area. Our main concern is heap which is free memory available, allocated dynamically using some standard library functions.

In C, the two key dynamic memory functions are malloc() and free().The prototype for malloc looks like  void *malloc(size_t size) and for free it looks like void free(void *pointer)

Here is an example to illustrate the use of these functions:

 The static way of defining an array

 int a[100];

 a[10] = 25;

The dynamic way of defining an array

         int *p;

         p = malloc(100 * sizeof(int));

         *(pointer+10) = 25;

When the array is no longer needed, it is deallocated using free function

       free(p); 

       p = NULL;

The assigning of NULL to pointer 'p' is optional, but it is done in order to avoid dangling pointer problem

For more understanding refer Dynamic memory allocation in c.

Dynamic Memory allocation in C++

  C++ provides to operators new and delete for dynamic memory allocation.

The following syntax shows the use of new operator in various ways

  variable = new typename;

                                           variable = new type(initializer);   //includes initialization

                                array = new type [size];    //array of objects

The memory is de-allocated using delete operator as shown:

delete variable;

delete[] array;

Here is an example to create a dynamic 1D array:

   int *p;

          pointer = new int[100];

       pointer[10] = 25;        

The pointer p is deallocated using delete:

      delete[] p;

      p = NULL;

C++ provides another option for dynamic memory allocation using the Standard Template Library.

Dynamic Memory allocation of 2D array in C++

  Allocating memory for 2D array is not straight forward like normal 1D array. A dynamic 2D array is an array of pointers to arrays. 

The steps used to create a dynamic 2D array are:

   1. int** a = new int*[row_size];  

      for(int i = 0; i < row_size; ++i)

2. a[i] = new int[column_size];

Figure 1.

First step creates 1D dynamic array(which is array of pointers) and in second step creates the column of the array. Figure 1 gives a clear idea.

Deallocating dynamic 2D array:

 for(int i = 0; i < row_size; ++i) {

    delete [] a[i];

}delete [] a;

Here is an example for creating and deleting dynamic 2D array with 4 rows and 5 columns (i.e a[4][5]):

int** a = new int*[4];

for(int i = 0; i < 4; ++i)

    ary[i] = new int[5];

for(int i = 0; i < 4; ++i) {

    delete [] a[i];

}delete [] a;