//file CBigInt013.cpp
//date 02/25/2005
//author aou
//csis250.tripod.com
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
/* Project #03
Date Assigned: 02/16/2005, Date Due: 02/23/2005
Implement the following functions (assume positive ints):
void subtract1(CBigInt a, CBigInt b, CBigInt &c); //P03
void test_subtract1(void);
Submit the printed problem description, examples (2), algorithms,
source code, and the output (5 test cases)
*/
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
/*
Description:
Example:
Algorithm:
Source:
Output:
*/
///////////////////////////////////////////////////////////
//includes
///////////////////////////////////////////////////////////
#include <iostream>
using namespace std;
///////////////////////////////////////////////////////////
//constants
///////////////////////////////////////////////////////////
const int MAX_DIGITS = 50;
const int BASE = 10;
const int TEST_COUNT = 10;
///////////////////////////////////////////////////////////
//class CBigInt
///////////////////////////////////////////////////////////
class CBigInt
{
private:
int _base;
char _sign;
char _digits[MAX_DIGITS];
bool isValid(char s[]);
void retrieveValue(char s[]);
public:
CBigInt(void);//constructor/auto-initializer
void display(void);
void initialize(void);
CBigInt(char s[]); //CBigInt bi("+12345");
void input(void);
void displayMinimized(void);
CBigInt(char ch);
void add1(CBigInt a, CBigInt b, CBigInt &c);
CBigInt add(CBigInt a, CBigInt b);
void add(CBigInt a);
void subtract1(CBigInt a, CBigInt b, CBigInt &c); //P03
//add(a, b, c);
//add(a, b);
//add(b);
//CBigInt abs(void);
//CBigInt pow(int expo);
};
void test_add1(void);
void test_ConstructorRandomPos(void);
void test_subtract1(void);
void test_ConstructorOne(void);
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void main(void)
{
srand(23);
test_add1();
//test_subtract1();
//test_ConstructorRandomPos();
//test_ConstructorOne();
/*
CBigInt a('+'), b, c('u');
a.display();
b.display();
c.display();
cout << "After b = a;\n";
b = a;
a.display();
b.display();
c.display();
*/
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::subtract1(CBigInt a, CBigInt b, CBigInt &c)
/*
Description: implements subtract operation for two big positive
integers
c = a-b
Examples:
a=5, b=3, c=a-b=>c=2
a=3, b=5, c=a-b=>c=-2
Algorithms0:
if a and b are same base and positive then
borrowed = 0 or -1
from rightmost to leftmost digits do
if a >= b then c = a - b, borrowed = 0
if a < b then borrowed = -1,
a = a + base, c = a - b
do not forget the borrowed
end do
if borrowed = -1 then sign = '-'
else sign = '+'
Algorithms1:
if a and b are same base and positive then
borrowed = 0
for i = max_digits-1 to 0 step -1
a.digits[i] = a.digits[i] - borrowed
if a.digits[i] >= b.digits[i] then
c.digits[i] = a.digits[i] - b.digits[i]
borrowed = 0
else
borrowed = 1,
a.digits[i] = a.digits[i] + base,
c.digits[i] = a.digits[i] - b.digits[i]
end do
if borrowed = 1 then
sign = '-'
for i = max_digits-1 to 0 step -1
c.digits[i] =9-c.digits[i]
end do
add 1 to c (using a loop from add1 function)
else
sign = '+'
examples:
00212 00212 00101
00101 00109 00912
----- ----- -----
00111 00103 199189
-00810
+1
-00811
00312
00423
-----
199889
-00110
+1
-00111
*/
{
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_subtract1(void)
{
cout << "-------------------------\n";
cout << "test subtract1\n";
cout << "-------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('+'), b('+'), c, t;
cout << "a = "; a.display();
cout << "b = "; b.display();
t.subtract1(a,b,c);
cout << "c = "; c.display();
cout << endl;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
CBigInt::CBigInt(char code)
/*
Description: Generates a random big integer based on the
value of parameter code
'+' => positive
'-' => negative
'r' => positive or negative
'z' => zero
'u' => 1
Example:
CBigInt a('+'); => a=+123
CBigInt a('-'); => a=-123
CBigInt a('z'); => a=+0
Algorithm:
if code is '+' then
set sign as +
length = random(1, 5)
place = MAX_DIGITS-1
do the following length times
d = random('0'.. '9')
digits[place] = d
place--
end do
end if
Source:
Output:
*/
{
if (code == '+') //CBigint aaa('+');
{
initialize();
int length = rand()%5 +1 ;
int place = MAX_DIGITS-1;
for (int i=1; i<=length; i++)
{
char d = rand()%10 + 48;
_digits[place] = d;
place--;
}
}
if (code == 'u') //CBigInt one('u');
{
initialize();
_digits[MAX_DIGITS-1] = '1';
}
if (code == 'z') //CBigInt zero('z');
{
initialize();
}
if (code == '-') //CBigint aaa('-');
{
initialize();
_sign = '-';
int length = rand()%5 +1 ;
int place = MAX_DIGITS-1;
for (int i=1; i<=length; i++)
{
char d = rand()%10 + 48;
_digits[place] = d;
place--;
}
}
if (code == 'r') //CBigint aaa('r');
{
initialize();
if ((rand()%2) == 0)
_sign = '+';
else
_sign = '-';
int length = rand()%5 +1 ;
int place = MAX_DIGITS-1;
for (int i=1; i<=length; i++)
{
char d = rand()%10 + 48;
_digits[place] = d;
place--;
}
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_ConstructorZero(void)
{
cout << "--------------------\n";
cout << "test_ConstructorZero\n";
cout << "--------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('z');
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
cout << "-----------------------------\n";
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_ConstructorOne(void)
{
cout << "-------------------\n";
cout << "test_ConstructorOne\n";
cout << "-------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('u');
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
cout << "-----------------------------\n";
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_ConstructorRandomPos(void)
{
cout << "-------------------------\n";
cout << "test_ConstructorRandomPos\n";
cout << "-------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('+');
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
cout << "-----------------------------\n";
}
}
/*
-------------------------
test_ConstructorRandomPos
-------------------------
a = +00000000000000000000000000000000000000000000000047[10]
a = +47
-----------------------------
a = +00000000000000000000000000000000000000000000000009[10]
a = +9
-----------------------------
a = +00000000000000000000000000000000000000000000054288[10]
a = +54288
-----------------------------
a = +00000000000000000000000000000000000000000000000001[10]
a = +1
-----------------------------
a = +00000000000000000000000000000000000000000000000511[10]
a = +511
-----------------------------
a = +00000000000000000000000000000000000000000000000167[10]
a = +167
-----------------------------
a = +00000000000000000000000000000000000000000000012232[10]
a = +12232
-----------------------------
a = +00000000000000000000000000000000000000000000000058[10]
a = +58
-----------------------------
a = +00000000000000000000000000000000000000000000000816[10]
a = +816
-----------------------------
a = +00000000000000000000000000000000000000000000045972[10]
a = +45972
-----------------------------
Press any key to continue*/
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::add1(CBigInt a, CBigInt b, CBigInt &c)
{
/*
Description: implements add operation for two big positive
integers
c = a+b
Examples:
a=3, b=5, c=a+b=>c=8
Algorithms:
Algorithms0:
if a and b are same base and positive then
carry = 0
from rightmost to leftmost digits do
add digits and carry
put the sum in c
do not forget the carry
end do
*/
int carry = 0;
for (int i= MAX_DIGITS-1; i>=0; i--)
{
int ad = a._digits[i]-48;
int bd = b._digits[i]-48;
int sd = carry + ad + bd;
carry = sd/BASE;
sd = sd%BASE;
c._digits[i] = sd+48;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_add1(void)
{
cout << "-------------------------\n";
cout << "test add1\n";
cout << "-------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('+'), b('+'), c, t;
cout << "a = "; a.display();
cout << "b = "; b.display();
t.add1(a,b,c);
cout << "c = "; c.display();
cout << endl;
}
}
///////////////////////////////////////////////////////////
// void CBigInt::displayMinimized(void)
///////////////////////////////////////////////////////////
void CBigInt::displayMinimized(void)
{
/*
Description:
This function displays the big integer in minimized form
Examples:
+00000000000000000000000000000000000000000000000123[10]
displays as +123
-00000000000000000000000000000000000000000000000023[10]
displays as -23
Algorithms:
Algorithm0:
display the sign
get the position of first non-zero digit in nz
(take care of all zeros possibility)
for i=nz to MAX_DIGITS-1
display digit[i]
end for
Algorithm1:
display the sign
//get the position of first non-zero digit in nz
//(take care of all zeros possibility)
nz = MAX_DIGITS-1
for i=0 to MAX_DIGITS-2
if digits[i] <> '0' then nz = i, exit for loop
end for
for i=nz to MAX_DIGITS-1
display digit[i]
end for
*/
cout << _sign;
//get the position of first non-zero digit in nz
//(take care of all zeros possibility)
int nz = MAX_DIGITS-1;
for (int i=0; i<=MAX_DIGITS-2; i++)
if (_digits[i] != '0')
{
nz = i;
break;
}
for (i=nz; i<=MAX_DIGITS-1; i++)
cout << _digits[i];
cout << endl;
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::retrieveValue(char s[])
{
/* get big integer from s
assumes that s has a valid number
Algorithm0:
if there is a sign then
get the sign and the remaining digits
else
assume the sign as +ve
get the all the digits
end if
Algorithm1:
if the first digit is + or - then
get the sign from the first digit
get the remaining digits
else
set the sign as +ve
get the all the digits
end if
Algorithm2:
if s[0] is + or - then
sign = s[0]
//get the remaining digits
else
sign = '+'
//get the all the digits
end if
Algorithm3:
if s[0] is + or - then
sign = s[0]
//get the remaining digits
j = MAX_DIGITS-1
for i = length(s)-1 to 1
digits[j] = s[i]
j--
end for
else
sign = '+'
//get the all the digits
j = MAX_DIGITS-1
for i = length(s)-1 to 0
digits[j] = s[i]
j--
end for
end if
*/
if (s[0] == '+' || s[0] == '-')
{
_sign = s[0];
//get the remaining digits
int j = MAX_DIGITS-1;
for (int i = strlen(s)-1; i>=1; i--)
{
_digits[j] = s[i];
j--;
}
}
else
{
_sign = '+';
//get the all the digits
int j = MAX_DIGITS-1;
for (int i = strlen(s)-1; i>=0; i--)
{
_digits[j] = s[i];
j--;
}
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
bool CBigInt::isValid(char s[])
{
/*
check if s has a valid integer
possibilities:
first character is +, -, or a digit 0 to 9
rest of the characters should be 0 to 9
Algorithm0:
if s[0] is not a digit or + or - then
return false
else
if rest of the digits are not 0 to 9 then
return false
else
return true
Algorithm1:
if (s[0] is not a digit) and (s[0] <> '+') and (s[0]<>'-') then
return false
else
if rest of the digits are not 0 to 9 then
return false
else
return true
Algorithm2:
if ((s[0]<'0' or s[0]>'9') and (s[0] <> '+') and (s[0]<>'- ') then
return false
else
for i=1 to strlen(s)-1
if s[i] is not 0 to 9 then
return false
end for
return true
*/
if ((s[0]<'0' || s[0]>'9') && (s[0] != '+') && (s[0] != '-'))
return false;
else
{
for (int i=1; i<=strlen(s)-1; i++)
if (s[i]<'0' || s[i]>'9')
return false;
return true;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::input(void)
{
char s[MAX_DIGITS+2];
cin >> s;
initialize();
if (!isValid(s))
return;
retrieveValue(s);
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
CBigInt::CBigInt(char s[])
{
initialize();
if (!isValid(s))
return;
retrieveValue(s);
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::display(void)
{
cout << _sign;
for (int i=0; i<=MAX_DIGITS-1; i++)
cout << _digits[i];
cout << '[' << _base << "]\n";
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::initialize(void)
{
_base = BASE;
_sign = '+';
for (int i=0; i<=MAX_DIGITS-1; i++)
_digits[i] = '0';
}
///////////////////////////////////////////////////////////
// CBigInt::CBigInt(void)
///////////////////////////////////////////////////////////
CBigInt::CBigInt(void)
{
initialize();
}
/*
*/
|