/* 

   CS 202, Fall 2007
   Homework#6, Problem 3

   Author: Harish Kumar

*/

// Implementation of multiplication of positive HugeInts by repeated addition.

// Fig. 11.22: Hugeint.h 
// HugeInt class definition.
#ifndef HUGEINT_H
#define HUGEINT_H

#include <iostream>
using std::ostream;

class HugeInt
{
   friend ostream &operator<<( ostream &, const HugeInt & );
   
public:
   HugeInt( long = 0 ); // conversion/default constructor
   HugeInt( const char * ); // conversion constructor

   // addition operator; HugeInt + HugeInt
   HugeInt operator+( const HugeInt & ) const;
   
   // addition operator; HugeInt + int
   HugeInt operator+( int ) const;            

   // addition operator; 
   // HugeInt + string that represents large integer value
   HugeInt operator+( const char * ) const;    

   // '>' operator; compares two HugeInt objects
   bool operator>(const HugeInt &operand2) const;

   // multiplication operator 
   HugeInt operator*(const HugeInt &N)const; 

private:
   short integer[ 30 ];
}; // end class HugeInt

#endif

/**************************************************************************
 * (C) Copyright 1992-2005 by Deitel & Associates, Inc. and               *
 * Pearson Education, Inc. All Rights Reserved.                           *
 *                                                                        *
 * DISCLAIMER: The authors and publisher of this book have used their     *
 * best efforts in preparing the book. These efforts include the          *
 * development, research, and testing of the theories and programs        *
 * to determine their effectiveness. The authors and publisher make       *
 * no warranty of any kind, expressed or implied, with regard to these    *
 * programs or to the documentation contained in these books. The authors *
 * and publisher shall not be liable in any event for incidental or       *
 * consequential damages in connection with, or arising out of, the       *
 * furnishing, performance, or use of these programs.                     *
 **************************************************************************/

/* 

   CS 202, Fall 2007
   Homework#6, Problem 3

   Author: Harish Kumar

*/

// Fig. 11.23: Hugeint.cpp 
// HugeInt member-function and friend-function definitions.
#include <cctype> // isdigit function prototype
using std::isdigit;

#include <cstring> // strlen function prototype
using std::strlen;

//#include "Hugeint.h" // HugeInt class definition

// default constructor; conversion constructor that converts
// a long integer into a HugeInt object
HugeInt::HugeInt( long value )
{
   // initialize array to zero
   for ( int i = 0; i <= 29; i++ )
      integer[ i ] = 0;   

   // place digits of argument into array 
   for ( int j = 29; value != 0 && j >= 0; j-- )
   {
      integer[ j ] = value % 10;
      value /= 10;
   } // end for
} // end HugeInt default/conversion constructor

// conversion constructor that converts a character string 
// representing a large integer into a HugeInt object
HugeInt::HugeInt( const char *string )
{
   // initialize array to zero
   for ( int i = 0; i <= 29; i++ )
      integer[ i ] = 0;

   // place digits of argument into array
   int length = strlen( string );

   for ( int j = 30 - length, k = 0; j <= 29; j++, k++ )

      if ( isdigit( string[ k ] ) )
         integer[ j ] = string[ k ] - '0';
} // end HugeInt conversion constructor

// addition operator; HugeInt + HugeInt
HugeInt HugeInt::operator+( const HugeInt &op2 ) const
{
   HugeInt temp; // temporary result
   int carry = 0;

   for ( int i = 29; i >= 0; i-- )
   {
      temp.integer[ i ] = 
         integer[ i ] + op2.integer[ i ] + carry;

      // determine whether to carry a 1
      if ( temp.integer[ i ] > 9 )
      {
         temp.integer[ i ] %= 10;  // reduce to 0-9
         carry = 1;
      } // end if
      else // no carry 
         carry = 0;
   } // end for

   return temp; // return copy of temporary object
} // end function operator+

// addition operator; HugeInt + int
HugeInt HugeInt::operator+( int op2 ) const
{ 
   // convert op2 to a HugeInt, then invoke 
   // operator+ for two HugeInt objects
   return *this + HugeInt( op2 ); 
} // end function operator+

// addition operator;
// HugeInt + string that represents large integer value
HugeInt HugeInt::operator+( const char *op2 ) const 
{ 
   // convert op2 to a HugeInt, then invoke 
   // operator+ for two HugeInt objects
   return *this + HugeInt( op2 ); 
} // end operator+

// overloaded > operator
bool HugeInt::operator>(const HugeInt &operand2) const
{
	for(int i=0; i<30 ;i++) // compare digits left to right
	{
		if( integer[i] != operand2.integer[i] ) 
			// return when digits unequal
			return (integer[i]>operand2.integer[i]); 
	}
	return false; // if both HugeInts are equal
} // end function operator>

// overloaded output operator
ostream& operator<<( ostream &output, const HugeInt &num )
{
   int i;

   for ( i = 0; ( num.integer[ i ] == 0 ) && ( i <= 29 ); i++ )
      ; // skip leading zeros

   if ( i == 30 )
      output << 0;
   else

      for ( ; i <= 29; i++ )
         output << num.integer[ i ];

   return output;
} // end function operator<<

// function operator* definition
HugeInt HugeInt::operator*(const HugeInt &N) const
{
		HugeInt I, P; //initialized to 0
		while (N>I)   //addition loop as given in the problem
		{ P = P + *this; I = I + 1; }
		return P;
} // end function operator*

/**************************************************************************
 * (C) Copyright 1992-2005 by Deitel & Associates, Inc. and               *
 * Pearson Education, Inc. All Rights Reserved.                           *
 *                                                                        *
 * DISCLAIMER: The authors and publisher of this book have used their     *
 * best efforts in preparing the book. These efforts include the          *
 * development, research, and testing of the theories and programs        *
 * to determine their effectiveness. The authors and publisher make       *
 * no warranty of any kind, expressed or implied, with regard to these    *
 * programs or to the documentation contained in these books. The authors *
 * and publisher shall not be liable in any event for incidental or       *
 * consequential damages in connection with, or arising out of, the       *
 * furnishing, performance, or use of these programs.                     *
 **************************************************************************/


/* 

   CS 202, Fall 2007
   Homework#6, Problem 3

   Author: Harish Kumar

*/

// 
// HugeInt test program.
#include <iostream>
using std::cout;
using std::endl;

//#include "Hugeint.h"

int main() //compute factorials using HugeInts as given in the problem
{
   HugeInt HugeNFactorial("1"), HugeN;
   for (int I=1; I<31; I++)
   { 
	   HugeN = HugeN + 1;
	   HugeNFactorial =  HugeNFactorial * HugeN ;                     
	   cout << HugeN << "! = " << HugeNFactorial << endl;
   }
   return 0;
} // end main

/* Program OUTPUT:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
22! = 1124000727777607680000
23! = 25852016738884976640000
24! = 620448401733239439360000
25! = 15511210043330985984000000
26! = 403291461126605635584000000
27! = 10888869450418352160768000000
28! = 304888344611713860501504000000
29! = 841761993739701954543616000000
30! = 252859812191058636308480000000



*/

/*
What is the largest factorial that can be computed exactly
	using the HugeInt class?  Why?**

ans) 28! is the largest as it needs 30 digits and appears to be the correct
value of 28*27!. 

Extra Credit: What happens when you reverse the order of
	the multiplication in the factorial driver program?  Why?**

ans) 

The program slows down and the results take much longer due to increase in the 
number of times the addition loop ( in operator* function) executes. For 
example to compute 12! the original loop adds 11! 12 times, but the new code 
adds 12 in the addition loop 39916800 (11!) times.  Thus, the run time is 
proportional to N!.
*/