目录
java大数运算详解【其一】大数加减法
java大数运算详解【其二】大数乘法
java大数运算详解【其三】大数乘法之平方算法之按位二次展开式算法
java大数运算详解【其四】大数乘法之平方算法之Karatsuba平方算法
java大数运算详解【其五】大数乘法之平方算法之ToomCook3平方算法
java大数运算详解【其六】大数乘法之单位乘法和经典乘法
java大数运算详解【其七】大数乘法之Karatsuba乘法和ToomCook3乘法
java大数运算详解【其八】大数除法
java大数运算详解【其九】大数除法之试商法（Knuth除法）核心算法
java大数运算详解【其十】大数除法之Burnikel-Ziegler除法算法
所有解释都是最基本的，没有过多赘述，如若不懂静心思考。
1.1、按位二次展开式算法
/**
* 将整型数组x的内容平方，结果放入整型数组z中，x的内容不变。
*/
private static final int[] squareToLen(int[] x, int len, int[] z) {
int zlen = len << 1;
if (z == null || z.length < zlen)
z = new int[zlen];
// 在调用intrinsified（增强）方法之前执行检查。
implSquareToLenChecks(x, len, z, zlen);
return implSquareToLen(x, len, z, zlen);
}
/**
* 参数验证。
*/
private static void implSquareToLenChecks(int[] x, int len, int[] z, int zlen) throws RuntimeException {
if (len < 1) {
throw new IllegalArgumentException("invalid input length: " + len);
}
if (len > x.length) {
throw new IllegalArgumentException("input length out of bound: " +
len + " > " + x.length);
}
if (len * 2 > z.length) {
throw new IllegalArgumentException("input length out of bound: " +
(len * 2) + " > " + z.length);
}
if (zlen < 1) {
throw new IllegalArgumentException("invalid input length: " + zlen);
}
if (zlen > z.length) {
throw new IllegalArgumentException("input length out of bound: " +
len + " > " + z.length);
}
}
/**
* Java运行时可以为该方法使用intrinsic（固有的，增强的）。
*/
@HotSpotIntrinsicCandidate
private static final int[] implSquareToLen(int[] x, int len, int[] z, int zlen) {
/*
* 这里使用的算法来自Colin Plumb的C库。
* 技巧:考虑乘法中的部分乘积
* “abcde”本身:
*
* a b c d e
* * a b c d e
* ==================
* ae be ce de ee
* ad bd cd dd de
* ac bc cc cd ce
* ab bb bc bd be
* aa ab ac ad ae
*
* 注意主对角线以上的所有元素:
* ae be ce de = (abcd) * e
* ad bd cd = (abc) * d
* ac bc = (ab) * c
* ab = (a) * b
*
* 是主对角线以下所有内容的副本:
* de
* cd ce
* bc bd be
* ab ac ad ae
*
* 因此，总和是2 *(对角线上方或下方)+对角线。
*
* 这是从对角线开始累积的(对角线由输入数字的平方组成)，
* 然后对角线除以2，非对角线相加，再乘以2。
* 低位只是输入低位的一个副本，因此不需要特别注意。
*/
// 储存平方值，右移一位(即，除以2)。
int lastProductLowWord = 0;
for (int j=0, i=0; j < len; j++) {//计算每一位的平方值并存储在z中且右移一位
long piece = (x[j] & LONG_MASK);
long product = piece * piece;
z[i++] = (lastProductLowWord << 31) | (int)(product >>> 33);
z[i++] = (int)(product >>> 1);
lastProductLowWord = (int)product;
}
// 计算对角线上方或下方的总和
for (int i=len, offset=1; i > 0; i--, offset+=2) {//注意：offset-1=2*(len-i)，即：2*len-offset=2*i-1.
int t = x[i-1];
t = mulAdd(z, x, offset, i-1, t);
addOne(z, offset-1, i, t);//t的添加位置为z[z.length-1-(offset-1)-i]，即：z[2*len-offset-i].
//故addOne函数最多需进位传播2*len-offset-i=i-1次，为判断运算是否溢出，需传参mlen为i，而不是i-1.
//其实运算一定不会产生溢出（zlen=2*len时），所以传参mlen为i-1也可行（同时传参offset为offset）。
}
// 回移并设置低位
primitiveLeftShift(z, zlen, 1);
z[zlen-1] |= x[len-1] & 1;
return z;
}
/**
* 将数组乘以一个整数k，然后添加到结果中，返回进位。
*/
static int mulAdd(int[] out, int[] in, int offset, int len, int k) {
implMulAddCheck(out, in, offset, len, k);
return implMulAdd(out, in, offset, len, k);
}
/**
* 参数验证。
*/
private static void implMulAddCheck(int[] out, int[] in, int offset, int len, int k) {
if (len > in.length) {
throw new IllegalArgumentException("input length is out of bound: " + len + " > " + in.length);
}
if (offset < 0) {
throw new IllegalArgumentException("input offset is invalid: " + offset);
}
if (offset > (out.length - 1)) {
throw new IllegalArgumentException("input offset is out of bound: " + offset + " > " + (out.length - 1));
}
if (len > (out.length - offset)) {
throw new IllegalArgumentException("input len is out of bound: " + len + " > " + (out.length - offset));
}
}
/**
* Java运行时可以为该方法使用intrinsic（固有的，增强的）。
* 将in数组（长度为len，数据倒序存储）乘以k，再添加到out数组（偏移量为offset，数据倒序存储），
* 添加位置为第offset位，即out[out.length-offset - 1].
* 返回进位。
*/
@HotSpotIntrinsicCandidate
private static int implMulAdd(int[] out, int[] in, int offset, int len, int k) {
long kLong = k & LONG_MASK;
long carry = 0;
offset = out.length-offset - 1;//重计算偏移量
for (int j=len-1; j >= 0; j--) {
long product = (in[j] & LONG_MASK) * kLong +
(out[offset] & LONG_MASK) + carry;
out[offset--] = (int)product;
carry = product >>> 32;
}
return (int)carry;
}
/**
* 在a中加上一个整数，把carry这个整数加到a中。
* 把carry添加到a中，添加位置为第offset+mlen位，即a[a.length-1-mlen-offset].
* 进位最多传播mlen位。
* 返回结果进位。
*/
static int addOne(int[] a, int offset, int mlen, int carry) {
offset = a.length-1-mlen-offset;
long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK);
a[offset] = (int)t;
if ((t >>> 32) == 0)
return 0;
while (--mlen >= 0) {
if (--offset < 0) { // 数据溢出
return 1;
} else {
a[offset]++;
if (a[offset] != 0)
return 0;//进位传播处理完成，返回0
}
}
return 1;//进位传播了mlen次，仍未处理完毕，返回进位1
}
// 将a数组（长度len，数据倒序存储）左移n位，假设没有前导零，0<=n<32.
static void primitiveLeftShift(int[] a, int len, int n) {
if (len == 0 || n == 0)
return;
int n2 = 32 - n;
for (int i=0, c=a[i], m=i+len-1; i < m; i++) {//循环移位
int b = c;
c = a[i+1];
a[i] = (b << n) | (c >>> n2);
}
a[len-1] <<= n;
}
按位二次展开式算法，即将mag数组看作len个项的和，并使用二次展开式进行计算其平方值。
如果觉得《java大数运算详解【其三】大数乘法之平方算法之按位二次展开式算法》对你有帮助，请点赞、收藏，并留下你的观点哦！
