求助：大整数乘法

Question

刚才看了一下分治法，还是没看懂。用java来实现的更是少之又少，我是个初学者，希望哪位高手可以用简单的程序来实现大整数乘法：
是用数组去实现，在线等回复，谢谢

Answer 1

大整数 long不可以吗？
  另你也可以自己定义一个需要的类型

Answer 2

原理很简单，不过用代码实现出来还是挺复杂的。最近正在学习分治法，顺便写一个练练手，呵呵。我是按照2为划分单位分治的，所以算法的时间复杂度理论上应该是O(lbn)，Gilles Brassard和Paul Bratley在其合著的《算法基础》一书的第一章中介绍了这种算法，而且，作者还说不一定局限于以2为划分单位，因数的位数也不一定要求相等，这个就没有深究了。分治法确实太伟大了，我的算法写的看上去及其复杂，但我将两个Long.MAX_VALUE相乘，还是在很短的时间内得到了结果。代码如下，欢迎大家批评指正：public class Multiplication { public static void main(String[] args) {
// 9223372036854775807L是Java的Long.MAX_VALUE
System.out.println(multiply(9223372036854775807L, 9223372036854775807L));
}

/*
 * 由于积可能超过long的最大值，故返回String，Java类库中有BigDecimal，为了使算法更单纯，就没有用
 */
public static String multiply(long m1, long m2) { // 使m1和m2位数相等，并同时等于2的幂
int maxLength = (int)(Math.ceil(Math.log10(Math.max(m1, m2)))); // 两数中大数的位数
int length = 1 << (int)(Math.ceil(Math.log(maxLength)/Math.log(2))); // 就近增大为2的整数次幂 // 相乘，见下面的multiply()方法和distributeToArray()方法
byte[] result = multiply(distributeToArray(m1, length), distributeToArray(m2, length));

// 按反序获取结果数组中的位，并忽略高位上补的0
StringBuffer resultString = new StringBuffer();
for (int i = result.length, appended = 0; i > 0; i--)
if (result[i-1] != 0 || appended == 1) { // 从第一个非0位开始获取
resultString.append(result[i-1]);
appended = 1;
} return resultString.toString();
}

/*
 * m1和m2长度必须相等且同为2的整数次幂
 */
private static byte[] multiply(byte[] m1, byte[] m2) { int length = m1.length; // 如果是一位相乘则直接返回结果数组
if (length == 1)
return distributeToArray(m1[0]*m2[0], 2); // 结果数组，长度是因数的2倍
byte[] result = new byte[length << 1];

// 因数长度的一半
int halfLength = length >> 1;

// m1的左半部
byte[] m1Left = new byte[halfLength];
System.arraycopy(m1, 0, m1Left, 0, halfLength); // m1的右半部
byte[] m1Right = new byte[halfLength];
System.arraycopy(m1, halfLength, m1Right, 0, halfLength); // m2的左半部
byte[] m2Left = new byte[halfLength];
System.arraycopy(m2, 0, m2Left, 0, halfLength); // m2的右半部
byte[] m2Right = new byte[halfLength];
System.arraycopy(m2, halfLength, m2Right, 0, halfLength);

// 分治法两两交叉相乘
byte[] resultLL = multiply(m1Left, m2Left);
byte[] resultLR = multiply(m1Left, m2Right);
byte[] resultRL = multiply(m1Right, m2Left);
byte[] resultRR = multiply(m1Right, m2Right);

System.arraycopy(resultLL, 0, result, 0, length); // 组合乘积，要注意进位
// 下面这三个循环写的比较傻，有更好的写法
for (int i = 0; i < length; i++) {
int s = result[i+halfLength] + resultLR[i];
if (s < 10)
result[i+halfLength] = (byte)s;
else {
result[i+halfLength] = (byte)(s-10);  // 大于10则往高位进1
result[i+halfLength+1] += 1;
}
}
for (int i = 0; i < length; i++) {
int s = result[i+halfLength] + resultRL[i];
if (s < 10)
result[i+halfLength] = (byte)s;
else {
result[i+halfLength] = (byte)(s-10);  // 大于10则往高位进1
result[i+halfLength+1] += 1;
}
}
for (int i = 0; i < length; i++) {
int s = result[i+length] + resultRR[i];
if (s < 10)
result[i+length] = (byte)s;
else {
result[i+length] = (byte)(s-10);  // 大于10则往高位进1
result[i+length+1] += 1;
}
}
return result;
}

/*
 * 该方法用来将整数按10进制位放入指定长度的byte数组，整数的高位也是数组的高位，不够填0
 */
private static byte[] distributeToArray(long l, int length) {
byte[] result = new byte[length];
for (int i = 0; l > 0; i++, l /= 10)
result[i] = (byte)(l % 10);
return result;
}}
程序的输出结果是：85070591730234615847396907784232501249

Answer 3

Java 有自己的 BigDecimal 你看看帮助吧！
非得用数组啊？ 我建议你研究一下BigDecimal的源代码，也许有收获!

Answer 4

就是，为什么不用BigInteger或者BigDecimal之类的东西，既然用java，人家已经开发好的api就应该让使。

Answer 5

你好，
int maxLength = (int)(Math.ceil(Math.log10(Math.max(m1, m2)))); // 两数中大数的位数
int length = 1 << (int)(Math.ceil(Math.log(maxLength)/Math.log(2))); // 就近增大为2的整数
请问，maxLength为什么是“两数中大数的位数”呢？
如果max=100，
maxLength求得为2
但是maxlength明显为3嘛

Answer 6

int maxLength = (int)(Math.ceil(Math.log10(Math.max(m1, m2)))); // 两数中大数的位数 
int length = 1 < < (int)(Math.ceil(Math.log(maxLength)/Math.log(2))); // 就近增大为2的整数 
这两行代码能给我解释一下吗？的确不懂~~~~~

Answer 7

自己写的话，算法还是很简单的，效率估计（肯定。。）没有java自带的api高

Answer 8

就大整数乘法来说，还是有效率很高的算法的。但用到数学知识较多，是将两个整数作为序列进行FFT，即离散福利叶变换，然后两个序列相乘，将结果IFFT，稍微整理一下，即可得出结果。效率比java自带的api要高。