大数乘法

背景：当遇到大数相乘是，用编程语言里面的数字类型做乘法会出现溢出情况，无法满足要求，故需要用字符串方式进行做乘法运算。
此文记录该算法的一个实现。先记录下来，已被后用或后面回顾。

算法原理：还记得我们小学学的算法吗，就是小学算法原理，利用位相乘，进位累加到前一位的原理。
1、将两个大数分解成n个（一个大数*1个一位数字）
2、将另一个大数分解成n个（1位数）
3、分解完后乘法按位相加。

package com.shuidexiongdi.multi;

public class BigMulti {
	
	private static final int ascall = 48;
	
	/**
	 * 字符串乘法
	 * @param mul1
	 * @param mul2
	 * @return
	 */
	public static String doMul(String mul1, String mul2) {
		char[][] arrayTemp = new char[mul2.length()][mul1.length()+mul2.length()];
		initArrayZero(arrayTemp);
		for(int i = mul2.length(),j = 0; i > 0; i--,j++) {
			copyArray(arrayTemp[i-1],doMulti(mul1,mul2.charAt(i-1)),j);
		}
		char [] reaultTemp = doAdd(arrayTemp); 
		//如果第一位是0，则去掉0
		return reaultTemp[0] == '0' ? String.valueOf(reaultTemp,1,reaultTemp.length-1) :String.valueOf(reaultTemp);
//		return String.valueOf(doAdd(arrayTemp));
	}
	
	/**
	 * 乘法
	 * @param str1 字符串乘数
	 * @param multi2 一个字符的被乘数
	 * @return 乘法结果，用char数组返回
	 */
	private static char[] doMulti(String str1, char multi2) {
		int temp;
		int temp1;//个位
		int temp2;//十位
		char[][] arrayTemp = new char[str1.length()][str1.length()+1];
		initArrayZero(arrayTemp);
		for (int i = str1.length(), j = str1.length()+1; i > 0; i--, j--) {
			temp = (str1.charAt(i-1) - ascall) * (multi2 - ascall) ;
			temp1 = temp / 10; //
			temp2 = Math.abs(temp % 10);
			arrayTemp[i-1][j-2] = String.valueOf(temp1).charAt(0);
			arrayTemp[i-1][j-1] = String.valueOf(temp2).charAt(0);
		}
		
		return doAdd(arrayTemp);
	}
	
	/**
	 * 初始化0数组
	 * @param array
	 */
	private static void initArrayZero(char[][] array) {
		for(char[] aaa : array) {
			for(int i = 0; i < aaa.length; i++) {
				aaa[i] = '0';
			}
		}
	}
	
	
	/**
	 * 拷贝数组中字符至正确位
	 * @param targetArray
	 * @param array
	 * @param index 数组偏移量
	 */
	private static void copyArray(char[] targetArray, char[] array,int index) {
		for(int i = array.length,j = targetArray.length; i > 0; i--,j--) {
			targetArray[j-1-index] = array[i-1];
		}
	}
	
	/**
	 * 将数组中字符按位做加法运算
	 * @param array
	 * @return
	 */
	private static char[] doAdd(char[][] array) {
		char[] add = new char[array[0].length];
		for(int i = 0; i < add.length; i++ ) {
			add[i] = '0';
		}
		
		int next = 0;//进位
		for(int i = add.length; i > 0; i--) {
			int addTemp = 0;//相加中间数
			for(char[] aaa : array) {
				addTemp += (aaa[i-1] - ascall);
			}
			addTemp += next;
			int temp2 = Math.abs(addTemp % 10);
			add[i-1] = String.valueOf(temp2).charAt(0);
			next = addTemp / 10;
		}
		return add;
	}
	
	public static void main(String[] args) {
		System.out.println(doMul("3345454654654654654654656456565","4534543543534534534543543543543543543"));
	}
	
}

评论

1 楼 hdwmp123 2012-02-14