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

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

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

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

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

修改绝对值比较

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

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

见代码

	/*
	 * 修改的简洁版的比较绝对值
	 */
	
	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的图示实例

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

具体执行见图示

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

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

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

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

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

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

		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数的运算，其实上面乘法里也包含了这样的运算，下面我单独列出来以备后面使用

		/*
		 * 数组乘以一个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;
		}