Multiplying large numbers in C/C++

Working with large numbers in C/C++ is always a problem. Those who have knowledge in Java/python tend to code in these languages for those particular problems. (Java has a BigInteger class where in there is no limit for integer range you work on. Python doesn’t have any limits on integers.) For those who wanted to handle large numbers in C/C++, lets discuss an approach for how to multiply large numbers.

We use arrays to store the numbers.
Why? Because we do not have any data type which could store big integers say around 10^3 digits.
How? Each digit of integer is stored in each index in the array. Lets store them in reverse order for simpler calculations.

Now we have two integers(A,B) in array each of length L1,L2 respectively. Product of these two numbers will be at most L1+L2. So lets take an empty Ans[] array of size 2*N.

Procedure :

Step 1 : Multiply index i of B with all the indexes j of A. Add the product to value in Ans[k] where 0 <= i < L2, 0 <= j < L1, k = i+j.
Step 2 : Repeat step 1 till i = L2. (Picture how you multiply two large numbers on a paper).
Step 3 :
for each i in range(0,L1+L2)
TMP = X/10. X = X%10. Y = Y+TMP.
X = A[i]
Y = A[i+1]
TMP = temporary variable.
Step 4 : reverse the array Ans, and that will be the final product.


#include <stdio.h>
#include <string.h>

int main()
    int a[100],b[100];
    int ans[200]={0};
    int i,j,tmp;
    char s1[101],s2[101];
    scanf(" %s",s1);
    scanf(" %s",s2);
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    for(i = l1-1,j=0;i>=0;i--,j++)
        a[j] = s1[i]-'0';
    for(i = l2-1,j=0;i>=0;i--,j++)
        b[j] = s2[i]-'0';
    for(i = 0;i < l2;i++)
        for(j = 0;j < l1;j++)
            ans[i+j] += b[i]*a[j];
    for(i = 0;i < l1+l2;i++)
        tmp = ans[i]/10;
        ans[i] = ans[i]%10;
        ans[i+1] = ans[i+1] + tmp;
    for(i = l1+l2; i>= 0;i--)
        if(ans[i] > 0)
    printf("Product : ");
    for(;i >= 0;i--)
    return 0;

Input :

Product : 3316139500221184007426

Related problems : Small Factorials(FCTRL2)
My Solution for Small Factorials


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s