biginteger.cpp

dot NET 下的大整数乘法

#include "StdAfx.h"
#include "BigInteger.h"

BigInteger::BigInteger(void)
{
	numbers=gcnew array<Int64>(1);
}

BigInteger::BigInteger(BigInteger^ another)
{
	*this=another;
}

BigInteger::BigInteger(String^ str)
{
	InitFromString(str);
}

BigInteger::BigInteger(array<Int64>^ num)
{
	numbers=gcnew array<Int64>(num->Length);
	Array::Copy(num, numbers, num->Length);
}

void BigInteger::InitFromString(System::String ^str)
{
	int lenth=str->Length;
	int i;
	numbers=gcnew array<Int64>(lenth);
	for (i=0; i<lenth; i++)
	{
		numbers[lenth-i-1]=Convert::ToInt64(str[i].ToString());
	}
}

String^ BigInteger::ToString()
{
	int lenth=numbers->Length;
	int i;
	String^ str;
	for (i=0; i<lenth; i++)
	{
		str+=numbers[lenth-i-1].ToString();
	}
	return str;
}

BigInteger^ BigInteger::operator +(BigInteger ^rhs)
{
	int newLenth=Math::Max(numbers->Length, rhs->numbers->Length)+1;
	array<Int64>^ newNumbers=gcnew array<Int64>(newLenth);
	int i;
	if (numbers->Length>rhs->numbers->Length)
	{
		for (i=0; i<rhs->numbers->Length; i++)
		{
			newNumbers[i]=numbers[i]+rhs->numbers[i];
		}
		for ( ; i<numbers->Length; i++)
		{
			newNumbers[i]=numbers[i];
		}
	}
	else
	{
		for (i=0; i<numbers->Length; i++)
		{
			newNumbers[i]=numbers[i]+rhs->numbers[i];
		}
		for ( ; i<rhs->numbers->Length; i++)
		{
			newNumbers[i]=rhs->numbers[i];
		}
	}
	return gcnew BigInteger(Tiaozheng(newNumbers));	
}

array<Int64>^ BigInteger::Tiaozheng(array<Int64>^ num)
{
	int i;
	Int64 t=0;
	int lenth=num->Length;
	for (i=0; i<lenth; i++)
	{
		num[i]+=t;
		t=num[i]/10;
		num[i]%=10;
	}
	int numberOfZeros=0;
	i=1;
	while(num[lenth-i]==0&&(lenth-i)>0)
	{
		i++;
		numberOfZeros++;
	}
	if (numberOfZeros==0)
	{
		return num;
	}
	array<Int64>^ newNum=gcnew array<Int64>(lenth-numberOfZeros);
	for (i=0; i<lenth-numberOfZeros; i++)
	{
		newNum[i]=num[i];
	}
	return newNum;
}

BigInteger^ BigInteger::operator *(BigInteger ^rhs)
{
	int t=numbers->Length+rhs->numbers->Length;
	int newLenth=1;
	while(newLenth<t)
	{
		newLenth<<=1;
	}
	array<CComplex>^ a;
	a=gcnew array<CComplex>(newLenth);
	array<CComplex>^ b;
	b=gcnew array<CComplex>(newLenth);
	array<CComplex>^ c;
	c=gcnew array<CComplex>(newLenth);
	int i;
	for (i=0; i<numbers->Length; i++)
	{
		a[i]=CComplex::FromReal(numbers[i]);
	}
	for (i=0; i<rhs->numbers->Length; i++)
	{
		b[i]=CComplex::FromReal(rhs->numbers[i]);
	}
	FFT(a, newLenth, 1);
	FFT(b, newLenth, 1);
	for (i=0; i<newLenth; i++)
	{
		c[i]=a[i]*b[i];
	}
	FFT(c, newLenth, -1);
	array<Int64>^ newNumbers=gcnew array<Int64>(newLenth);
	for (i=0; i<newLenth; i++)
	{
		newNumbers[i]=((int)(c[i].Re+0.5));
	}
	return gcnew BigInteger(Tiaozheng(newNumbers));
}

BigInteger^ BigInteger::operator += (BigInteger^ rhs)
{
	*this=this+rhs;
	return this;
}

BigInteger^ BigInteger::operator *= (BigInteger^ rhs)
{
	*this=this*rhs;
	return this;
}

BigInteger^ BigInteger::operator = (BigInteger^ rhs)
{
	if (this==rhs)
	{
		return this;
	}
	numbers=gcnew array<Int64>(rhs->numbers->Length);
	Array::Copy(rhs->numbers, numbers, numbers->Length);
	return this;
}

bool BigInteger::operator == (BigInteger^ rhs)
{
	if (numbers->Length!=rhs->numbers->Length)
	{
		return false;
	}
	int i;
	for (i=0; i<numbers->Length; i++)
	{
		if (numbers[i]!=rhs->numbers[i])
		{
			return false;
		}
	}
	return true;
}

bool BigInteger::operator != (BigInteger^ rhs)
{
	return !(*this==rhs);
}

BigInteger^ BigInteger::CommomMutiple(BigInteger^ rhs)
{
	int newLenth=numbers->Length+rhs->numbers->Length;	
	array<Int64>^ newNumbers=gcnew array<Int64>(newLenth);
	int i, j;
	for (i=0; i<newLenth; i++)
	{
		newNumbers[i]=0;
	}
	for (i=0; i<numbers->Length; i++)
	{
		for (j=0; j<rhs->numbers->Length; j++)
		{
			newNumbers[i+j]+=numbers[i]*rhs->numbers[j];
		}
	}
	return gcnew BigInteger(Tiaozheng(newNumbers));
}

void BigInteger::FFT(array<CComplex>^ numbers, int n, int sign)
/* numbers开始存放待计算的数据，最后存放计算后的数据
* n数据的长度，必须是2的整数次幂，如果不是请先补零，并且不要超过2的16次幂
* sign是计算的标号，sign=1时计算DFT, sign=-1时计算IDFT
*/
{
	int i, j, k, l, m, n1, n2;
	double c, c1, e, s, s1, t, tr, ti;
	CComplex temp;
	for (j=1, i=1; i<16; i++)
	{
		m=i;
		j=2*j;
		if (j==n)
		{
			break;
		}
	}
	n1=n-1;
	for (j=0, i=0; i<n1; i++)
	{
		if (i<j)
		{
			temp=numbers[j];
			numbers[j]=numbers[i];
			numbers[i]=temp;
		}
		k=n/2;
		while (k<(j+1))
		{
			j=j-k;
			k=k/2;
		}
		j=j+k;
	}
	n1=1;
	for (l=1; l<=m; l++)
	{
		n1=2*n1;
		n2=n1/2;
		e=Math::PI/n2;
		c=1.0;
		s=0.0;
		c1=Math::Cos(e);
		s1=-sign*Math::Sin(e);
		for (j=0; j<n2; j++)
		{
			for (i=j; i<n; i+=n1)
			{
				k=i+n2;
				tr=c*numbers[k].Re-s*numbers[k].Im;
				ti=c*numbers[k].Im+s*numbers[k].Re;
				numbers[k].Re=numbers[i].Re-tr;
				numbers[k].Im=numbers[i].Im-ti;
				numbers[i].Re=numbers[i].Re+tr;
				numbers[i].Im=numbers[i].Im+ti;
			}
			t=c;
			c=c*c1-s*s1;
			s=t*s1+s*c1;
		}
	}
	if (sign==-1)
	{
		for (i=0; i<n; i++)
		{
			numbers[i].Re=numbers[i].Re/n;
			numbers[i].Im=numbers[i].Im/n;
		}
	}

}