bignumbermultiplay.cs

大整数乘法算法

using System;
class bignumber
{
	public  static string stringadd(string s1,string s2)
	{
	     string s="";
		if(s1.Length==0)
			return s2;
		else if(s2.Length==0)
			return s1;
		if(s1[0]=='-'&s2[0]=='-')
		{
			s1=s1.Remove(0,1);
			s2=s2.Remove(0,1);
			s='-'+stringadd(s1,s2);
		}
		else if(s1[0]=='-')
		{
			s1=s1.Remove(0,1);
			//Console.WriteLine(s1);
			s=stringsub(s2,s1);
		}
		else if(s2[0]=='-')
		{
			s2=s2.Remove(0,1);
			s=stringsub(s1,s2);
		}
		else
		{
		    int a,b;
			a=s1.Length;
			b=s2.Length;
			if(a<b)
				s=stringadd(s2,s1);
			else
			{
			    int flag=0,i,c;
				s1=reverse(s1);
				s2=reverse(s2);
				for(i=0;i<=b-1;i++)
				{
				    c=s1[i]+s2[i]-96+flag;
					flag=c/10;
					s=c%10+s;
				}
				for(i=b;i<a;i++)
				{
				    c=s1[i]-48+flag;
					flag=c/10;
					s=c%10+s;
				}
				if(flag==1)
					s=flag+s;
			}
		}
		return s;
	}

	public static string stringsub(string s1,string s2)
	{
	    string s="";
		int a;
		a=comparestr(s1,s2);
		if(a==-1)
			s='-'+stringsub(s2,s1);
		else if(a==0)
			s=s+0;
		else
		{
		    int flag=0,i,c;
			s1=reverse(s1);
			s2=reverse(s2);
			flag=0;
			for(i=0;i<s2.Length;i++)
			{
			    c=s1[i]-s2[i]-flag;
				if(c<0)
				{
				    c=c+10;
					flag=1;
				}
				else
					flag=0;
				s=c+s;
			}
			for(i=s2.Length;i<s1.Length;i++)
			{
			    c=s1[i]-48-flag;
				if(c<0)
				{
				    c=c+10;
					flag=1;
				}
				else
					flag=0;
				s=c+s;
			}
			i=0;
			while(i<s.Length&s[i]=='0')
				i++;
			if(i==s.Length)
				s=s.Remove(0,i-1);
			else
				s=s.Remove(0,i);
		}
		return s;
	}

	public static string reverse(string s)
	{
	    int i;
		string s1="";
		for(i=s.Length-1;i>=0;i--)
            s1=s1+s[i];
		return s1;
	}

	public static int comparestr(string s1,string s2)
	{
	    int a,b,i;
		a=s1.Length;
		b=s2.Length;
		if(a>b)
			return 1;
		else if(a<b)
			return -1;
		else
		{
		    i=0;
			while(i<a&&s1[i]==s2[i])
				i=i+1;
			if(i==a)
				return 0;
			else 
				if(s1[i]>s2[i])
					 return 1;
			else
					 return -1;

		}
	}
	public static string bigmaltiplay(string s1,string s2)
	{
		string s="";
		if(s1[0]=='-'&s2[0]=='-')
		{
			s1=s1.Remove(0,1);
			s2=s2.Remove(0,1);
			return bigmaltiplay(s1,s2);
		}
		else if(s1[0]=='-')
		{
			s1=s1.Remove(0,1);
			s='-'+bigmaltiplay(s1,s2);
			return s;
		}
		else if(s2[0]=='-')
		{
		    s2=s2.Remove(0,1);
			s='-'+bigmaltiplay(s1,s2);
			return s;
		}

		 int a,b,i;
		string S1A,S1B,S2C,S2D,s3,s4,s5,s6,s7,s8;
		a=s1.Length;
		b=s2.Length;
		if(a==0|b==0)
			return "";
		i=0;                 //---开始把S1和S2前面的零去掉
		while(i<a&&s1[i]=='0')
			i=i+1;
		if(i==a)
			s1=s1.Remove(0,i-1);
		else
			s1=s1.Remove(0,i);
		i=0;
		while(i<a&&s2[i]=='0')
			i=i+1;
		if(i==a)
			s2=s2.Remove(0,i-1);
		else
			s2=s2.Remove(0,i);//-----结束--------
		if(a<=3&b<=3)
			s=s+int.Parse(s1)*int.Parse(s2);
		else if(b>a)
			s=bigmaltiplay(s2,s1);
		else 
		{   
			
			if(b<=a/2)
			{
				S1B=s1.Substring(a-b,b);
				S1A=s1.Remove(a-b,b);
				S2C="0";
				S2D=s2;
				s3=bigmaltiplay(S1A,S2C);
				s4=bigmaltiplay(S1B,S2D);
				s5=bigmaltiplay(stringsub(S1A,S1B),stringsub(S2D,S2C));
				s6=stringadd(s3,s4);
				s7=stringadd(s5,s6);
				s8=stringadd(s3.PadRight(2*b+s3.Length,'0')
					,s7.PadRight(b+s7.Length,'0'));
				s=stringadd(s8,s4);
			}
			else
			{
			    S1A=s1.Substring(0,a/2);
				S1B=s1.Remove(0,a/2);
				S2C=s2.Substring(0,b-a/2-a%2);
				S2D=s2.Remove(0,b-a/2-a%2);
				s3=bigmaltiplay(S1A,S2C);
				s4=bigmaltiplay(S1B,S2D);
				s5=bigmaltiplay(stringsub(S1A,S1B),stringsub(S2D,S2C));
				s6=stringadd(s3,s4);
				s7=stringadd(s5,s6);
				s8=stringadd(s3.PadRight((a/2+a%2)*2+s3.Length,'0')
					,s7.PadRight(a/2+a%2+s7.Length,'0'));
				s=stringadd(s8,s4);
			}
			
		}
		return s;
	}
	public static void Main()
	{
	    string s1,s2;
		for(int i=1;i<3;i++)
		{
			Console.WriteLine("请输入两个数:");
			s1=Console.ReadLine();
			s2=Console.ReadLine();
			Console.WriteLine(bigmaltiplay(s1,s2));
		}
	}
}