java大数相乘算法

准备阶段：

       准备一个整型数组若无特别说明下文提到的数组都是指该整型数组其维数为str1和str2这两个字符串的长度之和（两数相乘，其乘积的位数必不大于两乘数的位数之和）。因事先无法知道str1和str2的长度，所以使用动态内存分配的方式定义该数组这里记为arr。该数组的作用是用来保存两个大数相乘的结果每个数组元素存放一个整数并且该整数是0~9间的整数。初始状态都设置为0。

运算步骤：

        在进行大数相乘时仍然采用传统的计算方式即从数的最低位开始用其每一位依次与被乘数相乘然后将结果依次相加。显然要得到最终结果需要涉及到多次的相乘和相加的运算。

        第一次相乘

               （本文约定一次相乘意为乘数的某一位和被乘数的所有位依次相乘并把结果进行相应处理后的一次过程）乘数str2的末位bn与被乘数的每一位相乘并把结果按末位在前首位在后的顺序存入数组arr中。若1≤k≤m如果c[k]≥10则需要进位使得c[k+1]=c[k+1]+c[k]/10c[k]=c[k]%10这个过程称之为数组的重构。

        当进行第二次相乘时乘数str2的倒数第二位b[n- 1]与被乘数的每一位相乘结果依次和数组arr中的attr[2]~attr[m+1]的元素相加并且修改对应数组元素然后按需要进行数组的重构。以此类推当完成第n次相乘后数组arr中存放的数据便是最终结果不过是反序的即最高位在后个位在前这时只要将结果数组逆转，并移除首位为0的元素。最后依次输出每个数组元素的值即可

下面是用Java具体代码的实现：

import java.util.Arrays;

public class BigNumberMultiplication {

	/**
	 * 计算两数相乘
	 * 在进行大数相乘时，仍然采用传统的计算方式，即从数的最低位开始，用其每一位依次与被乘数相乘，然后将结果依次相加存放在结果数组中；（结果数组为末位在前首位在后）
	 * 每次相乘之后对数组进行重构，对大于10的产生进位；
	 * 计算完后对结果数组进行逆转，逆转完之后将结果首位为0的的元素移除，此时的结果数组就为最终计算的结果。
	 * @param str1	被乘数
	 * @param str2	乘数
	 * @return 返回两数相乘后的结果数组
	 */
	public int[] calculateMulti(int[] str1,int[] str2){
		int[] resultArr = new int[str1.length+str2.length];//两数相乘的最大位数不会超过两数的长度之和
		int offset =0;//记录乘数已经进行计算的次数，即进行第几次乘数运算
		for(int i=str2.length-1;i>=0;i--){
			//用其每一位一次与被乘数相乘，将结果一次相加存放在结果数组对应位置中
			for(int j=str1.length-1;j>=0;j--){
				resultArr[offset+str2.length-1-j]+=str2[i]*str1[j];
			}
			//重构数组
			rebulidResultArr(resultArr,offset,str1.length);
			offset++;
		}
		convertResultArr(resultArr);
		//将结果首位为0的元素移除
		boolean isBegin= false;
		for(int i=0;i<resultArr.length;i++){
			if(!isBegin&&resultArr[i]>0){
				isBegin = true;
				resultArr = Arrays.copyOfRange(resultArr, i, resultArr.length);
				break;
			}
		}
		return resultArr;
	}

	/**
	 * 重构结果数组，判断指定位的数值是否大于10，如果大于10就要进位
	 * @param resultArr	待重构的数组
	 * @param offset	重构的起始索引，在这里为第几次重构或者第几次相乘
	 * @param length	需要重构的长度，在这里为被乘数的长度。
	 */
	private void rebulidResultArr(int[] resultArr, int offset, int length) {
		int i= offset;
		while(i<offset+length){
			if(resultArr[i]>10){
				resultArr[i+1] += resultArr[i]/10;
				resultArr[i] %= 10;
			}
			i++;
		}
	}
	/**
	 * 翻转数组，将指定的数组逆转过来
	 * @param resultArr	待翻转的数组
	 */
	private void convertResultArr(int[] resultArr){
		int i=0,j=resultArr.length-1,temp = 0;
		while(i<j){
			temp = resultArr[i];
			resultArr[i]=resultArr[j];
			resultArr[j]=temp;
			i++;
			j--;
		}
	}
	/**
	 * 打印计算的结果
	 * @param resultArr	计算的结果数组
	 */
	public void printResultArr(int[] resultArr){
		for(int i=0;i<resultArr.length;i++){
			System.out.print(resultArr[i]);
		}
	}
	
	public static void main(String[] args) {
		BigNumberMultiplication test= new BigNumberMultiplication();
		int[] str =new int[20];
		for(int i=0;i<str.length;i++){
			str[i]=(i+1)%10;
			System.out.print(str[i]);
		}
		System.out.println();
		int[] resuleArr = test.calculateMulti(str, str);
		test.printResultArr(resuleArr);
		
	}
	
	
}