clongint.cpp

一个用来对非常大的数进行科学计算的程序库

#include "stdafx.h"
#include <afx.h>
#include <math.h>
#include "CLongInt.h"

//////////////////////////////////////////////////////////////
/*         Define some static and private members           */
//////////////////////////////////////////////////////////////
const char CLongInt::sCharSet[] = {'0', '1', '2', '3', '4', '5', '6'
,'7', '8', '9', '+', '-'};			   

//////////////////////////////////////////////////////////////
CLongInt::CLongInt()
{
	m_csInt = '0';
	m_bSign = 0;
}

//////////////////////////////////////////////////////////////
CLongInt::CLongInt(long nNum)
{
	if (nNum < 0)
    {
		nNum = -nNum;
		m_bSign = -1;
    }
	else if (nNum == 0) m_bSign = 0;
	else m_bSign = 1;
	
	m_csInt.Format("%ld", nNum);
}

//////////////////////////////////////////////////////////////
CLongInt::CLongInt(const char *lpszNumStr)
{
	m_csInt = ToRegularNumStr(lpszNumStr);
	
	if (m_csInt.IsEmpty())
		return;
	
	switch (m_csInt[0])
	{
	case '-':
		m_bSign = -1;
		m_csInt.Remove('-');
		break;
	case '0':
		m_bSign = 0;
		break;
	default:
		m_bSign = 1;
	}
}

//////////////////////////////////////////////////////////////
CLongInt::CLongInt(const CString & cs)
{
	m_csInt = ToRegularNumStr(LPCTSTR(cs));
	
	if (m_csInt.IsEmpty())
		return;
	
	switch (m_csInt[0])
	{
	case '-':
		m_bSign = -1;
		m_csInt.Remove('-');
		break;
	case '0':
		m_bSign = 0;
		break;
	default:
		m_bSign = 1;
	}
}

//////////////////////////////////////////////////////////////
CLongInt::CLongInt(const CLongInt & li)
{
	if (this != &li)
    {
		m_csInt = li.m_csInt;
		m_bSign = li.m_bSign;
    }
}

//////////////////////////////////////////////////////////////
CLongInt::~CLongInt()
{
	return;
}

//////////////////////////////////////////////////////////////
CLongInt & CLongInt::operator = (long nNum)
{
	CLongInt li(nNum);
	*this = li;
	return *this;
}

//////////////////////////////////////////////////////////////
CLongInt & CLongInt::operator = (const CLongInt & li)
{
	if (this != &li)
    {
		m_csInt = li.m_csInt;
		m_bSign = li.m_bSign;
    }
	return *this;
}

//////////////////////////////////////////////////////////////
CLongInt CLongInt::operator + (long nNum)       const
{
	if (nNum == 0)
		return *this;
	
	CLongInt li = nNum;
	return *this + li;
}

//////////////////////////////////////////////////////////////
CLongInt CLongInt::operator + (const CLongInt & li)     const
{
	if (li.m_bSign == 0)
		return *this;
	if (this -> m_bSign == 0)
		return li;
	
	CLongInt liEnd;
	CString cs1 = this -> m_csInt, cs2 = li.m_csInt;
	
	if ( (this -> m_bSign > 0 && li.m_bSign > 0)
		|| (this -> m_bSign < 0 && li.m_bSign < 0) )
    {
		int nSet0 = cs1.GetLength() - cs2.GetLength();
		CString csZero('0', abs(nSet0));
		
		if (nSet0 > 0)
			cs2 = csZero + cs2;
		else
			cs1 = csZero + cs1;
		
		csZero.Empty();
		
		const int iSecLen = 2;  // long  -2,147,483,648 to 2,147,483,647
		int icsLen = cs1.GetLength();
		int iSection = int(ceil(float(icsLen) / float(iSecLen)));
		int *piUp = new int [iSection + 1];  // Not use Index 0
		long iSecVal1, iSecVal2, iSecResult;
		CString csSecResult, csResult;
		
		//  sec 4  3  2  1
		//  idx 0 12 34 56
		//  cs1 1|12|34|56
		//  cs2 0|00|01|23
		
		for (int i = 1; i <= iSection; i++)
		{
			CString csSection;
			
			if (i == iSection && icsLen % iSecLen != 0)
				csSection = cs1.Left(icsLen % iSecLen);
			else
				csSection = cs1.Mid(icsLen - i * iSecLen, iSecLen);
			
			iSecVal1 = atol(csSection);
			
			if (i == iSection && icsLen % iSecLen != 0)
				csSection = cs2.Left(icsLen % iSecLen);
			else
				csSection = cs2.Mid(icsLen - i * iSecLen, iSecLen);
			
			iSecVal2 = atol(csSection);
			
			iSecResult = iSecVal1 + iSecVal2;
			
			if (iSecResult >= pow(10, iSecLen))
			{
				iSecResult -= long(pow(10, iSecLen));
				piUp[i] = 1;
			}
			else
				piUp[i] = 0;
			
			csSecResult.Format("%ld", iSecResult);
			CString csZero('0', iSecLen - csSecResult.GetLength());
			csSecResult = csZero + csSecResult;
			csZero.Empty();
			
			csResult = csSecResult + csResult;
			
			csSection.Empty();
		}
		
		if (piUp[iSection] != 1)
			csResult.TrimLeft('0');
		
		icsLen = csResult.GetLength();
		
		for (i = 1; i <= iSection - 1; i++)
			if (piUp[i] == 1)
				csResult.SetAt(icsLen - 1 - i * iSecLen, csResult[icsLen - 1 - i * iSecLen] + 1);
			
			if (piUp[iSection] == 1)
			{
				csResult = '1' + csResult;
				icsLen++;
			}
			
			delete []piUp;
			
			for (i = icsLen - 1; i >= 1; i--)
				if (csResult[i] > '9')
				{
					csResult.SetAt(i, csResult[i] - 10);
					csResult.SetAt(i - 1, csResult[i - 1] + 1);
				}
				
				if (csResult[0] > '9')
				{
					csResult.SetAt (0, csResult[0] - 10);
					csResult = '1' + csResult;
				}
				
				liEnd.m_csInt = csResult;
				
				if (this -> m_bSign < 0 && li.m_bSign < 0)
					liEnd.m_bSign = -1;
				else
					liEnd.m_bSign = 1;
	}
	else
    {
		if (*this < 0)
			return li - (-*this);
		else
			return *this - (-li);
    }
	
	return liEnd;
}

//////////////////////////////////////////////////////////////
//Friend member
CLongInt operator + (long n, const CLongInt & li)
{
	return li + n;
}

//////////////////////////////////////////////////////////////
CLongInt CLongInt::operator - (long nNum)       const
{
	if (nNum == 0)
		return *this;
	
	CLongInt li = nNum;
	return *this - li;
}

//////////////////////////////////////////////////////////////
CLongInt CLongInt::operator - (const CLongInt & li)     const
{
	CLongInt liEnd;
	
	if (*this == li)
    {
		liEnd = 0;
		return liEnd;
    }
	else if (li.m_bSign == 0)
		return *this;
	else if (this -> m_bSign == 0)
		return - li;
	
	// Two number have different m_bSign
	if (this -> m_bSign > 0 && li.m_bSign < 0)  // 1234 - (-0399)
		return *this + ( -li);
	else if (this -> m_bSign < 0 && li.m_bSign > 0)  // -1234 - 0399
		return - (- (*this) + li);
	
	// Two number have same m_bSign
	if (*this > li && li.m_bSign > 0)     // +Big -  +Small
    {
		//  sec 4  3  2  1
		//  idx 0 12 34 56
		//  cs1 1|12|34|56
		//  cs2 0|00|01|23
		CString cs1 = this -> m_csInt, cs2 = li.m_csInt;
		int nSet0 = cs1.GetLength() - cs2.GetLength();
		CString csZero('0', abs(nSet0));
		
		if (nSet0 > 0)
			cs2 = csZero + cs2;
		else
			cs1 = csZero + cs1;
		
		csZero.Empty();
		
		const int iSecLen = 2;  // long  -2,147,483,648 to 2,147,483,647
		int icsLen = cs1.GetLength();
		int iSection = int(ceil(float(icsLen) / float(iSecLen)));
		long *piDowm = new long [iSection + 1];  // Not use Index 0
		long iSecVal1, iSecVal2, iSecResult;
		CString csSecResult, csResult;
		
		for (int i = 1; i <= iSection; i++)
		{
			CString csSection;
			
			if (i == iSection && icsLen % iSecLen != 0)
				csSection = cs1.Left(icsLen % iSecLen);
			else
				csSection = cs1.Mid(icsLen - i * iSecLen, iSecLen);
			
			iSecVal1 = atol(csSection);
			
			if (i == iSection && icsLen % iSecLen != 0)
				csSection = cs2.Left(icsLen % iSecLen);
			else
				csSection = cs2.Mid(icsLen - i * iSecLen, iSecLen);
			
			iSecVal2 = atol(csSection);
			
			iSecResult = iSecVal1 - iSecVal2;
			
			if (iSecResult < 0)
			{
				iSecResult += long(pow(10, iSecLen));
				piDowm[i] = TRUE;
			}
			else
				piDowm[i] = FALSE;
			
			csSecResult.Format("%ld", iSecResult);
			CString csZero('0', iSecLen - csSecResult.GetLength());
			csSecResult = csZero + csSecResult;
			csZero.Empty();
			
			csResult = csSecResult + csResult;
			
			csSection.Empty();
		}
		
		icsLen = csResult.GetLength();
		
		for (i = 1; i <= iSection - 1; i++)
			if (piDowm[i] == 1)
				csResult.SetAt (icsLen - 1 - i * iSecLen, csResult[icsLen - 1 - i * iSecLen] - 1);
			
			delete []piDowm;
			
			for (i = icsLen - 1; i >= 1; i--)
				if (csResult[i] < '0')
				{
					csResult.SetAt (i, csResult[i] + 10);
					csResult.SetAt (i - 1, csResult[i - 1] - 1);
				}
				
				csResult.TrimLeft('0');
				
				liEnd.m_csInt = csResult;
				liEnd.m_bSign = 1;
    }
	else if (*this > li && li.m_bSign < 0)  // -0399 - (-1234)
		liEnd = -li - ( - (*this) );
	else if (*this < li && li.m_bSign > 0)  //  0399 - 1234
		liEnd = - (li - *this);
	else  // -1234 - (-0399)
		liEnd = - ( -(*this) - ( -li));
	
	return liEnd;
}

//////////////////////////////////////////////////////////////
//Friend member
CLongInt operator - (long n, const CLongInt & li)
{
	CLongInt li1 = n;
	return li1 - li;
}

//////////////////////////////////////////////////////////////
CLongInt CLongInt::operator - () const
{
	CLongInt li = *this;
	li.m_bSign = - li.m_bSign;
	return li;
}

//////////////////////////////////////////////////////////////
CLongInt CLongInt::operator * (long n)          const
{
	CLongInt li = n;
	return *this * li;
}

//////////////////////////////////////////////////////////////
CLongInt CLongInt::operator * (const CLongInt & li)     const
{
	CLongInt liEnd;
	if (this -> m_bSign * li.m_bSign == 0)
		return liEnd;
	
	CString cs1 = this -> m_csInt;
	CString cs2 = li.m_csInt;
	int len1 = cs1.GetLength(), len2 = cs2.GetLength();
	int iEndZero = 0;
	
	cs1.TrimRight('0');
	iEndZero += len1 - cs1.GetLength();
	cs2.TrimRight('0');
	iEndZero += len2 - cs2.GetLength();
	
	if (cs1.GetLength() - cs2.GetLength() < 0)
    {
		CString csTemp = cs1;
		cs1 = cs2;
		cs2 = csTemp;
    }
	
	// Now cs1 is longer than cs2
	
	const int iSecLen = 2;  // long  -2,147,483,648 to 2,147,483,647
	int icsLen1 = cs1.GetLength(), icsLen2 = cs2.GetLength();
	int iSection = int(ceil(float(icsLen1) / float(iSecLen)));
	long *piUp = new long [iSection + 1];  // Not use Index 0
	long iSecVal1, iSecResult;
	CString csSecResult, csResult;
	
	for (int i = icsLen2 - 1; i >= 0; i--)
	{
		if (cs2[i] == '0')
			continue;
		for (int sec = 1; sec <= iSection; sec++)
		{
			CString csSection;
			
			if (sec == iSection && icsLen1 % iSecLen != 0)
				csSection = cs1.Left(icsLen1 % iSecLen);
			else
				csSection = cs1.Mid(icsLen1 - sec * iSecLen, iSecLen);
			
			iSecVal1 = atol(csSection);
			iSecResult = iSecVal1 * (cs2[i] - '0');
			
			if (iSecResult >= pow(10, iSecLen))
			{
				piUp[sec] = long(iSecResult / pow(10, iSecLen));
				iSecResult = iSecResult % long(pow(10, iSecLen));
			}
			else
				piUp[sec] = 0;
			
			csSecResult.Format("%ld", iSecResult);
			CString csZero('0', iSecLen - csSecResult.GetLength());
			csSecResult = csZero + csSecResult;
			csZero.Empty();			
		
			csResult = csSecResult + csResult;
			csSection.Empty();
		}
		
		for (int j = 1; j <= iSection - 1; j++)
			csResult.SetAt (csResult.GetLength() - 1 - j * iSecLen, csResult[csResult.GetLength() - 1 - j * iSecLen] + char(piUp[j]));
		
		if (piUp[iSection] > 0)
			csResult = char(piUp[iSection] + '0') + csResult;
		
		for (j = csResult.GetLength() - 1; j >= 1; j--)
		{
			if (csResult[j] > '9')
			{
				csResult.SetAt (j, csResult[j] - 10);
				csResult.SetAt (j - 1, csResult[j - 1] + 1);
			}
		}
		
		if (csResult[0] > '9')
		{
			csResult.SetAt (0, csResult[0] - 10);
			csResult = '1' + csResult;
		}
		
		CString csZero('0', icsLen2 - 1 - i);