CPosBigInt10
[ Home ] [ Up ]

//  CPosBigInt10.cpp
//  03/01/2004
//  Author: AOU


/*
Implement very long positive integers and 
simple operations associated with them

a="12000000000001111111111113"
b="62222222222222222222222222222222222223"
c = a+b
*/

//////////////////////////////////////////////////////////////////////
// include files
//////////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>


//////////////////////////////////////////////////////////////////////
// constants
//////////////////////////////////////////////////////////////////////
const int MAX_DIGITS = 50;
const int TEST_COUNT = 20;

const char *TEST_DATA[] =
  {
  "0", "1", "12", "123", "1234", "123450", "1234506", "12345067",
  "123450670", "1234506708", "1234506708", "Hello", "PSU",
  "9", "99", "999", "9999", "99999", "999999", "9999999"
  "10", "200", "3000", "40000", "500000", "6000000", "70000000",
  "800000000", "9000000000", "1090000000000", "11900000000000",
  "129000000000000", "1390000000000000", "14900000000000000"
  };

const int TEST_DATA_COUNT = sizeof(TEST_DATA)/sizeof(TEST_DATA[0]);


//////////////////////////////////////////////////////////////////////
// class CPosBigInt
//////////////////////////////////////////////////////////////////////
class CPosBigInt
  {
  private:
    char _digits[MAX_DIGITS];
    void initialize(void);
  public:
    CPosBigInt(void);
    void display(void);
    CPosBigInt(char d[]);               // 2004.01.28
    CPosBigInt(char ch);                // p02 A:2004.01.30, P:2004.02.11
    void displayMinimized(void);        // p02 A:2004.01.30, P:2004.02.11
    bool shiftLeft(void);               // 2004.02.02
    friend void add(CPosBigInt x, CPosBigInt y, CPosBigInt &z); // 2004.02.09

    void displayScientific(void);       // p03 A:2004.02.11

    CPosBigInt(short int x);            // 2004.02.16
    // [SHRT_MIN, SHRT_MAX] = [-32767,32767]

    CPosBigInt(unsigned short int x);   // 2004.02.16
    // [0, USHRT_MAX] = [0, 65535]

    CPosBigInt(long int x);             // 2004.02.16
    // [LONG_MIN, LONG_MAX] = [-2147483647, 2147483647]

    CPosBigInt(unsigned long int x);    // 2004.02.16
    // [0, ULONG_MAX] = [0, 4294967295]


    void displayWithSeparatorForThousands(void);

    friend ostream & operator << (ostream &bob, const CPosBigInt &bi); //2004.02.23
    CPosBigInt(const CPosBigInt &bi); //2004.02.23
    friend bool isEqual(const CPosBigInt &bi1, const CPosBigInt &bi2); //2004.02.23

    bool isEqual(const CPosBigInt &bi2);      //2004.02.25
    bool operator ==(const CPosBigInt &bi2);  //2004.02.25

    bool operator < (const CPosBigInt &bi2);  //p06 A:2004.02.16, P:2004.03.03



  // void displayRev(void);              //
  //wish list
  //  shiftRight    Matt
  //  subtract (-)  Chad
  //  multiply (*)  Brian
  //  divide (/)    Grant
  //  input >>      Alex
  //  negate        Tony1
  //  square root   Aifu
  //  array average Bill
  //  factorial     Christine
  //  output <<     Tony2
  //  sort          Yeh
  //  construct from short, unsigned short, long, unsigned long

  };

//////////////////////////////////////////////////////////////////////
// friend functions prototypes
//////////////////////////////////////////////////////////////////////
void add(CPosBigInt x, CPosBigInt y, CPosBigInt &z);


//////////////////////////////////////////////////////////////////////
// driver prototypes
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Constructor_Str(void);
void driver_CPosBigInt_Constructor_Rand(void);
void driver_CPosBigInt_displayMinimized(void);
void driver_CPosBigInt_shiftLeft(void);
void driver_CPosBigInt_Constructor_RandZ(void);
void driver_CPosBigInt_add(void);
void driver_CPosBigInt_displayScientific(void);
void driver_CPosBigInt_Constructor_ShortInt(void);
void driver_CPosBigInt_Constructor_UnsignedShortInt(void);
void driver_CPosBigInt_Constructor_LongInt(void);
void driver_CPosBigInt_Constructor_UnsignedLongInt(void);
void driver_CPosBigInt_displayWithSeparatorForThousands(void);
void driver_CPosBigInt_OperatorInsertion(void);
void driver_CPosBigInt_ConstructorCopy(void);
void driver_CPosBigInt_isEqualFriend(void);
void driver_CPosBigInt_isEqual(void);
void driver_CPosBigInt_Operator_isEqual(void);

void driver_CPosBigInt_Operator_isLessThan(void);


//////////////////////////////////////////////////////////////////////
// void main(void)
//////////////////////////////////////////////////////////////////////
void main(void)
  {
  //driver_CPosBigInt_Constructor_Str();

  //driver_CPosBigInt_Constructor_Rand();
  //driver_CPosBigInt_displayMinimized();
  
  //driver_CPosBigInt_shiftLeft();

  //driver_CPosBigInt_Constructor_RandZ();
  
  //driver_CPosBigInt_add();
  
  //driver_CPosBigInt_displayScientific();
  
  //driver_CPosBigInt_Constructor_ShortInt();
  //driver_CPosBigInt_Constructor_UnsignedShortInt();
  //driver_CPosBigInt_Constructor_LongInt();
  //driver_CPosBigInt_Constructor_UnsignedLongInt();
  
  //driver_CPosBigInt_displayWithSeparatorForThousands();

  //driver_CPosBigInt_OperatorInsertion();
  //driver_CPosBigInt_ConstructorCopy();
  //driver_CPosBigInt_isEqualFriend();

  //driver_CPosBigInt_isEqual();
  //driver_CPosBigInt_Operator_isEqual();
  
  //driver_CPosBigInt_Operator_isLessThan();
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Operator_isLessThan(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Operator_isLessThan(void)
  {
  cout << "-------------------------------------\n";
  cout << "driver_CPosBigInt_Operator_isLessThan\n";
  cout << "-------------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('d');
    cout << "a=" << a;
    CPosBigInt b(a);
    cout << "b=" << b;
    CPosBigInt c('d');
    cout << "c=" << c;

    if (a < b)
      cout << "a is less than b\n";
    else
      cout << "a is NOT less than b\n";

    if (a < c)
      cout << "a is less than c\n";
    else
      cout << "a is NOT less than c\n";

    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::operator < (const CPosBigInt &bi2)
//////////////////////////////////////////////////////////////////////
bool CPosBigInt::operator <(const CPosBigInt &bi2)
  {
  cout << "Missing code\n";
  return false;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Operator_isEqual(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Operator_isEqual(void)
  {
  cout << "----------------------------------\n";
  cout << "driver_CPosBigInt_Operator_isEqual\n";
  cout << "----------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('d');
    cout << "a=" << a;
    CPosBigInt b(a);
    cout << "b=" << b;
    CPosBigInt c('d');
    cout << "c=" << c;

    if (a.operator == (b))
      cout << "a is equal to b\n";
    else
      cout << "a is NOT equal to b\n";

    if (a == b)
      cout << "a is equal to b\n";
    else
      cout << "a is NOT equal to b\n";

    if (a == c)
      cout << "a is equal to c\n";
    else
      cout << "a is NOT equal to c\n";

    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::operator ==(const CPosBigInt &bi2)
//////////////////////////////////////////////////////////////////////
bool CPosBigInt::operator ==(const CPosBigInt &bi2)
  {
  for (int i=0; i<MAX_DIGITS; i++)
    if (this->_digits[i] != bi2._digits[i])
      return false;

  return true;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_isEqual(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_isEqual(void)
  {
  cout << "---------------------------------\n";
  cout << "driver_CPosBigInt_isEqual\n";
  cout << "---------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('d');
    cout << "a=" << a;
    CPosBigInt b(a);
    cout << "b=" << b;
    CPosBigInt c('d');
    cout << "c=" << c;

    if (a.isEqual(b))
      cout << "a is equal to b\n";
    else
      cout << "a is NOT equal to b\n";

    if (a.isEqual(c))
      cout << "a is equal to c\n";
    else
      cout << "a is NOT equal to c\n";

    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::isEqual(const CPosBigInt &bi2)
//////////////////////////////////////////////////////////////////////
bool CPosBigInt::isEqual(const CPosBigInt &bi2)
  {
  for (int i=0; i<MAX_DIGITS; i++)
    if (this->_digits[i] != bi2._digits[i])
      return false;

  return true;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_isEqualFriend(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_isEqualFriend(void)
  {
  cout << "---------------------------------\n";
  cout << "driver_CPosBigInt_isEqualFriend\n";
  cout << "---------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('d');
    cout << "a=" << a;
    CPosBigInt b(a);
    cout << "b=" << b;
    CPosBigInt c('d');
    cout << "c=" << c;

    if (isEqual(a, b))
      cout << "a is equal to b\n";
    else
      cout << "a is NOT equal to b\n";

    if (isEqual(a, c))
      cout << "a is equal to c\n";
    else
      cout << "a is NOT equal to c\n";

    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// bool isEqual(const CPosBigInt &bi1, const CPosBigInt &bi2)
//////////////////////////////////////////////////////////////////////
bool isEqual(const CPosBigInt &bi1, const CPosBigInt &bi2)
  {
  for (int i=0; i<MAX_DIGITS; i++)
    if (bi1._digits[i] != bi2._digits[i])
      return false;

  return true;
  
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_ConstructorCopy(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_ConstructorCopy(void)
  {
  cout << "---------------------------------\n";
  cout << "driver_CPosBigInt_ConstructorCopy\n";
  cout << "---------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('d');
    cout << "a=" << a;
    CPosBigInt b(a);
    cout << "b=" << b;

    cout << "----------------------------------------------------\n";
    }
  }



//////////////////////////////////////////////////////////////////////
// CPosBigInt::CPosBigInt(const CPosBigInt &bi)
//////////////////////////////////////////////////////////////////////
CPosBigInt::CPosBigInt(const CPosBigInt &bi)
  {
  for (int i=0; i<MAX_DIGITS; i++)
    this->_digits[i] = bi._digits[i];
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_OperatorInsertion(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_OperatorInsertion(void)
  {
  cout << "-----------------------------------\n";
  cout << "driver_CPosBigInt_OperatorInsertion\n";
  cout << "-----------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('d');
    cout << "a="; a.display();
    cout << "a=" << a;
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// ostream & operator << (ostream &bob, const CPosBigInt &bi)
//////////////////////////////////////////////////////////////////////
ostream & operator << (ostream &john, const CPosBigInt &bi)
  {
  for (int i=0; i<MAX_DIGITS; i++)
    john << bi._digits[i];

  john << endl;
  
  return john;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_displayWithSeparatorForThousands(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_displayWithSeparatorForThousands(void)
  {
  cout << "--------------------------------------------------\n";
  cout << "driver_CPosBigInt_displayWithSeparatorForThousands\n";
  cout << "--------------------------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('d');
    cout << "a="; a.display();
    cout << "a="; a.displayMinimized();
    cout << "a="; a.displayWithSeparatorForThousands();
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// void CPosBigInt::displayWithSeparatorForThousands(void)
//////////////////////////////////////////////////////////////////////
/*
Purpose: Display big integer with Separator For Thousands
Example:
  000 =>                 0
  123 =>               123
  1234 =>            1,234
  23456789 =>   23,456,789
  123456789 => 123,456,789

Obs0: Seperate each three digits with a comma
Obs1: Check the size and do accordingly
Obs2: Determine the digits to be displayed before first comma
Obs3: Display without any temporary holding variable
Obs4: Display with some temporary holding variable
Obs5: Process digits from left to right if using Obs3
Obs6: Process digits from  right to left if using Obs4
Obs7: if we process from right to left we have to use temp var
Obs8: if we process from left to right we do not have to use temp var

Algorithm0:
  Determine the number of leadingZeros
  digitCount = MAX_DIGITS-leadingZeros
  digitsBeforeComma = digitCount%3
  i = leadingZeros
  while digitsBeforeComma > 0
    display digit[i]
    i++
    digitsBeforeComma--
    end while

  digitsPrinted=0
  while i<MAX_DIGITS
    if digitsPrinted = 0 then
      display ','
    diplay digit[i]
    digitsPrinted++
      end if
    end while

Algorithm1:
  Determine the number of leadingZeros
  digitCount = MAX_DIGITS-leadingZeros

  i = leadingZeros
  while i<MAX_DIGITS
    diplay digits[i]
    i++
    if i<MAX_DIGITS && (MAX_DIGITS-i)%3 = 0 then
      display ','
    end while



*/
void CPosBigInt::displayWithSeparatorForThousands(void)
  {
  int leadingZeros = MAX_DIGITS-1; 

  for (int i=0; i<=MAX_DIGITS-2; i++)
    {
    if (_digits[i] != '0')
      {
      leadingZeros = i;
      break;
      }
    }
  
  i = leadingZeros;
  while (i<MAX_DIGITS)
    {
    cout << _digits[i];
    i++;
    if ((i<MAX_DIGITS) && (MAX_DIGITS-i)%3 == 0)
      cout << ',';
    }

  cout << endl;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Constructor_UnsignedLongInt(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Constructor_UnsignedLongInt(void)
  {
  cout << "---------------------------------------------\n";
  cout << "driver_CPosBigInt_Constructor_UnsignedLongInt\n";
  cout << "---------------------------------------------\n";

  unsigned long int x;
  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    x = rand()%ULONG_MAX;
    x = 2*x;
    x = x*x;

    CPosBigInt a(x);
    cout << "After CPosBigInt a(" << x << ");\n";
    cout << "a="; a.display();

    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// CPosBigInt::CPosBigInt(unsigned long int x)
//////////////////////////////////////////////////////////////////////
/*
Purpose: Construct a big integer from a unsigned long integer
Example: CPosBigInt a(123) => a="000123"
Algorithm0:
  initialize
  get the last digit from x and put it in d
  put d in the last position of digits[]
  continue the same while going to the left
  until no more digits in x

Algorithm1:
  initialize
  while x > 0
    d = x%10
    if d <> 0 then 
      put d in digits[] at the proper place
    x = x/10
  
Algorithm2:
  initialize
  p = MAX_DIGITS-1

  while x > 0
    d = x%10
    if d <> 0 then 
      convert and put d in digits[] at the proper(p) place

    x = x/10
    p--
    end while
  
*/
CPosBigInt::CPosBigInt(unsigned long int x)
  {
  initialize();
  int p = MAX_DIGITS-1;

  while (x > 0)
    {
    int d = x%10;
    if (d != 0) 
      _digits[p] = '0' + d;

    x = x/10;
    p--;
    }
  
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Constructor_LongInt(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Constructor_LongInt(void)
  {
  cout << "-------------------------------------\n";
  cout << "driver_CPosBigInt_Constructor_LongInt\n";
  cout << "-------------------------------------\n";

  long int x;
  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    x = rand()%LONG_MAX;
    x = x * x;

    CPosBigInt a(x);
    cout << "After CPosBigInt a(" << x << ");\n";
    cout << "a="; a.display();

    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// CPosBigInt::CPosBigInt(long int x)
//////////////////////////////////////////////////////////////////////
/*
Purpose: Construct a big integer from a long integer
Example: CPosBigInt a(123) => a="000123"
Algorithm0:
  initialize
  get the last digit from x and put it in d
  put d in the last position of digits[]
  continue the same while going to the left
  until no more digits in x

Algorithm1:
  initialize
  while x > 0
    d = x%10
    if d <> 0 then 
      put d in digits[] at the proper place
    x = x/10
  
Algorithm2:
  initialize
  p = MAX_DIGITS-1

  while x > 0
    d = x%10
    if d <> 0 then 
      convert and put d in digits[] at the proper(p) place

    x = x/10
    p--
    end while
  
*/
CPosBigInt::CPosBigInt(long int x)
  {
  initialize();
  int p = MAX_DIGITS-1;

  while (x > 0)
    {
    int d = x%10;
    if (d != 0) 
      _digits[p] = '0' + d;

    x = x/10;
    p--;
    }
  
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Constructor_UnsignedShortInt(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Constructor_UnsignedShortInt(void)
  {
  cout << "----------------------------------------------\n";
  cout << "driver_CPosBigInt_Constructor_UnsignedShortInt\n";
  cout << "----------------------------------------------\n";

  unsigned short int x;
  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    x = rand()%USHRT_MAX;
    x = 2*x;

    CPosBigInt a(x);
    cout << "After CPosBigInt a(" << x << ");\n";
    cout << "a="; a.display();

    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// CPosBigInt::CPosBigInt(unsigned short int x)
//////////////////////////////////////////////////////////////////////
/*
Purpose: Construct a big integer from a short unsigned integer
Example: CPosBigInt a(123) => a="000123"
Algorithm0:
  initialize
  get the last digit from x and put it in d
  put d in the last position of digits[]
  continue the same while going to the left
  until no more digits in x

Algorithm1:
  initialize
  while x > 0
    d = x%10
    if d <> 0 then 
      put d in digits[] at the proper place
    x = x/10
  
Algorithm2:
  initialize
  p = MAX_DIGITS-1

  while x > 0
    d = x%10
    if d <> 0 then 
      convert and put d in digits[] at the proper(p) place

    x = x/10
    p--
    end while
  
*/
CPosBigInt::CPosBigInt(unsigned short int x)
  {
  initialize();
  int p = MAX_DIGITS-1;

  while (x > 0)
    {
    int d = x%10;
    if (d != 0) 
      _digits[p] = '0' + d;

    x = x/10;
    p--;
    }
  
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Constructor_ShortInt(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Constructor_ShortInt(void)
  {
  cout << "--------------------------------------\n";
  cout << "driver_CPosBigInt_Constructor_ShortInt\n";
  cout << "--------------------------------------\n";

  short int x;
  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    x = rand()%SHRT_MAX;
    CPosBigInt a(x);
    cout << "After CPosBigInt a(" << x << ");\n";
    cout << "a="; a.display();

    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// CPosBigInt::CPosBigInt(short int x)
//////////////////////////////////////////////////////////////////////
/*
Purpose: Construct a big integer from a short integer
Example: CPosBigInt a(123) => a="000123"
Algorithm0:
  initialize
  get the last digit from x and put it in d
  put d in the last position of digits[]
  continue the same while going to the left
  until no more digits in x

Algorithm1:
  initialize
  while x > 0
    d = x%10
    if d <> 0 then 
      put d in digits[] at the proper place
    x = x/10
  
Algorithm2:
  initialize
  p = MAX_DIGITS-1

  while x > 0
    d = x%10
    if d <> 0 then 
      convert and put d in digits[] at the proper(p) place

    x = x/10
    p--
    end while
  
*/
CPosBigInt::CPosBigInt(short int x)
  {
  initialize();
  int p = MAX_DIGITS-1;

  while (x > 0)
    {
    int d = x%10;
    if (d != 0) 
      _digits[p] = '0' + d;

    x = x/10;
    p--;
    }
  
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_displayScientific(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_displayScientific(void)
  {
  cout << "-----------------------------------\n";
  cout << "driver_CPosBigInt_displayScientific\n";
  cout << "-----------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt x('d');

    cout << "x="; x.display();

    cout << "x="; x.displayScientific();

    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// void CPosBigInt::displayScientific(void)
//////////////////////////////////////////////////////////////////////
/*
Purpose:  Display big integers in scientific notation
Example:  000010000000 => 1E7
          000120000000 => 12E7
          000001230000 => 123E4
          100000000000 => 1E11
          000000000000 => 0E0  
          000000000001 => 1E0
Algorithm0:
  posFirstNZD = position of first non-zero digit
  posLastNZD  = position of last non-zero digit
  expo = MAX_DIGITS-1-posLastNZD
  for i=posFirstNZD to posLastNZD
    display digits[i]
    end for

  display 'E'
  display expo
*/
void CPosBigInt::displayScientific(void)
  {
  int posFirstNZD = MAX_DIGITS-1;
  for (int i=0; i<=MAX_DIGITS-1; i++)
    if (_digits[i] != '0')
      {
      posFirstNZD = i;
      break;
      }

  int posLastNZD  = MAX_DIGITS-1;
  for (i=MAX_DIGITS-1; i>=0; i--)
    if (_digits[i] != '0')
      {
      posLastNZD = i;
      break;
      }
  
  int expo = MAX_DIGITS-1-posLastNZD;

  for (i=posFirstNZD; i<=posLastNZD; i++)
    cout << _digits[i];

  cout << 'E';
  cout << expo << endl;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_add(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_add(void)
  {
  cout << "---------------------\n";
  cout << "driver_CPosBigInt_add\n";
  cout << "---------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt x('d'), y('d'), z('d');

    cout << "x="; x.display();
    cout << "y="; y.display();
    cout << "z="; z.display();

    add(x, y, z);

    cout << "After add(x, y, z);\n";

    cout << "x="; x.display();
    cout << "y="; y.display();
    cout << "z="; z.display();
    }

  for (i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt x('r'), y('r'), z('r');

    cout << "x="; x.display();
    cout << "y="; y.display();
    cout << "z="; z.display();

    add(x, y, z);

    cout << "After add(x, y, z);\n";

    cout << "x="; x.display();
    cout << "y="; y.display();
    cout << "z="; z.display();


    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// void add(CPosBigInt x, CPosBigInt y, CPosBigInt z)
//////////////////////////////////////////////////////////////////////
/*
Purpose: Add the values of x and y and put result in z
Example: x=1234, y=67 => z=1301
Algorithm0:
Initialize z to zero
c = 0
for i= MAX_DIGITS-1 to 0 do the following
  sum = x.digits[i] + y.digits[i] + c
  d = sum%10
  c = sum/10
  z.digits[i]=d
  end for

*/
void add(CPosBigInt x, CPosBigInt y, CPosBigInt &z)
  {
  z.initialize();
  int c = 0, d, sum;
  for (int i= MAX_DIGITS-1; i>=0; i--)
    {
    sum = (x._digits[i]-'0') + (y._digits[i]-'0') + c;
    d = sum%10;
    c = sum/10;
    z._digits[i]='0'+ d;
    }
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Constructor_RandZ(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Constructor_RandZ(void)
  {
  cout << "----------------------------------\n";
  cout << "driver_CPosBigInt_Constructor_RandZ\n";
  cout << "----------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('z');
    cout << "a="; a.display();
    cout << "------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_shiftLeft(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_shiftLeft(void)
  {
  cout << "---------------------------\n";
  cout << "driver_CPosBigInt_shiftLeft\n";
  cout << "----------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('d');

    cout << "a="; a.display();

    a.shiftLeft();

    cout << "a="; a.display();

    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::shiftLeft(void)
//////////////////////////////////////////////////////////////////////
/*
Purpose: Shift left all the digits
Example: '00012' => '00120'
Algorithm:

if the first digit is non-zero then
    overflow = true
  else
    overflow = false

for i=1 to MAX_DIGITS-1
  digits[i] = digits[i+1]
  end for

digits[MAX_DIGITS-1] = '0'

return not(overflow)

*/
bool CPosBigInt::shiftLeft(void)
  {
  bool overflow;

  if (_digits[0] != '0')
      overflow = true;
    else
      overflow = false;

  for (int i=1; i<=MAX_DIGITS-1; i++)
    _digits[i] = _digits[i+1];
    

  _digits[MAX_DIGITS-1] = '0';

  return !overflow;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_displayMinimized(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_displayMinimized(void)
  {
  cout << "----------------------------------\n";
  cout << "driver_CPosBigInt_displayMinimized\n";
  cout << "----------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('r');
    cout << "a="; a.display();
    cout << "a="; a.displayMinimized();
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// void CPosBigInt::displayMinimized(void)
//////////////////////////////////////////////////////////////////////
/*
Purpose:   Display a big integer in minimized form (without leading zeros)
Examples:  000000123 will be displayed as 123
Algorithm:
  do the following for i=0 to MAX_DIGITS-2
    if digits[i] != '0' then
      startPrint = i
      exit loop
      end if
    end do

  do the following for i=startPrint to MAX_DIGITS-1
    display digits[i]
    end do
*/
void CPosBigInt::displayMinimized(void)
  {
  int startPrint = MAX_DIGITS-1; //corrected 2004.02.18

  for (int i=0; i<=MAX_DIGITS-2; i++)
    {
    if (_digits[i] != '0')
      {
      startPrint = i;
      break;
      }
    }

  for (i=startPrint; i<=MAX_DIGITS-1; i++)
    cout << _digits[i];
  
  cout << endl;
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Constructor_Rand(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Constructor_Rand(void)
  {
  cout << "----------------------------------\n";
  cout << "driver_CPosBigInt_Constructor_Rand\n";
  cout << "----------------------------------\n";

  for (int i=0; i<=TEST_COUNT-1; i++)
    {
    CPosBigInt a('r');
    cout << "a="; a.display();
    cout << "----------------------------------------------------\n";
    }
  }


//////////////////////////////////////////////////////////////////////
// CPosBigInt::CPosBigInt(char ch)
//////////////////////////////////////////////////////////////////////
/*
Purpose:   A constructor to create a random big integer
Examples:  CPosBigInt x('r'); could give x=667621
Algorithm:
  initialize all digits with zeros
  set leadingZeros to a random number between 0 and MAX_DIGITS;
  do the following for i=leadingZeros to MAX_DIGITS-1
    d = random integer between 0 and 9
    c = random character betwwe '0' to '9' using d 
    digits[i] = c
    end do
*/
CPosBigInt::CPosBigInt(char ch)
  {
  initialize();

  if ('r' == ch)
      {
      int leadingZeros = rand()%(MAX_DIGITS+1);

      for (int i=0; i<=MAX_DIGITS-1; i++)
        {
        char c;
        if (i < leadingZeros)
            c = '0';
          else
            c = '0' + rand()%10;
        _digits[i] = c;
        }
      }

  if ('d' == ch)
    {
    int k   = rand()%TEST_DATA_COUNT;

    int len = strlen(TEST_DATA[k]);

    for (int j=0; j<=len-1; j++)
      if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
        return;

    for (int i=0; i<=len-1; i++)
      _digits[MAX_DIGITS-len+i] = TEST_DATA[k][i];

    }

  if ('z' == ch)
    {
    // create a random big integer from test data 
    // with lots of leading and trailing zeros
    // fully contained
    // Algorithm0:
    //   initialize with zeros
    //   pick a spot randomly so that TEST_DATA[k] would be fully contained
    //   put the TEST_DATA[k] starting at that point

    // Algorithm1:
    //   initialize with zeros
    //   k = random(0..TEST_DATA_COUNT-1)
    //   len = length of TEST_DATA[k]
    //   spot = rand(0..MAX_DIGITS-len-1]
    //   for i=0 to len-1 do
    //     digits[spot+i] = TEST_DATA[k][i]
    //     end do

    int k = rand()%TEST_DATA_COUNT;
    //cout << "    k = " << k    << endl;

    int len = strlen(TEST_DATA[k]);
    //cout << "  len = " << len  << endl;

    //cout << "from constructor CPosBigInt(char ch) " << TEST_DATA[k] << endl;

    for (int j=0; j<=len-1; j++)
      if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
        return;

    int spot = rand()%(MAX_DIGITS-len);
    //cout << " spot = " << spot << endl;

    for (int i=0; i<=len-1; i++)
      _digits[spot+i] = TEST_DATA[k][i];
    
    }
  }


//////////////////////////////////////////////////////////////////////
// void CPosBigInt::initialize(void)
//////////////////////////////////////////////////////////////////////
/*
Initializes a big integer with zeros
*/
void CPosBigInt::initialize(void)
  {
  for (int i=0; i<MAX_DIGITS; i++)
    _digits[i] = '0';
  }


//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Constructor_Str(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Constructor_Str(void)
  {
  cout << "---------------------------------\n";
  cout << "driver_CPosBigInt_Constructor_Str\n";
  cout << "---------------------------------\n";

  CPosBigInt a("1234");
  cout << "a="; a.display();

  CPosBigInt b("12");
  cout << "b="; b.display();

  CPosBigInt c("Hello");
  cout << "c="; c.display();
  }


//////////////////////////////////////////////////////////////////////
// CPosBigInt::CPosBigInt(char d[])
//////////////////////////////////////////////////////////////////////
/*
A constructor that takes a character array and
creates and initializes a big integer

CPosBigInt a("12345");
will create object a with value 12345

"12345"
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000012345

Algorithm:
fill digits with zeros
 for
len = length of a[]

digits[MAX_DIGITS-len]  =  d[0]
digits[MAX_DIGITS-len+1] = d[1]
digits[MAX_DIGITS-len+2] = d[2]
digits[MAX_DIGITS-len+3] = d[3]
digits[MAX_DIGITS-len+4] = d[4]

for i=0 to len-1
  digits[MAX_DIGITS-len+i] = d[i]

*/
CPosBigInt::CPosBigInt(char d[])
  {
  initialize();

  int len = strlen(d);

  for (int j=0; j<=len-1; j++)
    if (d[j] < '0' || d[j] >'9')
      return;

  for (int i=0; i<=len-1; i++)
    _digits[MAX_DIGITS-len+i] = d[i];

  }


//////////////////////////////////////////////////////////////////////
// CPosBigInt::CPosBigInt(void)
//////////////////////////////////////////////////////////////////////
CPosBigInt::CPosBigInt(void)
  {
  initialize();
  };


//////////////////////////////////////////////////////////////////////
// void CPosBigInt::display(void)
//////////////////////////////////////////////////////////////////////
void CPosBigInt::display(void)
  {
  for (int i=0; i<MAX_DIGITS; i++)
    cout << _digits[i];

  cout << endl;
  };


//////////////////////////////////////////////////////////////////////
// IMPORTANT TO REMEMBER
//////////////////////////////////////////////////////////////////////
  /*
  cout << "// [SHRT_MIN, SHRT_MAX] = [-32767,32767]\n";
  cout << "[" << SHRT_MIN << ", " << SHRT_MAX << "]\n";

  cout << "// [0, USHRT_MAX] = [0, 65535]\n";
  cout << "[" << 0 << ", " << USHRT_MAX << "]\n";

  cout << "// [LONG_MIN, LONG_MAX] = [-2147483647, 2147483647]\n";
  cout << "[" << LONG_MIN << ", " << LONG_MAX << "]\n";

  cout << "// [0, ULONG_MAX] = [0, 4294967295]\n";
  cout << "[" << 0 << ", " << ULONG_MAX << "]\n";
  */


//////////////////////////////////////////////////////////////////////
// SAMPLE OUTPUT:
//////////////////////////////////////////////////////////////////////
/*

*/