hugenumber.cpp

一个较完备的HugeNumber类

	else
		pN = 1;

	int floatMargin = huge.size - huge.floatPosition;
	int sizeA = floatMargin + floatPosition + precision;
	int sizeB = huge.size;
	int floatPositionA = floatMargin + floatPosition;
	int *a = new int [ sizeA + 1 ];
	int *b = new int [ huge.size + 1 ];

	int rSize, sizeR, beginMargin = 0;
	if ( floatPositionA >= sizeB )
		rSize = sizeA - huge.size + 1;
	else
	{
		rSize = 1 + precision;
		beginMargin = sizeB - floatPositionA;
	}
	
	sizeR = rSize;
	int *result = new int [ rSize + 1 ];

	//init result[], for each i result[ i ] == 0
	init( result, rSize + 1 );

	//copy the first number to a[]
	int i;
	for ( i = 1; i <= sizeA; i ++ )
		if ( i <= size )
			a[ i ] = hugeNumber[ i ];
		else
			a[ i ] = 0;

	//copy the second number to b[]
	for ( i = 1; i <= huge.size; i ++ )
		b[ i ] = huge.hugeNumber[ i ]; 

	int sizeTempA = sizeB + 1;

	int *tempA = new int [ sizeTempA + 1 ];
	//init tempA, for each tempA[ i ] == 0
	init( tempA, sizeTempA + 1 );
	//copy a[] to tempA[]
	copy( tempA + 2, a + 1, sizeB );

	//compute the result
	for ( int indexA = sizeB; indexA <= sizeA; indexA ++ )
	{
		int indexR = indexA - sizeB + 1 + beginMargin;
		
		result[ indexR ] = findAppropriate( tempA, b, sizeB );

		if ( indexA >= size && isZero( tempA + 1, sizeTempA ) )
		{
			sizeR = indexR;
			break;
		}
		
		if ( indexA != sizeA )
			moveLeftAndValue( tempA + 1, sizeTempA, a[ indexA + 1 ] );
	}

	int margin = 0;
	int tmp = floatPositionA - sizeB + 1;
	int rFloatPosition = ( tmp > 0 ? tmp : 1 );

	if ( result[ 1 ] == 0 && rFloatPosition != 1 )
	{
		margin = 1;
		sizeR --;
		rFloatPosition --;
	}

	HugeNumber temp( result + 1 + margin, sizeR, rFloatPosition, pN, precision );
	*this = temp;
	delete []a;
	delete []b;
	delete []result;

	return *this;
}

void HugeNumber::init( int a[], int size )
{
	for ( int i = 0; i < size; i ++ )
		a[ i ] = 0;
}

void HugeNumber::copy( int a[], int b[], int size )
{
	for ( int i = 0; i < size; i ++ )
		a[ i ] = b[ i ];
}

int HugeNumber::findAppropriate( int a[], int b[], int size )
{
	int down = 0;
	int *result = new int [ size + 2 ];
	int counter = 0;

	//init result-----result[] = { 0 }
	init( result, size + 2 );

	
	while ( true ) // while result is bigger than 0
	{
		down = 0;
		for ( int i = size; i >= 1; i -- )
		{
			result[ i + 1 ] = a[ i + 1 ] - b[ i ] - down;
			if ( result[ i + 1 ] < 0 )
			{
				down = 1;
				result[ i + 1 ] += 10;
			}
			else
				down = 0;
		}
		
		result[ 1 ] = a[ 1 ] - down;
		if ( result[ 1 ] < 0 )    // if result is smaller than 0, break;
			break;

		copy( a, result, size + 2 );
		counter ++;
	}

	delete []result;

	return counter;
}

bool HugeNumber::isZero( int a[], int size )
{
	for ( int i = 0; i < size; i ++ )
		if ( a[ i ] != 0 )
			return false;

	return true;
}

void HugeNumber::moveLeftAndValue( int a[], int size, int item )
{
	a[ 0 ] = 0;

	for ( int i = 1; i < size; i ++ )
		a[ i - 1 ] = a[ i ];

	a[ size - 1 ] = item;
}

int HugeNumber::factorial()
{
	if ( floatPosition != size )
		return -1;

	if ( hugeNumber[ 0 ] == 1 )
		return -2;     // the operand is a negtive

	int pN = 0;
	int n = convertToInt( hugeNumber, size );

	//--------------------testing------------------
	//cout << n << endl;
	//---------------------------------------------

	const int maxSize = 100000;
	int *result = new int [ maxSize ];

	int begin = maxSize - 1, upLimit = 100000;

	//init reslut, make sure that for each result[ i ] == 0, reslut[ maxSize ] == 1 
	init( result, maxSize );
	result[ maxSize - 1 ] = 1;

	//compute the n!
	for ( int each = 2; each <= n; each ++ )
	{
		int up = 0;
		for ( int i = maxSize - 1; i >= begin; i -- )
		{
			result[ i ] = result[ i ] * each + up;

			if ( result[ i ] > upLimit )
			{
				up = result[ i ] / upLimit;
				result[ i ] %= upLimit;

				if ( i == begin )
					begin --;
			}
			else
				up = 0;
		}
	}

	/*
	cout << result[ begin ];
	for ( int index = begin + 1; index < maxSize; index ++ )
		cout << setw( 5 ) << setfill( '0' ) << result[ index ];

	cout << endl;
	*/
	int firstLen = findHowMany( result[ begin ] );
	int size_ = firstLen + 5 * ( maxSize - 1 - begin );
	int *tempRes = new int [ size_ ];

	int index_ = -1;
	int t = result[ begin ];
	for ( int ii = firstLen -1; ii >= 0; ii -- )
	{
		tempRes[ ii ] = t % 10;
		t /= 10;
	}
	
	index_ = firstLen - 1;
	int sta[ 5 ];
	for ( int s = begin + 1; s < maxSize; s ++ )
	{
		t = result[ s ];
		int ss;
		for ( ss = 4; ss >= 0; ss -- )
		{
			sta[ ss ] = t % 10;
			t /= 10;
		}
		for ( ss = 0; ss < 5; ss ++ )
			tempRes[ ++ index_ ] = sta[ ss ];
	}
	
	HugeNumber tNumber( tempRes, size_, size_, pN, precision );
	*this = tNumber;

	delete [] tempRes;
	delete [] result;
	return 0;
}

int HugeNumber::operator ^= ( const HugeNumber & huge )
{
	if ( huge.floatPosition != huge.size )  //if huge---the second operand is not an integer
		return -1;

	if ( huge.size > 5 )   //the second operand is too big, the program can't solve it
		return 1;

	int temp = convertToInt( huge.hugeNumber, huge.size );

	int pN = 0;
	if ( hugeNumber[ 0 ] == 0 )
			pN = 0;
		else if ( temp % 2 == 0 )
			pN = 0;
		else
			pN = 1;

	/* 
	 * if the first operand is less than 99999,
	 * we can convert it to an integer, 
	 * and it can be faster
	 */
	if ( size < 5 )   
	{
		int tempA = convertToInt( hugeNumber, size );
		const int SIZE = 100000;
		int *result = new int [ SIZE + 1 ];

		init( result, SIZE + 1);
		int begin = square( tempA, temp, result, SIZE );

		int firstLen = findHowMany( result[ begin ] );

		int resSize = firstLen + 5 * ( SIZE - begin ); 
		int *res = new int[ resSize ], sta[ 5 ];

		int index, t = result[ begin ];
		for ( index = firstLen - 1; index >= 0; index -- )
		{
			res[ index ] = t % 10;
			t /= 10;
		}
		int index_ = firstLen - 1;

		for ( index = begin + 1; index <= SIZE; index ++ )
		{
			t = result[ index ];
			int i;
			for ( i = 4; i >= 0; i -- )
			{
				sta[ i ] = t % 10;
				t /= 10;
			}

			for ( i = 0; i < 5; i ++ )
				res[ ++ index_ ] = sta[ i ];
		}
		 
		HugeNumber _temp( res, resSize, resSize - ( size - floatPosition ) * temp, pN, precision );

		*this = _temp;
		delete []res;
		delete []result;
	}
	/**
	 * if the first operand is more than 99999
	 * we have to deal it in a less efficient way
	 */
	else   
	{
		if ( temp != 0 )
		{
			HugeNumber temp_;
			temp_ = *this;
			for ( int i = 1; i < temp; i ++ )
				(*this) *= temp_;
		}
		else  //you know x^0 == 1
		{
			int a[] = { 1 };
			HugeNumber temp__( a, 1, 1, pN, precision );
			*this = temp__;
		}
	}

	return 0;
}

int HugeNumber::convertToInt( int a[], int n )
{
	int result = 0, ten = 1;
	for ( int i = n; i >= 1; i -- )
	{
		result += a[ i ] * ten;
		ten *= 10;
	}

	return result;
}

int HugeNumber::findHowMany( int x )
{
	if ( x == 0 )
		return 1;

	int i, t;
	for ( i = 0, t = 1; x >= t; ++ i, t *= 10 );

	return i;
}

void HugeNumber::print( int a[], int size )
{
	for ( int i = 1; i <= size; i ++ )
		cout << a[ i ];
	cout << endl;
}

int HugeNumber::square( int x, int y, int result[], const int size )
{
	int begin = size,
		upLimit = 100000;
	result[ size ] = 1;

	for ( int i = 0; i < y; i ++ )
	{
		int up = 0;
		for ( int j = size; j >= begin; j -- )
		{
			result[ j ] = result[ j ] * x + up;

			if ( result[ j ] >= upLimit )
			{
				up = result[ j ] / upLimit;
				result[ j ] %= upLimit;

				if ( j == begin )
					begin --;
			}
			else
				up = 0;

		}
	}

	return begin;
}