Java 小例子：大数乘法和阶乘

这是一个不借助 BigInteger 来实现大数乘法的例子，顺便做了一个阶乘。

大数乘法的实现是基于印度的格子乘法（参考这里），使用这种方法，计算 m 位数乘以 n 位数只需要创建一个 m+n 位的数组保存结果即可。

当然，这种方式效率绝不可能跟 BigInteger 比，但作为初学者的练习，是很有价值的。

public class BigMultiply { public static void main(String[] args) { System.out.println(factorial(“1000”)); } /** * 阶乘 * * @param n 要进行阶乘的数字 * * @return 阶乘结果 */ private static String factorial(String n) { if (Integer.parseInt(n) <= 1) { return “1”; } else { return bigMultiply(n, factorial(String.valueOf(Integer.parseInt(n) – 1))); } } /** * 大数字乘法 * * @param number1 数字1 * @param number2 数字2 * * @return 乘法结果 */ private static String bigMultiply(String number1, String number2) { short[] numbers1 = toIntArray(number1); short[] numbers2 = toIntArray(number2); short[] result = multiply(numbers1, numbers2); return toString(result); } private static short[] multiply(short[] numbers1, short[] numbers2) { short[] result = new short[numbers1.length + numbers2.length]; for (int i = 0; i < numbers1.length; i++) { for (int j = 0; j < numbers2.length; j++) { int tenth = i + j; int cellResult = numbers1[i] * numbers2[j]; put(result, tenth + 1, cellResult % 10); put(result, tenth, cellResult / 10); } } return result; } /** * put <i>number</i> into <i>index</i> position of <i>result</i> * * @param result – * @param index – * @param number – */ private static void put(short[] result, int index, int number) { result[index] += number; carryFrom(result, index); } /** * 进位 * * @param result 数组 * @param index 开始进位的位置 */ private static void carryFrom(short[] result, int index) { if (index < 0) { return; } if (result[index] >= 10) { result[index – 1]++; result[index] = (short)(result[index] – 10); carryFrom(result, index – 1); } } private static short[] toIntArray(String numbers) { short[] result = new short[numbers.length()]; for (int i = 0; i < numbers.length(); i++) { result[i] = (short)(Integer.parseInt(numbers.substring(i, i + 1))); } return result; } private static String toString(short[] ints) { int start = 0; while (ints[start] == 0) { start++; } String str = “”; while (start < ints.length) { str += ints[start]; start++; } return str; }}

影子依旧可以相亲相爱。哪一块骨骼最温暖，总能一击即中。