// CPosBigInt05.cpp
// 02/09/2004
// Author: AOU
// fix the error in add function
/*
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>
//////////////////////////////////////////////////////////////////////
// constants
//////////////////////////////////////////////////////////////////////
const int MAX_DIGITS = 50;
const int TEST_COUNT = 10;
const char *TEST_DATA[] =
{
"0", "1", "12", "123", "1234", "123450", "1234506", "12345067",
"123450670", "1234506708", "1234506708", "Hello", "PSU",
"9", "99", "999", "9999", "99999", "999999", "9999999"
};
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
void displayMinimized(void); // p02
bool shiftLeft(void); // 2004.02.02
friend void add(CPosBigInt x, CPosBigInt y, CPosBigInt &z); // 2004.02.09
void displayRev(void); //
//wish list
// shiftRight Matt
// add (+) Tom
// subtract (-) Chad
// multiply (*) Brian
// divide (/) Grant
// displayScientific Daniel
// input >> Alex
// negate Tony1
// square root Aifu
// average of array 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_add(void);
//////////////////////////////////////////////////////////////////////
// void main(void)
//////////////////////////////////////////////////////////////////////
void main(void)
{
//driver_CPosBigInt_Constructor_Str();
//driver_CPosBigInt_Constructor_Rand();
//driver_CPosBigInt_displayMinimized();
//driver_CPosBigInt_shiftLeft();
driver_CPosBigInt_add();
}
//////////////////////////////////////////////////////////////////////
// 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();
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;
cout << "**********z="; z.display();
}
//////////////////////////////////////////////////////////////////////
// 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();
}
}
//////////////////////////////////////////////////////////////////////
// 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)
{
// supply the code
}
//////////////////////////////////////////////////////////////////////
// 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();
}
}
//////////////////////////////////////////////////////////////////////
// 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)
supply the code
*/
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
// Rough plan:
// 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
}
}
//////////////////////////////////////////////////////////////////////
// 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;
};
//////////////////////////////////////////////////////////////////////
// SAMPLE OUTPUT:
//////////////////////////////////////////////////////////////////////
/*
---------------------
driver_CPosBigInt_add
---------------------
x=00000000000000000000000000000000000000000000000001
y=00000000000000000000000000000000000000000012345067
z=00000000000000000000000000000000000000000000000099
**********z=00000000000000000000000000000000000000000000000000
After add(x, y, z);
x=00000000000000000000000000000000000000000000000001
y=00000000000000000000000000000000000000000012345067
z=00000000000000000000000000000000000000000000000000
------------------------------------------
x=00000000000000000000000000000000000000000000000000
y=00000000000000000000000000000000000000001234506708
z=00000000000000000000000000000000000000000000001234
**********z=00000000000000000000000000000000000000000000000000
After add(x, y, z);
x=00000000000000000000000000000000000000000000000000
y=00000000000000000000000000000000000000001234506708
z=00000000000000000000000000000000000000000000000000
------------------------------------------
x=00000000000000000000000000000000000000000000999999
y=00000000000000000000000000000000000000000000999999
z=00000000000000000000000000000000000000000000000012
**********z=00000000000000000000000000000000000000000000000000
After add(x, y, z);
x=00000000000000000000000000000000000000000000999999
y=00000000000000000000000000000000000000000000999999
z=00000000000000000000000000000000000000000000000000
------------------------------------------
x=00000000000000000000000000000000000000000000001234
y=00000000000000000000000000000000000000000000123450
z=00000000000000000000000000000000000000000000123450
**********z=00000000000000000000000000000000000000000000000000
After add(x, y, z);
x=00000000000000000000000000000000000000000000001234
y=00000000000000000000000000000000000000000000123450
z=00000000000000000000000000000000000000000000000000
------------------------------------------
x=00000000000000000000000000000000000000000000000001
y=00000000000000000000000000000000000000000012345067
z=00000000000000000000000000000000000000000000000001
**********z=00000000000000000000000000000000000000000000000000
After add(x, y, z);
x=00000000000000000000000000000000000000000000000001
y=00000000000000000000000000000000000000000012345067
z=00000000000000000000000000000000000000000000000000
------------------------------------------
x=00000000000000000000000000000000000000000000000000
y=00000000000000000000000000000000000000000000000999
z=00000000000000000000000000000000000000000000000012
**********z=00000000000000000000000000000000000000000000000000
After add(x, y, z);
x=00000000000000000000000000000000000000000000000000
y=00000000000000000000000000000000000000000000000999
z=00000000000000000000000000000000000000000000000000
------------------------------------------
x=00000000000000000000000000000000000000000012345067
y=00000000000000000000000000000000000000000000009999
z=00000000000000000000000000000000000000000000000000
**********z=00000000000000000000000000000000000000000000000000
After add(x, y, z);
x=00000000000000000000000000000000000000000012345067
y=00000000000000000000000000000000000000000000009999
z=00000000000000000000000000000000000000000000000000
------------------------------------------
x=00000000000000000000000000000000000000000000001234
y=00000000000000000000000000000000000000000000000012
z=00000000000000000000000000000000000000000000000009
**********z=00000000000000000000000000000000000000000000000000
After add(x, y, z);
x=00000000000000000000000000000000000000000000001234
y=00000000000000000000000000000000000000000000000012
z=00000000000000000000000000000000000000000000000000
------------------------------------------
x=00000000000000000000000000000000000000000000000000
y=00000000000000000000000000000000000000000000000012
z=00000000000000000000000000000000000000000000000001
**********z=00000000000000000000000000000000000000000000000000
After add(x, y, z);
x=00000000000000000000000000000000000000000000000000
y=00000000000000000000000000000000000000000000000012
z=00000000000000000000000000000000000000000000000000
------------------------------------------
x=00000000000000000000000000000000000000000000009999
y=00000000000000000000000000000000000000000000999999
z=00000000000000000000000000000000000000000000000999
**********z=00000000000000000000000000000000000000000000000000
After add(x, y, z);
x=00000000000000000000000000000000000000000000009999
y=00000000000000000000000000000000000000000000999999
z=00000000000000000000000000000000000000000000000000
------------------------------------------
Press any key to continue
*/
|