Monday, 30 June 2014

Multiplication of two huge number

Can we multiply two huge number of more than 1000 digit each?
the numbers are far larger than the range of "long long int".

yes, we can. the idea is pretty simple, Using the Elementary school approach.
for example, we want to multiply ABC with XY. we will store ABC in string num1, and XY in num2.

l1=num1.size(),  l2=num2.size(); 
here, l1 is the number of digit in 1st string and l2 is the number of digit in 2nd string.

the approach we were taught in primary school is:
last digit of the result array / string will be CY,
(last-1)th digit will be BY + CX,
(last-2)th digit will be AY + BX,
(last-3)th digit will be AX.
if any digit become larger than 9, then the carry will be added to the previous digit. 

initially all digit of result array is 0, we will first add AY, BY, CY to the array, then we will add AX, BX, CX to the array. to optimize the code a little, we will consider the carry operation after all intermediate multiplications. 

mx=l1+l2;
note that, the maximum number of digit of the result string is =l1+l2, and the minimum is = l1+l2-1 (if no carry for the first digit)
example: 1000*100 = 100000 & 9999*999=9989001.
                    
int arr[mx], n1[l1], n2[l2];  
for(int i=0; i<l1; i++) n1[i]=num1[i]-'0';
for(int i=0; i<l2; i++) n2[i]=num2[i]-'0';           
to make calculation easier, we will initialize:
--> an integer array arr[] of length mx for intermediate calculation for result array, 
--> an integer array n1[] of l1 length to store the numeric value of ASCII digit of string num1, 
--> an integer array n2[] of l2 length to store the numeric value of ASCII digit of string num2.

for(int i=l1-1; i>=0; i--)
        for(int j=l2-1; j>=0; j--)
            arr[i+j+1]+=n1[i]*n2[j];
this is the main part, consider 0-based index and look the index carefully, after multiplying ith digit of 1st string and jth digit of 2nd string, we are storing it in (i+j+1)th digit of result array.

for(int i=mx-1; i>0; i--)
   if(arr[i]>9)
   {
        arr[i-1]+=arr[i]/10;
        arr[i]=arr[i]%10;
   }
now, the carry operation, from last digit to first digit, if any value of array element  is 10 or more, simply add the carry to its left index. look at the condition, why i>0 instead of i>=0? we know the first digit can not have a carry, actually there no problem whether you write i>0 or i>=0.  

int pos=0;
while(!arr[pos]) pos++;     
the result array may contain leading zeroes, here, pos is the position of first non-zero array index.

string s="";
for(int i=pos;i<mx;i++)
    s+=arr[i]+'0';
initialize an empty string, after eliminating of leading zeroes, convert each digit value to ASCII and store it to the string from the first non-zero digit. now s is the result string of multiplication.

Code
Complexity of the code is O(l1*l2)
you will find plenty of problems related to big number multiplication.