BigInteger提供的乘法操作
- 乘法 :
public BigInteger multiply(BigInteger val)
使用示例
1
2
3
4
5
6
7
8
| public class Test {
public static void main(String[] args) {
BigInteger a = new BigInteger("12090");
BigInteger b = new BigInteger("1234");
System.out.println(a.multiply(b));
}
}
|
实现思路
想到乘法我们很容易想到结合小学时学的列竖式的方法, 事实上老版的JDK的确是这么做的, 直接把mag数组的每一个int当做一个位（即把大整数当作$2^{32}$进制数）, 利用列竖式的思路进行计算两个乘数的绝对值的乘积，然后根据乘数的符号设置结果的符号。
但在我研究版本的JDK中还根据乘数的规模的不同选用不同的算法。选用不同算法的分界线是由实验确定的。
JDK中采用了三种算法：
本文章不对这些算法做讲解，已在单独的一篇文章（三种大数相乘算法）分析这些算法并剖析JDK中的源码实现。
下面对JDK中的实现源码（除了三种算法的具体实现）进行分析。
1
2
3
| public BigInteger multiply(BigInteger val) {
return multiply(val, false);
}
|
public BigInteger multiply(BigInteger val)调用的另一个重载方法，这个方法要求还传入一个boolean参数指定是否是递归调用，这个参数的具体作用看下文。
这个重载方法主要是根据乘数的规模（位数）的不同选用不同的算法，当规模较小时选用简单的小学生算法，当规模处于中等时采用Karatsuba算法，再大规模则采用Toom Cook-3算法。
这个重载方法在选用这三种算法之前，先判断是不是一些特殊情况以对采用专门为这些特殊情况提供的算法，具体如下：
- 如果两个乘数中有为0的，直接返回大整数0；
- 如果两个乘数时同一个，采用平方算法，平方算法不再剖析，平方算法和乘法的思路相同，将其转化为两个相同的乘数相乘，根据底数的规模选用三种乘法中的某一算法，在具体实现利用两个乘数相同的特点进行了优化；
- 如果两个乘数中有位数小于32位的，直接将此乘数转换成
int进一步计算（调用multiplyByInt）；
- 如果规模较小，调用
multiplyToLen，采用小学生算法进行计算；
- 如果规模中等，调用
multiplyKaratsuba，采用Karatsuba算法进行计算；
- 如果规模较大，调用
multiplyToomCook3，采用Toom Cook-3算法进行计算；
源码分析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| private BigInteger multiply(BigInteger val, boolean isRecursion) {
if (val.signum == 0 || signum == 0)
return ZERO;
int xlen = mag.length;
if (val == this && xlen > MULTIPLY_SQUARE_THRESHOLD) {
return square();
}
int ylen = val.mag.length;
if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD)) {
int resultSign = signum == val.signum ? 1 : -1;
if (val.mag.length == 1) {
return multiplyByInt(mag, val.mag[0], resultSign);
}
if (mag.length == 1) {
return multiplyByInt(val.mag, mag[0], resultSign);
}
int[] result = multiplyToLen(mag, xlen,
val.mag, ylen, null);
result = trustedStripLeadingZeroInts(result);
return new BigInteger(result, resultSign);
} else {
if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD)) {
return multiplyKaratsuba(this, val);
} else {
if (!isRecursion) {
if (bitLength(mag, mag.length) +
bitLength(val.mag, val.mag.length) >
32L*MAX_MAG_LENGTH) {
reportOverflow();
}
}
return multiplyToomCook3(this, val);
}
}
}
|
参数isRecursion作用是避免多次判断是否会溢出由于较大规模会调用Toom-Cook3，所以只有使用Toom-Cook3算法时才可能溢出。Toom-Cook3算法会递归的调用multiply，而判断是否可能溢出只需要在首次调用时被判断，当首次调用该方法时传入isRecursion为false，而当递归调用该算法时都出传入isRecursion为true。而判断是否溢出只当isRecursion为false时进行，这样就保证了只判断一次，避免重复进行浪费时间。
分析辅助方法multiplyByInt :
基本思路就是小学生算法，源码很容易看懂。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| private static BigInteger multiplyByInt(int[] x, int y, int sign) {
if (Integer.bitCount(y) == 1) {
return new BigInteger(shiftLeft(x,Integer.numberOfTrailingZeros(y)), sign);
}
int xlen = x.length;
int[] rmag = new int[xlen + 1];
long carry = 0;
long yl = y & LONG_MASK;
int rstart = rmag.length - 1;
for (int i = xlen - 1; i >= 0; i--) {
long product = (x[i] & LONG_MASK) * yl + carry;
rmag[rstart--] = (int)product;
carry = product >>> 32;
}
if (carry == 0L) {
rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length);
} else {
rmag[rstart] = (int)carry;
}
return new BigInteger(rmag, sign);
}
|