mod.java

大数除法（含模）有时需要进行超多位数的除法

import java.math.BigInteger;//使用java大数包来检验结果的正确性
public class MOD
{
	public static void main (String args[])
	{
		int op1[]={5,5,3,2,2,3,2,3,5,4,5,4,2,3,1,2,3,1,2,3,5,1,3,5,6,5,4,3,2,3,1
		,2,1,2,2,3,1,2,2,1,5,5,1,2,0,2,5,4,5,1,2,2,0,0,2,1,5,4,1,2,0,9,8,8,7,9,7
		,8,5,6,4,6,5,8,5,4,8,8,5,4,4,5,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,2,3,5,5,1,6
		,5,1,6,5,1,5,1,6,4,1,5,3,4,1,1,5,6,4,5,6,7,6,5,7,1,5,4,2,1,8,4,5,6,5,9,6
		,9,8,7,5,8,7,5,9,8,5,2,5,4,4,5,8,7,6,6,8,5,4,7,8,6,5,8,4,1,2,5,7,5,6,8,0
		,9,8,7,5,8,4,5,2,2,5,7,8,5,4,5,5,6,8,2,5,2,5,5,2,2,5,5,2,2,5,5,2,3,6,5,5
		,9,8,5,4,2,1,5,7,7,8,5,4,6,9,9,2,2,0,0,2,5,5,2,2,2,0,2,2,2,0,2,8,2,5,6,8
		,8,5,6,9,8,7,4,1,2,5,2,1,0,1,0,2,6,6,8,5,5,6,5,5,2,5,6,5,7,4,2,6,5,5,4,9
		,9,8,5,5,7,4,7,8,8,4,1,2,5,6,9,8,5,6,3,2,5,8,7,4,5,5,8,4,2,3,5,4,5,2,6,4
		,9,8,7,5,8,7,5,9,8,5,2,5,4,4,5,8,7,6,6,8,5,4,7,8,6,5,8,4,1,2,5,7,5,6,8,0
		};//被除数		
		int op2[]={4,6,9,8,4,3,5,1,4,4,3,8,9,7,3,4,5,8,4,6,3,4,2,3,3,5,5,5,4,1,2
		,8,5,5,8,5,5,4,5,2,6,5,5,6,2,3,2,3,3,5,5,1,1,5,5,5,4,6,4,5,5,5,5,4,4,5,2
		,5,5,5,8,7,4,5,8,4,1,1,2,5,8,7,4,4,5,6,9,8,5,6,5,7,4,5,8,2,2,3,0,3,6,5,6
		};//除数
		int len1=op1.length,len2=op2.length;//取得被除数与除数的长度
		System.out.println("被除数的长度："+len1+"位，除数的长度:"+len2+"位。\n被除数：");
		for(int n=0;n<len1;n++)
			System.out.print(op1[n]);System.out.println("\n除数：");//显示被除数
		for(int n=0;n<len2;n++)
			System.out.print(op2[n]);//显示除数
		System.out.println("\n除法结果：(用java包做除法比较结果)");		
		BigInteger p,q;
		p = new BigInteger("5532232354542312312351356543231212231221551202545122002154120988797856465854885445123456789123456235516516515164153411564567657154218456596987587598525445876685478658412575680987584522578545568252552255225523655985421577854699220025522202220282568856987412521010266855655256574265549985574788412569856325874558423545264987587598525445876685478658412575680");
		q = new BigInteger("4698435144389734584634233555412855855452655623233551155546455554452555874584112587445698565745822303656");
		long time=System.currentTimeMillis();//取得时间
		System.out.println(p.divide(q));//显示除法的结果		
		System.out.println("用包做除法得出的模");
		System.out.println(p.mod(q));//显示模
		time=System.currentTimeMillis()-time;
		System.out.println("java除法运行需要："+time+"微秒.");
		time=System.currentTimeMillis();//取得时间
		MOD zgb = new MOD();
		System.out.print("除法结果：(我的结果)\n");
		zgb.div(op1,len1,op2,len2);//做除法并求模
		System.out.println("\n模(我的结果)");
		for(int n=0;n<len1;n++)
		{
			if(op1[n]!=0)
			for(;n<len1;n++)
			System.out.print(op1[n]);//求出模
		}
		System.out.println();		
		time=System.currentTimeMillis()-time;
		System.out.println("我的运行需要："+time+"微秒.");
	}
	public void div(int op1[],int len1,int op2[],int len2)
	{
		int[] b=new int[len2+1];
		int i,j,k=0;
		for(i=len2-1;i<len1;)
		{
			int k1=k,i1=i;
			for(j=1;j<=10;j++)
			{
				mul(op2,len2,j,b);				
				if(com(b,len2,op1,k,i)==2)
				{
					if(j!=1)
					{
						mul(op2,len2,j-1,b);
						sub(op1,k,i,b,len2);
					}
					while(op1[k]==0)
						k++;
					i++;
					System.out.print(j-1);//做除法的结果
					break;
				}
			}
		}
	}
	public void mul(int op1[],int len,int op2,int result[])
	{
		int i;
		result[len]=0;
		for(i=len;i>0;i--)
		{
			result[i]+=op1[i-1]*op2;//做乘法
			result[i-1]=result[i]/10;
			result[i]%=10;//进位，最高进位保存在result[0]，没进位则为0
		}
	}
	public int com(int op1[],int len,int op2[],int s,int t)
	{
		int i=0;
		if(op1[0]==0)	i++;
		if(len-i>t-s)//op1的长度大于op2,返回2，以示大于
			return 2;
		else if(len-i<t-s)//op1的长度小于op2,返回1，以示小于
			return 1;
		for(;i<=len;i++,s++)
		{
			if(op1[i]!=op2[s])
			{
				if(op1[i]>op2[s])//一旦发现op1上某位数大于op2，即大于，否则小于
					return 2;//大于
				else
					return 1;//小于
			}
		}
		return 0;//op1与op2的长度相等，而且各位数都相等，故判定两数相等
	}
	public boolean sub(int op1[],int s,int i,int op2[],int j)
	{
		for(;i>=s;i--,j--)
		{
			op1[i]-=op2[j];
			if(op1[i]<0)
			{
				if(i>s)
				{
					op1[i]+=10;//做减法
					op1[i-1]--;
				}
				else return false;
			}
		}
		return true;
	}
}