自己动手写Java大整数《2》优化和乘法

136 阅读 0 评论 90 点赞

我是靠谱客的博主贤惠烤鸡，这篇文章主要介绍自己动手写Java大整数《2》优化和乘法，现在分享给大家，希望可以做个参考。

在决定自己动手写Java下的大整数包后。

上周写了大整数的表示、绝对值的比较大小、取负值和加减法运算。

这次我看到别人的方法后改进了绝对值比较大小的代码，并且添加上大整数的乘法运算。

修改绝对值比较

上次写的绝对值的比较没有事先好好分析下，直接逐情况排除，代码非常难看。

这次看到别人很简洁的代码。由于输出只可能是-1,0,1. 可以逐渐剥离-1和1的情况剩下的就是0的情况。

见代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
	/*
* 修改的简洁版的比较绝对值
*/
public int Abscompare(DecimalBig that)
{
if(this.digits.length < that.digits.length) {
return -1;
}
if (that.digits.length < this.digits.length) {
return 1;
}
for(int i = 0; i < this.digits.length; i++) {
if(this.digits[i] < that.digits[i]) {
return -1;
}
if(that.digits[i] < this.digits[i]) {
return 1;
}
}
return 0;
}

乘法运算

这里乘法运算同样实行十进制一样的简单的运算法则。

其实乘法还可以使用Karatsuba快速乘法、快速傅里叶变换乘法。对于特殊的平方运算

也有优化的算法。这都待后续补充。这里只实现简单的乘法。

具体见123456*123321的图示实例

第二个数组的每一位乘以第一个数组，得到一串数组，并错位相加。

具体执行见图示

这里会用到两个数组相加的方法

复制代码

1
public static int[] Add(int[] x, int[] val)

这里有一个要注意的地方。就是数组的每一位是一个int型的数，逐位相乘时先转换成long型的数

运算。最后把long型的数转换成两位Radix=10^9进制的数。

对于带符号的运算，首先判断只要有一个因子是0乘积就是0，否则乘积的符号就是this.sign乘以that.sign.

（上版本代码有bug，已修复）

复制代码

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

public DecimalBig Multiply(DecimalBig that)
{
if (this.sign==0||that.sign==0)
<span style="white-space:pre">
</span>return Zero;
int resultsign=this.sign;
int[] resultdigits={0};
for(int i=that.digits.length-1;i>=0;i--)
{
//建立数组默认全零
int[] addresult = new int[this.digits.length];
int carry=0;
for (int j=this.digits.length-1;j>=0;j--)
{
long addlong= (long)this.digits[j]*that.digits[i]+carry;
int lowbit=(int)(addlong%Radix);
carry=(int)(addlong/Radix);
addresult[j]=lowbit;
}
if (carry>0)
{
int[] temp = new int[this.digits.length + 1];
System.arraycopy(addresult, 0, temp, 1, addresult.length);
temp[0] = carry;
addresult = temp;
}
int[] temp2=new int[addresult.length+that.digits.length-1-i];
System.arraycopy(addresult, 0, temp2, 0, addresult.length);
resultdigits=Add(resultdigits, temp2);
}
return new DecimalBig(resultsign, resultdigits);
}

后面除法需要int数组乘以int数的运算，其实上面乘法里也包含了这样的运算，下面我单独列出来以备后面使用

复制代码

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

/*
* 数组乘以一个int类型的数
*/
public int[] Multiplyint(int th[], int that)
{
if (th==Zero.digits||that==0)
return Zero.digits;
//建立数组默认全零
int[] addresult = new int[th.length];
int carry=0;
for (int j=th.length-1;j>=0;j--)
{
long addlong= (long)th[j]*that+carry;
int lowbit=(int)(addlong%Radix);
carry=(int)(addlong/Radix);
addresult[j]=lowbit;
}
if (carry>0)
{
int[] temp = new int[th.length + 1];
System.arraycopy(addresult, 0, temp, 1, addresult.length);
temp[0] = carry;
addresult = temp;
}
return addresult;
}