//file CBigInt010.cpp
//date 02/16/2005
//author aou
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
/* Project #03
Date Assigned: 02/16/2005, Date Due: 02/23/2005
Implement the following functions:
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 main(void)
{
//test_add1();
test_ConstructorRandomPos();
/*
CBigInt b;
cout << "b = "; b.display();
CBigInt a("667627001667627001667627001");
cout << "a = "; a.display();
CBigInt c("+667627001667627001667627001");
cout << "c = "; c.display();
CBigInt d("-667627001667627001667627001");
cout << "d = "; d.display();
CBigInt e("667-627001667627001667627001");
cout << "e = "; e.display();
cout << "Enter a big integer " ;
a.input();
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
cout << "Enter a big integer " ;
a.input();
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
*/
//cin >> a; a.input();
//cin >> b;
//cin >> c;
//c = a + b; add(a, b, c);
//cout << c; c.display();
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
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:
*/
{
initialize();
if (code == '+')
{
_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_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";
{
CBigInt a("123"), b("999"), c, t;
a.display();
b.display();
t.add1(a,b,c);
c.display();
cout << endl;
}
{
CBigInt a("11111111111111"), b("222222222222"), c, t;
a.display();
b.display();
t.add1(a,b,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();
}
/*
*/
|