大数相乘的算法

昨天去参加某个公司的面试，前面的聊天还是挺愉快的，最后他给我出了道题，叫我算1000的阶乘。首先的想法是递归或者循环计算，但是思考了一下1000的阶乘的结果int和long肯定是存不下的，改用BigInteger别人不允许，最后就结果可想而知---被深深地鄙视了。我肯定是吞不下这口气啊，五分钟不够你就让我写出来，还是只有笔和纸。回到小窝，怀着郁闷和悲愤的心情，坚决攻克。最后就有如下的成果了。

测试结果：

1000的阶乘139ms，结果长度为2568；

10000的阶乘21909ms，结果程度为35660

 

代码如下：

 

	/**
	 * 计算从Start到end的乘积
	 * 
	 * @param start
	 *            开始索引
	 * @param end
	 *            结束索引
	 * @return 结果的字符串
	 */
	private static String getNumber(int start, int end) {
		String str = Integer.toString(start);
		for (int i = start; i < end; i++) {
			str = getBigInteger(str, Integer.toString(i + 1));
		}
		return str;
	}

 

// 计算两个数的乘积，任何长度
	private static String getBigInteger(String str1, String str2) {
		// 字符串长度
		int len1 = str1.length();
		int len2 = str2.length();

		// 存储最先添加的尾数
		StringBuffer buffer = new StringBuffer();
		// 存储最后一次加法运算的结果
		StringBuffer b = new StringBuffer();

		// 存储每一位相乘的结果
		int[] result = new int[len1 + 1];

		// 将字符串转换为整型数组
		char[] temp1 = str1.toCharArray();
		char[] temp2 = str2.toCharArray();

		int[] num1 = new int[len1];
		int[] num2 = new int[len2];

		// 初始化数组
		for (int i = 0; i < len1; i++) {
			num1[i] = Character.getNumericValue(temp1[i]);
		}
		// System.out.println();
		for (int j = 0; j < len2; j++) {
			num2[j] = Character.getNumericValue(temp2[j]);
		}

		// 计算每一位相乘的结果
		for (int i = len2 - 1; i >= 0; i--) {
			// 进位
			int carry = 0;
			// 从最低位算起
			for (int j = len1 - 1; j >= 0; j--) {
				// 加上进位和上一次运算结果的第j位得到该位的值
				int res = num2[i] * num1[j] + carry + result[j];
				carry = 0;
				// 如果结果大于等于10，得到进位值
				if (res >= 10) {
					carry = res / 10;
				}
				// 得到该位的结果
				result[j + 1] = res % 10;
				if (i <= 0 && j < len1 - 1) {
					b.append(result[j + 1]);
				}
			}
			// 最高位为进位值
			result[0] = carry;
			// 添加结果的最后一位
			buffer.append(result[len1]);
			if (i <= 0) {
				// 添加最高位
				b.append(result[0]);
				buffer.append(b);
			}
		}

		return reverseStringAndClearZero(buffer.toString());
	}

 

// 反向输出结果并且去掉最前面的0
	private static String reverseStringAndClearZero(String str) {
		StringBuffer buffer = new StringBuffer();
		boolean isZero = true;
		for (int i = str.length() - 1; i >= 0; i--) {
			if (isZero && str.charAt(i) != '0') {
				isZero = false;
			}
			if (!isZero) {
				buffer.append(str.charAt(i));
			}
		}
		return buffer.toString();
	}

 

小子不才，速度只能这样了，如果哪位大侠有更好的解决方案，请告知，谢谢

评论

3 楼 cloud21 2011-05-18  

月影无痕 写道

如果是应用中确实存在这个需求，那么我的解决办法可能就是预先缓存数据结果：

也就是说，将1－－1000的阶乘结果直接编译到程序中，以后在程序中调用时，可以直接使用，无须消耗CPU资源。

即使消耗，也仅仅是程序第一次计算阶乘的时间代码

说的很有道理了。

2 楼 bobo 2010-10-26  

月影无痕 写道

如果是应用中确实存在这个需求，那么我的解决办法可能就是预先缓存数据结果：

也就是说，将1－－1000的阶乘结果直接编译到程序中，以后在程序中调用时，可以直接使用，无须消耗CPU资源。

即使消耗，也仅仅是程序第一次计算阶乘的时间代码

空间换时间，相当于做了个缓存，看项目中使用的频率来采用不同的策略吧

另没有仔细阅读这个大数相乘的算法，是否可以理解自己实现一个BigInt的类以及乘法，这样参考BigInteger的源代码就好了

1 楼 月影无痕 2010-10-20  

如果是应用中确实存在这个需求，那么我的解决办法可能就是预先缓存数据结果：

也就是说，将1－－1000的阶乘结果直接编译到程序中，以后在程序中调用时，可以直接使用，无须消耗CPU资源。

即使消耗，也仅仅是程序第一次计算阶乘的时间代码