//file CBigInt017.cpp
//date 03/09/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 = 5;
///////////////////////////////////////////////////////////
//class CBigInt
///////////////////////////////////////////////////////////
class CBigInt
{
private:
int _base;
char _sign;
char _digits[MAX_DIGITS];
bool isValid(char s[]);
void retrieveValue(char s[]);
void initialize(void);
public:
CBigInt(void);//constructor/auto-initializer
void display(void);
CBigInt(char s[]); //CBigInt bi("+12345");
void input(void);
void displayMinimized(void);
CBigInt(char code);
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
int length(void);
CBigInt(int x); // CBigInt b(34);
//lessThan (b);
//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 test_length(void);
void test_ConstructorInt(void);
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void main(void)
{
srand(23);
CBigInt x("+123");
x.display();
CBigInt y("-123");
y.display();
CBigInt z("-1-3");
z.display();
//test_add1();
//test_length();
//test_ConstructorInt();
//test_subtract1();
//test_ConstructorRandomPos();
//test_ConstructorOne();
}
CBigInt::CBigInt(int x)
/*
Description:
a constructor using an integer value
Example:
CBigInt bob(23); => bob = "+0000...00000000023"
CBigInt t(-52); => t ="-0000...00000000052"
Algorithm0:
initialize
get the sign
break x into the digits and put them in digits[]
Algorithm1:
initialize
if x < 0 then
set sign to -ve
x = -x
end if
//break x into the digits and put them in digits[]
//divide x by 10 repeatedly while saving the remainder right to left
i = MAX_DIGITS - 1
while (x>0)
rem = x % BASE
quo = x / BASE
digits[i] = rem
i--
x = quo
end while
Source:
Output:
*/
{
initialize();
if (x < 0)
{
_sign = '-';
x = -x;
}
int i = MAX_DIGITS - 1;
int rem, quo;
while (x>0)
{
rem = x % BASE;
quo = x / BASE;
_digits[i] = rem + '0';
i--;
x = quo;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_ConstructorInt(void)
{
cout << "-------------------------\n";
cout << "test_ConstructorInt\n";
cout << "-------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int x = rand();
if (rand()%2==0)
x = -x;
CBigInt a(x);
cout << "x = " << x << endl;
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
cout << "a.length() = " << a.length() << endl;
cout << endl;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
int CBigInt::length(void)
/*
Description:
returns the lenght excluding leading zeros
Example:
a = +00000000000000000000000000000000000000000000000047[10]
=> 2
a = +00000000000000000000000000000000000000000000000009[10]
=> 1
Algorithm0:
given: MAX_LENGTH, number
find the leading non-zero digit
starting at that point going all the way to righmost
count all the digits
Algorithm1:
count the leading zeros in MAX_DIGITS-1 and put it in countLeadingZeros
return MAX_DIGITS-countLeadingZeros
Algorithm2:
countLeadingZeros = 0
for i=0 to MAX_DIGITS-2
if digits[i] == '0' then
countLeadingZeros++
else
break
end if
end for
return MAX_DIGITS-countLeadingZeros
Source:
Output:
-------------------------
test_length
-------------------------
a = +00000000000000000000000000000000000000000000000000[10]
a = +0
a.length() = 1
a = +00000000000000000000000000000000000000000000000001[10]
a = +1
a.length() = 1
a = -00000000000000000000000000000000000000000009458450[10]
a = -9458450
a.length() = 7
a = +00000000000000000000000000000000000000000000000064[10]
a = +64
a.length() = 2
a = +00000000000000000000000000000032232573896284895161[10]
a = +32232573896284895161
a.length() = 20
a = -00000000000000000000000000000000000000000953448193[10]
a = -953448193
a.length() = 9
a = -03113040230371410675125010486802116715270020734397[10]
a = -3113040230371410675125010486802116715270020734397
a.length() = 49
a = +00008227035706975055837701807614572323831934591755[10]
a = +8227035706975055837701807614572323831934591755
a.length() = 46
a = -00000000000000000000000000000000000000000000328747[10]
a = -328747
a.length() = 6
a = -00000000000828071096675834086625234979410594268041[10]
a = -828071096675834086625234979410594268041
a.length() = 39
a = -00000000000000069316251219604479814570312850495846[10]
a = -69316251219604479814570312850495846
a.length() = 35
a = +00000000000000000000000000019701727586253849900959[10]
a = +19701727586253849900959
a.length() = 23
Press any key to continue
*/
{
/*
int countLeadingZeros = 0;
for (int i=0; i<=MAX_DIGITS-2; i++)
if (_digits[i] == '0')
countLeadingZeros++;
else
break;
return MAX_DIGITS-countLeadingZeros;
*/
for (int i=0; i<=MAX_DIGITS-2; i++)
if (_digits[i] != '0')
return MAX_DIGITS-i;
return 1;
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_length(void)
{
cout << "-------------------------\n";
cout << "test_length\n";
cout << "-------------------------\n";
{
CBigInt a;
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
cout << "a.length() = " << a.length() << endl;
cout << endl;
}
{
CBigInt a('u');
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
cout << "a.length() = " << a.length() << endl;
cout << endl;
}
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('r');
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
cout << "a.length() = " << a.length() << endl;
cout << endl;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
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()%MAX_DIGITS +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()%MAX_DIGITS +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()%MAX_DIGITS +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, xx("+123"), yy(123);
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:
length of a should be <= MAX_DIGITS
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 (strlen(s) > MAX_DIGITS)
return false;
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();
}
/*
*/
|