Search This Blog

Sunday, January 1, 2012

Multiply Two Large Numbers - JAVA



public class MultiplyTwoLargeNumbersTest {


/** a and b hold very large integer values such that if these are multiplied, the result can't be stored in
 *  another integer variable as the size will cross the limit or the maximum value an integer variable can hold.
 *  Thus, this code is designed to multiply such big numbers and store the result into a String variable.
 */
public static void main(String[] args){

int a = 999999999;
int b = 888888888;

MultiplyTwoLargeNumbers obj = new MultiplyTwoLargeNumbers(new Integer(a).toString(),new Integer(b).toString());
String result = obj.mulTwoNum();
System.out.println(result);
}
}

class MultiplyTwoLargeNumbers{

private String number1,number2;


/** The constructor of this class 'MultiplyTwoLargeNumbers' sets the instance variables number1 and number2
*   which are of String type with the integer values passed into itusing the toString() method for String.
*/
public MultiplyTwoLargeNumbers(String n1 , String n2){
number1 = n1;
number2 = n2;
}


/** This method 'mulTwoNum' is doing all the main stuff of multiplying two numbers stored as a String in the
*   instance variables number1 and number2.
*/
public String mulTwoNum(){

int arr1[];
int arr2[];

arr1 = convertToArray(number1);
arr2 = convertToArray(number2);

int arr3[][] = new int[arr2.length][arr1.length+arr2.length];
int arr4[] = new int[arr1.length+arr2.length+2];

for(int p=0 ; p<arr1.length+arr2.length+1 ; p++)
arr4[p]=0;

for (int y=0 ; y<arr2.length ; y++){
for (int z=0 ; z<arr1.length+arr2.length ; z++){
arr3[y][z] = 0;
}
}

for (int k=0,row=0 ; k<arr2.length ; k++,row++){ //for num2
for (int j=0 , col=arr2.length+arr1.length-1-k ; j<arr1.length ;col--, j++){ //for num1

arr3[row][col] = arr1[arr1.length-1-j]*arr2[arr2.length-k-1];

}

}
for (int y=0 ; y<arr2.length ; y++){
for (int z=0 ; z<arr1.length+arr2.length ; z++){
}
}


for (int y=arr1.length+arr2.length-1 ; y>0 ; y--){
for (int z=0 ; z<arr2.length ; z++){
arr4[(arr1.length+arr2.length+1)-(arr1.length+arr2.length-1)+y] += arr3[z][y];

}
}

for(int u=0 ; u<arr4.length ; u++){
}

for(int q=arr4.length-1 ; q>0 ; q--){
if(arr4[q]>9){
arr4[q-1] += arr4[q]/10;
arr4[q]=arr4[q]%10;
}
}
String strToRet="";

for(int u=0 ; u<arr4.length ; u++){
strToRet += new Integer(arr4[u]).toString();
}

return trimResultString(strToRet);
}


 /** The method 'convertToArray' takes String as a parameter containing an integer value and returns
 *   an array of integer.
 *   For example, if str = "216" then, this method will return a with values a[0]=2, a[1]=1 and a[2]=6.
 */
public int[] convertToArray(String str){

int a[] = new int[str.length()];
for(int i=0 ; i<str.length() ; i++){
a[i] = Integer.parseInt(str.substring(i,i+1));
}
return a;
}


    /** The method 'trimResultString' takes a String parameter and returns a String value.
* This method is to get rid of extra 0s present at the beginning of 'res'.
    * For example, if res = "000156" then, this method will return "156".
*/
public String trimResultString(String res){

int ind[] = new int[10];
int index=99999;

for(int i=0 ; i<10 ; i++){
ind[i] = res.indexOf(new Integer(i).toString());
}
for(int i=1 ; i<9 ; i++){
if(ind[i]>0)
index = Math.min(index, ind[i]);
}
res = res.substring(index);

return res;
}
}

No comments:

Post a Comment