top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

Provide an algorithm to add and multiply two large integers which cannot be represented by built-in types.

+2 votes
219 views

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?

posted Dec 10, 2015 by anonymous

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

0 votes

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];
}
answer Dec 19, 2015 by Salil Agrawal
Similar Questions
+7 votes

Input:
First List: 5->6->3 // represents number 563
Second List: 8->4->2 // represents number 842
Output
Resultant list: 4->7->4->0->4->6 // represents number 474046

0 votes

You are given 2 long integers having n digits each and you are required to multiply them using C.

Assumptions
Numbers are represented in an array of size n .
Calculate the time complexity using traditional divide and conquer

Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...