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

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

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

``````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];
}
``````
Similar Questions

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

Result should be stored in new linked list.

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