Question

Provide an algorithm to add and multiply two large integers which cannot be represented by built-in types, C code would be a great help?

Answer 1

First you need to represent the integers into linklist or array lets assume you represent it in the array say A size M and B size N.

int C[100]; //  Multiplication is in C-array

void multiply(int A[], int M, int B[], int N)
{
    int s = M + N - 1;

    for(int j = N - 1; j >= 0; j--)
    {
        int carry = 0;
        int move = s;
        for(int i = M-1; i >= 0; i--)
        {
            int m = A[i] * B[j];
            int sum = m + C[move] + carry;
            int num = sum%10;
            int c = sum/10;
            C[move] = num;
            carry=c;
            move--;
        }
        C[move]=C[move]+carry;            
        s--;            
    }
}

Addition Function

int D[100]; // Addition is in D-array 
void add(int A[], int M, int B[], int N)
{
   int sum[100];
   int carry = 0;
   int k = 0;
   int i = M - 1;
   int j = N - 1;

   for (; i >= 0 && j >= 0; i--, j--, k++) {
      sum[k] = (A[i] + B[j] + carry) % 10;
      carry = (A[i] + B[j] + carry) / 10;
   }

   if (M > N) {
      while (i >= 0) {
         sum[k++] = (A[i] + carry) % 10;
         carry = (A[i--] + carry) / 10;
      }
      if(sum[k-1]!=carry)
         sum[k++]=carry;
   } 
   else if (M < N) {
      while (j >= 0) {
         sum[k++] = (B[j] + carry) % 10;
         carry = (B[j--] + carry) / 10;
      }
      if(sum[k-1] != carry)
         sum[k++]=carry;
   }
   else {
      if (carry > 0)
         sum[k++] = carry;
   }

   for (i=0; k>=0; i++)
     D[i] = sum[--k];
}