// Compute the square root of a huge integer.
#include <iostream>
#include <iomanip>
using std::cin;
using std::cout;
using std::endl;

#include <ctime>
#include <cstring>

void generateNumber( int number[], int size );
void findSqrt( int number[], int sqrt[], int numberSize, int &sqrtSize );
void multiply( int multiplicand[], int multiplier[], int product[],
	           int multiplicandSize, int multiplierSize, int &productSize );
bool less( int number1[], int number2[], int number1Size, int number2Size );
void printResult( int number[], int sqrt[], int numberSize, int sqrtSize );
void verify( int number[], int sqrt[], int numberSize, int sqrtSize );
void increment( int number[], int &numberSize );
const int arraySize = 100;

// function main begins program execution
int main()
{
   srand( static_cast< int >( time(0) ) );
   int numberSize = 70 + rand() % 10; // the number of digits of number is numberSize + 1
   int number[ arraySize ] = { 0 }; // a huge positive integer in the way that

   generateNumber( number, numberSize );

   int sqrt[ arraySize ] = { 0 }; // the square root of number
   int sqrtSize = numberSize / 2; // the number of digits of sqrt is sqrtSize + 1

   findSqrt( number, sqrt, numberSize, sqrtSize );

   printResult( number, sqrt, numberSize, sqrtSize );

   verify( number, sqrt, numberSize, sqrtSize );

   system( "pause" );
} // end function main

// put a randomly generated positive integer into the array number,
// the number of digits is size + 1
void generateNumber( int number[], int size )
{
   for( int i = 0; i < size; i++ )
      number[ i ] = rand() % 10;
   number[ size ] = 1 + rand() % 9;
}

// if number1 < number2, retuen true; otherwise, return false
bool less( int number1[], int number2[], int number1Size, int number2Size )
{
	if( number1Size < number2Size )
		return true;
	if( number1Size > number2Size )
		return false;

	for( int i = number1Size-1; i >= 0; i-- )
	{
		if( number1[i] < number2[i] )
			return true;
		if( number1[i] > number2[i] )
			return false;
	}

	return false;
}

// put the square root of number into the array sqrt
void findSqrt( int number[], int sqrt[], int numberSize, int &sqrtSize )
{
	int c = 0;
	int buffer[ arraySize ] = {0} ;
	int bufferSize = arraySize;
	sqrtSize += 1;
	memset( sqrt, 0, sqrtSize*sizeof(int) );
	for( int i = sqrtSize-1; i >= 0; i-- )
	{
		do
		{
			memset(buffer,0,bufferSize*sizeof(int));
			sqrt[i]++;
			multiply( sqrt, sqrt, buffer, sqrtSize,sqrtSize,bufferSize );
		}
		while( less( buffer, number, bufferSize, numberSize ) );
		sqrtSize--;
		sqrt[i]--;
	}
	for( int i = sqrtSize-1; i >= 0 && sqrt[i] == 0; i-- )
		c++;
	sqrtSize -= c;
}

// put the product of multiplicand and multiplier into the array product
void multiply( int multiplicand[], int multiplier[], int product[],int multiplicandSize, int multiplierSize, int &productSize )
{
	int carry = 0, c = 0;
	memset(product, 0, productSize*sizeof(int));
 	for( int i = 0; i < multiplicandSize; i++ ) // 先乘
		for( int j = 0; j < multiplierSize; j++ )
			product[i+j] += multiplicand[i] * multiplier[j];

	for( int i = 0; i < multiplicandSize + multiplierSize; i++ ) // 進位
	{
		product[i] += carry;
		carry = product[i] / 10;
		product[i] %= 10;
	}

	for( int i = productSize-1; i >= 0 && product[i] == 0; i-- ) // 算位數
		c++;
	productSize -= c;
}



// print number and sqrt
void printResult( int number[], int sqrt[], int numberSize, int sqrtSize )
{
   cout << "The square root of\n\n";
   for( int i = numberSize-1; i >= 0; i-- )
      cout << number[ i ];

   cout << "\n\nis\n\n";
   for( int i = sqrtSize-1; i >= 0; i-- )
      cout << sqrt[ i ];
   cout << endl << endl;
}

// print the square of sqrt and the square of ( sqrt + 1 )
// if number is less than the square of sqrt, then print Error
// if the square of ( sqrt + 1 ) is less than number, then print Error
void verify( int number[], int sqrt[], int numberSize, int sqrtSize )
{
   for( int i = numberSize-1; i >= 0; i-- )
      cout << "-";
   cout << endl << endl;

   int buffer[ arraySize ] = { 0 };
   int bufferSize = numberSize;
   multiply( sqrt, sqrt, buffer, sqrtSize, sqrtSize, bufferSize );

   cout << "The square of\n\n";

   for( int i = sqrtSize-1; i >= 0; i-- )
      cout << sqrt[ i ];

   cout << "\n\nis\n\n";

   for( int i = bufferSize-1; i >= 0; i-- )
      cout << buffer[ i ];
   cout << endl << endl;

   if( less( number, buffer, numberSize, bufferSize ) )
      cout << "Error!\n\n";


   int copy[ arraySize ] = {0};
   int copySize = sqrtSize;
   for( int i = sqrtSize-1; i >= 0; i-- )
      copy[ i ] = sqrt[ i ];

   increment( copy, copySize );

   multiply( copy, copy, buffer, copySize, copySize, bufferSize );

   cout << "\nThe square of\n\n";

   for( int i = copySize-1; i >= 0; i-- )
      cout << copy[ i ];

   cout << "\n\nis\n\n";

   for( int i = bufferSize-1; i >= 0; i-- )
      cout << buffer[ i ];
   cout << endl << endl;

   if( less( buffer, number, bufferSize, numberSize ) )
      cout << "Error!\n\n";
}

// increment number by 1
void increment( int number[], int &numberSize )
{
   int term = 0;
   int i;
   while( number[ term ] == 9 )
      term++;

   for( i = 0; i < term; i++ )
      number[ i ] = 0;

   number[ term ]++;

   if( term > numberSize )
      numberSize = term;
}