// CPosBigInt12_p10.cpp
// 04/02/2004
// Author: AOU
/********************************************************************/
/********************************************************************/
/*
2004 Spring csis 250 P10 Date Assigned: 04/02/2004, Due: 04/07/2004
Add detailed descriptions, at least two examples, and detailed algorithm to
each function in the latest source code including the solution to project 9.
Do not have to add comments to the driver functions.
This will prepare you for the test on Monday (4/5/2004)
Submit the following:
(1) Printed description, examples, algorithms, and the source code.
/********************************************************************/
/********************************************************************/
/*
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 char *TEST_DATA[] =
{
"0", "1", "12", "123", "1234", "123450", "1234506", "12345067"
};
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 code); // 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
bool operator <= (const CPosBigInt &bi2); //p07 A:2004.03.04
bool operator > (const CPosBigInt &bi2); //p07 A:2004.03.04
bool operator >= (const CPosBigInt &bi2); //p07 A:2004.03.04
bool operator != (const CPosBigInt &bi2); //p07 A:2004.03.04
bool shiftRight(void); //p08
bool shiftRight(int d); //p08
bool shiftLeft(int d); //p08
CPosBigInt add(const CPosBigInt &y);
CPosBigInt operator +(const CPosBigInt &y); //p09
};
// 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 driver_CPosBigInt_Operator_isLessThanOrEqual(void);
void driver_CPosBigInt_Operator_isGreaterThan(void);
void driver_CPosBigInt_Operator_isGreaterThanOrEqual(void);
void driver_CPosBigInt_Operator_isNotEqual(void);
void driver_CPosBigInt_shiftRight(void);
void driver_CPosBigInt_shiftRightD(void);
void driver_CPosBigInt_shiftLeftD(void);
void driver_CPosBigInt_addMember(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();
//driver_CPosBigInt_Operator_isLessThanOrEqual();
//driver_CPosBigInt_Operator_isGreaterThan();
//driver_CPosBigInt_Operator_isGreaterThanOrEqual();
//driver_CPosBigInt_Operator_isNotEqual();
//driver_CPosBigInt_shiftRight();
//driver_CPosBigInt_shiftRightD();
//driver_CPosBigInt_shiftLeftD();
//driver_CPosBigInt_addMember();
}
//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_addMember(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_addMember(void)
{
cout << "---------------------------\n";
cout << "driver_CPosBigInt_addMember\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();
z = x.add(y);
cout << "After z = x.add(y);\n";
cout << "x="; x.display();
cout << "y="; y.display();
cout << "z="; z.display();
cout << "----------------------------------------------------\n";
}
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();
z = x.add(y);
cout << "After z = x.add(y);\n";
cout << "x="; x.display();
cout << "y="; y.display();
cout << "z="; z.display();
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// CPosBigInt CPosBigInt::add(const CPosBigInt &y)
//////////////////////////////////////////////////////////////////////
CPosBigInt CPosBigInt::add(const CPosBigInt &y)
{
CPosBigInt z;
int c = 0, d, sum;
for (int i= MAX_DIGITS-1; i>=0; i--)
{
sum = (this->_digits[i]-'0') + (y._digits[i]-'0') + c;
d = sum%10;
c = sum/10;
z._digits[i]='0'+ d;
}
return z;
}
//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_shiftLeftD(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_shiftLeftD(void)
{
cout << "----------------------------\n";
cout << "driver_CPosBigInt_shiftLeftD\n";
cout << "----------------------------\n";
int da[] = {-1, 0, 1, MAX_DIGITS/2, MAX_DIGITS, MAX_DIGITS+1};
int daCount = sizeof(da)/sizeof(da[0]);
for (int i=0; i<daCount; i++)
{
CPosBigInt a('d');
cout << "a="; a.display();
int d = da[i];
a.shiftLeft(d);
cout << "After a.shiftLeft(" << d << ");\n";
cout << "a="; a.display();
cout << "----------------------------------------------------\n";
}
for (i=0; i<=TEST_COUNT-1; i++)
{
CPosBigInt a('d');
cout << "a="; a.display();
int d = -5 + rand()%(MAX_DIGITS +11);
a.shiftLeft(d);
cout << "After a.shiftLeft(" << d << ");\n";
cout << "a="; a.display();
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::shiftLeft(int d)
//////////////////////////////////////////////////////////////////////
bool CPosBigInt::shiftLeft(int d)
{
if (d == 0)
return true;
else if (d < 0)
return false;
else if (d >= MAX_DIGITS)
{
this->initialize();
return true;
}
else //d > 0 and d < MAX_DIGITS
{
cout << "code missing\n";
return true;
}
}
//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_shiftRightD(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_shiftRightD(void)
{
cout << "-----------------------------\n";
cout << "driver_CPosBigInt_shiftRightD\n";
cout << "-----------------------------\n";
for (int i=0; i<=TEST_COUNT-1; i++)
{
CPosBigInt a('d');
cout << "a="; a.display();
int d = -5 + rand()%(MAX_DIGITS +11);
a.shiftRight(d);
cout << "After a.shiftRight(" << d << ");\n";
cout << "a="; a.display();
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::shiftRight(int d)
//////////////////////////////////////////////////////////////////////
bool CPosBigInt::shiftRight(int d)
{
cout << "code missing\n";
return true;
}
//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_shiftRight(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_shiftRight(void)
{
cout << "----------------------------\n";
cout << "driver_CPosBigInt_shiftRight\n";
cout << "----------------------------\n";
for (int i=0; i<=TEST_COUNT-1; i++)
{
CPosBigInt a('d');
cout << "a="; a.display();
a.shiftRight();
cout << "a="; a.display();
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::shiftRight(void)
//////////////////////////////////////////////////////////////////////
bool CPosBigInt::shiftRight(void)
{
cout << "code missing\n";
return true;
}
//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Operator_isNotEqual(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Operator_isNotEqual(void)
{
cout << "-------------------------------------\n";
cout << "driver_CPosBigInt_Operator_isNotEqual\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 NOT equal to b\n";
else
cout << "a is equal to b\n";
if (a != c)
cout << "a is NOT equal to c\n";
else
cout << "a is equal to c\n";
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::operator != (const CPosBigInt &bi2)
//////////////////////////////////////////////////////////////////////
bool CPosBigInt::operator != (const CPosBigInt &bi2)
{
return !(*this == bi2);
}
//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Operator_isGreaterThanOrEqual(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Operator_isGreaterThanOrEqual(void)
{
cout << "-----------------------------------------------\n";
cout << "driver_CPosBigInt_Operator_isGreaterThanOrEqual\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 greater than or equal to b\n";
else
cout << "a is NOT greater than or equal to b\n";
if (a >= c)
cout << "a is greater than or equal to c\n";
else
cout << "a is NOT greater than or equal to c\n";
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::operator >= (const CPosBigInt &bi2)
//////////////////////////////////////////////////////////////////////
bool CPosBigInt::operator >= (const CPosBigInt &bi2)
{
return !(*this < bi2);
}
//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Operator_isGreaterThan(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Operator_isGreaterThan(void)
{
cout << "----------------------------------------\n";
cout << "driver_CPosBigInt_Operator_isGreaterThan\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 greater than b\n";
else
cout << "a is NOT greater than b\n";
if (a > c)
cout << "a is greater than c\n";
else
cout << "a is NOT greater than c\n";
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::operator > (const CPosBigInt &bi2)
//////////////////////////////////////////////////////////////////////
bool CPosBigInt::operator > (const CPosBigInt &bi2)
{
CPosBigInt temp(bi2);
return (temp < *this);
}
//////////////////////////////////////////////////////////////////////
// void driver_CPosBigInt_Operator_isLessThanOrEqual(void)
//////////////////////////////////////////////////////////////////////
void driver_CPosBigInt_Operator_isLessThanOrEqual(void)
{
cout << "--------------------------------------------\n";
cout << "driver_CPosBigInt_Operator_isLessThanOrEqual\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 or equal to b\n";
else
cout << "a is NOT less than or equal to b\n";
if (a <= c)
cout << "a is less than or equal to c\n";
else
cout << "a is NOT less than or equal to c\n";
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CPosBigInt::operator <= (const CPosBigInt &bi2)
//////////////////////////////////////////////////////////////////////
bool CPosBigInt::operator <= (const CPosBigInt &bi2)
{
CPosBigInt temp(bi2);
return !(temp < *this);
}
//////////////////////////////////////////////////////////////////////
// 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)
{
if (*this == bi2)
return false;
for (int i=0; i<=MAX_DIGITS-1; i++)
if (_digits[i] < bi2._digits[i])
return true;
else if (_digits[i] > bi2._digits[i])
return false;
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=0 to MAX_DIGITS-2
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=0; i<=MAX_DIGITS-2; i++) //corrected 2004.03.11
_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:
//////////////////////////////////////////////////////////////////////
/*
*/
|