//file CBigInt029.cpp
//date 04/20/2005
//author aou
//csis250.tripod.com
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
/* Project #05
Date Assigned: 04/08/2005, Date Due: 04/13/2005
Complete/implement the following functions (assume positive ints):
CBigInt operator *(CBigInt b);
void test_operator_multiply(void);
Submit the printed problem description, examples (2), algorithms,
source code, and the output produced by the test function
-----------------
SAMPLE OUTPUT
-----------------
i1 = 41
i2 = 18467
m = 757147
a = +00000000000000000000000000000000000000000000000041[10]
b = +00000000000000000000000000000000000000000000018467[10]
c = +00000000000000000000000000000000000000000000757147[10]
i1 = 6334
i2 = 26500
m = 167851000
a = +00000000000000000000000000000000000000000000006334[10]
b = +00000000000000000000000000000000000000000000026500[10]
c = +00000000000000000000000000000000000000000167851000[10]
a = -00001397724783114332134597298167586122324167251171[10]
b = +00000000000000000000000000000000000000000000027529[10]
c = -38477965554354449333329021255478361462000257486459[10]
a = +00000000000000000000000000000000016009056842068205[10]
b = +00000000000000000000000000000000000000000000024393[10]
c = +00000000000000000000000000000390508923548569724565[10]
a = +00000000000000000048438699015694370173838778088934[10]
b = -00000000008524216851870982822798918608808347333552[10]
c = -##################################################[10]
a = +00000000000000000000000000000000000009112816429356[10]
b = -00000000000000000000000149227768525235918193002592[10]
c = -00000000001359885260732904062005078000093892890752[10]
a = +00000730252830378770392444447521857882436950443929[10]
b = +41386128465945400576013500430704622215352311234357[10]
c = +##################################################[10]
Press any key to continue
*/
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
/*
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 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 add1(CBigInt a, CBigInt b, CBigInt &c);
CBigInt add(CBigInt a, CBigInt b);
void add(CBigInt a);
friend void add1(CBigInt a, CBigInt b, CBigInt &c);
friend CBigInt add1(CBigInt a, CBigInt b);
CBigInt add1(CBigInt b);
CBigInt operator +(CBigInt b);
bool operator == (CBigInt b);
bool operator != (CBigInt b);
CBigInt operator *(CBigInt b);
CBigInt(const CBigInt &bi);
CBigInt & operator = (const CBigInt &b);
friend ostream & operator << (ostream & bob, const CBigInt & b);
};
/*
Possible Add functions
friend void add(CBigInt a, CBigInt b, CBigInt &c) | add(x, y, z); //z=x+y
member void add(CBigInt a, CBigInt b, CBigInt &c) | t.add(x, y, z);//z=x+y
member void add(CBigInt a, CBigInt b) | z.add(x, y); //z=x+y
member CBigInt add(CBigInt a) | z = x.add(y) //z=x+y
member CBigInt operator +(CBigInt a) | z = x+y //z=x+y
*/
/*
Possible Multiplication functions
member CBigInt operator *(CBigInt a) | z = x*y //z=x*y
*/
///////////////////////////////////////////////////////////
// test functions
///////////////////////////////////////////////////////////
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 test_global_add1(void);
void test_global_returning_add1(void);
void test_member_returning_add1(void);
void test_operator_add(void);
void test_operator_equal(void);
void test_operator_notequal(void);
void test_operator_multiply(void);
void test_ConstructorCopy(void);
void test_operator_assign(void);
void test_pointers(void);
///////////////////////////////////////////////////////////
// global functions
///////////////////////////////////////////////////////////
void add1(CBigInt a, CBigInt b, CBigInt &c);
CBigInt add1(CBigInt a, CBigInt b);
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void main(void)
{
test_pointers();
/*
CBigInt a('r'), b('r');
a.displayMinimized();
b.displayMinimized();
cout << "a=" << a << ", b=" << b << endl;
*/
//test_operator_assign();
//test_ConstructorCopy();
//test_operator_multiply();
//test_operator_notequal();
//test_operator_equal();
//test_operator_add();
//test_member_returning_add1();
//test_global_returning_add1();
//test_global_add1();
//test_add1();
//test_length();
//test_ConstructorInt();
//test_subtract1();
//test_ConstructorRandomPos();
//test_ConstructorOne();
}
void test_pointers(void)
{
cout << "-------------\n";
cout << "test_pointers\n";
cout << "-------------\n";
CBigInt a('r');
a.display();
CBigInt *p;
p = &a;
(*p).display();
p->display();
cout << p << endl;
cout << endl;
a = 4;
a.display();
(*p).display();
p->display();
cout << p << endl;
cout << sizeof(p) << endl;
cout << sizeof(a) << endl;
cout << endl;
*p = 5;
a.display();
(*p).display();
p->display();
cout << p << endl;
cout << sizeof(p) << endl;
cout << sizeof(a) << endl;
int *ip;
int ia=3;
ip = &ia;
cout << ip << endl;
cout << sizeof(ip) << endl;
cout << sizeof(ia) << endl;
}
ostream & operator << (ostream & bob, const CBigInt & b)
{
bob << b._sign;
int nz = MAX_DIGITS-1;
for (int i=0; i<=MAX_DIGITS-2; i++)
if (b._digits[i] != '0')
{
nz = i;
break;
}
for (i=nz; i<=MAX_DIGITS-1; i++)
bob << b._digits[i];
return bob;
}
CBigInt & CBigInt::operator =(const CBigInt &b)
{
_base = b._base;
_sign = b._sign;
for (int i=0; i<=MAX_DIGITS-1; i++)
_digits[i] = b._digits[i];
return *this;
}
void test_operator_assign(void)
{
cout << "-------------------\n";
cout << "test_operator_assign\n";
cout << "-------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('r');
CBigInt b('r');
CBigInt c('r');
cout << "a = "; a.displayMinimized();
cout << "b = "; b.displayMinimized();
cout << "c = "; c.displayMinimized();
a = b = c;
cout << "After a = b = c;\n";
cout << "a = "; a.displayMinimized();
cout << "b = "; b.displayMinimized();
cout << "c = "; c.displayMinimized();
cout << "-----------------------------\n";
}
}
CBigInt::CBigInt(const CBigInt &bi)
{
cout << "Copy constructor was called\n";
_base = bi._base;
_sign = bi._sign;
for (int i=0; i<=MAX_DIGITS-1; i++)
_digits[i] = bi._digits[i];
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
CBigInt CBigInt::operator *(CBigInt b)
/*
Description: multiply, overload *
Example: c=a*b;
Algorithm0:
ta = a (a is *this)
sum=0
for each digit d from right to left in the biginteger b
tp = ta * d (using a loop)
sum = sum + tp
shift ta one digit to left (adding 0 to right)
end for
Algorithm1:
ta = a (*this)
sum=0
for i=MAX_DIGITS-1 to 0 step -1
db = b.digits[i]-'0'
//tp = ta * db (using a loop)
tp = 0
carry = 0
for j=MAX_DIGITS-1 to 0 step -1
dta = ta.digits[j]-'0'
dtp = dta*db + carry
carry = dtp/BASE
dtp = dtp%BASE
tp.digit[j] = dtp + '0'
next j
if carry > 0 then
fill sum with '#' characters and exit function
sum = sum + tp //already overloaded
//shift ta one digit to left (adding 0 to right)
for k=0 to MAX_DIGITS-2
ta.digits[k] = ta.digits[k+1]
next k
ta.digits[MAX_DIGITS-1] = '0'
next i
//set sign of sum
if (sign of a is not equal to sign of b) then
set sign of sum to -ve
return sum
Source:
Output:
*/
{
CBigInt sum(0);
return sum;
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_operator_multiply(void)
{
cout << "-----------------\n";
cout << "test_operator_multiply\n";
cout << "-----------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int i1 = rand();
int i2 = rand();
int m = i1 * i2;
cout << "i1 = " << i1 << endl;
cout << "i2 = " << i2 << endl;
cout << "m = " << m << endl;
cout << endl;
CBigInt a(i1), b(i2), c;
cout << "a = "; a.display();
cout << "b = "; b.display();
c = a*b; // c = a.add1(b);
//c = a.operator * (b);
cout << "c = "; c.display();
cout << endl;
}
for (i=1; i<=TEST_COUNT; i++)
{
CBigInt a('r'), b(rand()), c;
cout << "a = "; a.display();
cout << "b = "; b.display();
c = a*b; //
cout << "c = "; c.display();
cout << endl;
}
for (i=1; i<=TEST_COUNT; i++)
{
CBigInt a('r'), b('r'), c;
cout << "a = "; a.display();
cout << "b = "; b.display();
c = a*b; //
cout << "c = "; c.display();
cout << endl;
}
}
bool CBigInt::operator !=(CBigInt b)
{
return !(*this == b);
/*
if (b == *this)
return false;
else
return true;
*/
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_operator_notequal(void)
{
cout << "-----------------\n";
cout << "test_operator_notequal\n";
cout << "-----------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('r'), b('r');
cout << "a = "; a.display();
cout << "b = "; b.display();
if (a != b)
cout << "a and b are NOT equal\n";
else
cout << "a and b are equal\n";
cout << endl;
a = b;
cout << "a = "; a.display();
cout << "b = "; b.display();
if (a != b)
cout << "a and b are NOT equal\n";
else
cout << "a and b are equal\n";
cout << endl;
}
}
bool CBigInt::operator ==(CBigInt b)
{
if (_base != b._base) return false;
if (_sign != b._sign) return false;
for (int i= 0; i<=MAX_DIGITS-1; i++)
if (_digits[i] != b._digits[i]) return false;
return true;
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_operator_equal(void)
{
cout << "-----------------\n";
cout << "test_operator_equal\n";
cout << "-----------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('r'), b('r');
cout << "a = "; a.display();
cout << "b = "; b.display();
if (a == b)
cout << "a and b are equal\n";
else
cout << "a and b are NOT equal\n";
cout << endl;
a = b;
cout << "a = "; a.display();
cout << "b = "; b.display();
if (a == b)
cout << "a and b are equal\n";
else
cout << "a and b are NOT equal\n";
cout << endl;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
CBigInt CBigInt::operator +(CBigInt b)
{
CBigInt c;
int carry = 0;
for (int i= MAX_DIGITS-1; i>=0; i--)
{
int ad = _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;
}
return c;
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_operator_add(void)
{
cout << "-----------------\n";
cout << "test_operator_add\n";
cout << "-----------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int i1 = rand();
int i2 = rand();
int s = i1 + i2;
cout << "i1 = " << i1 << endl;
cout << "i2 = " << i2 << endl;
cout << "s = " << s << endl;
cout << endl;
CBigInt a(i1), b(i2), c;
cout << "a = "; a.displayMinimized();
cout << "b = "; b.displayMinimized();
c = a+b; // c = a.add1(b);
c = a.operator + (b);
cout << "c = "; c.displayMinimized();
cout << endl;
}
for (i=1; i<=TEST_COUNT; i++)
{
CBigInt a('+'), b('+'), c;
cout << "a = "; a.display();
cout << "b = "; b.display();
c = a+b; // c = a.add1(b);
cout << "c = "; c.display();
cout << endl;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
CBigInt CBigInt::add1(CBigInt b)
{
CBigInt c;
int carry = 0;
for (int i= MAX_DIGITS-1; i>=0; i--)
{
int ad = _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;
}
return c;
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_member_returning_add1(void)
{
cout << "-------------------------\n";
cout << "test_member_returning_add1\n";
cout << "-------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('+'), b('+'), c;
cout << "a = "; a.display();
cout << "b = "; b.display();
c = a.add1(b); // c = a+b;
cout << "c = "; c.display();
cout << endl;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
CBigInt add1(CBigInt a, CBigInt b)
{
CBigInt c;
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;
}
return c;
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_global_returning_add1(void)
{
cout << "-------------------------\n";
cout << "test_global_returning_add1\n";
cout << "-------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('+'), b('+'), c;
cout << "a = "; a.display();
cout << "b = "; b.display();
c = add1(a, b);
cout << "c = "; c.display();
cout << endl;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void add1(CBigInt a, CBigInt b, CBigInt &c)
{
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_global_add1(void)
{
cout << "-------------------------\n";
cout << "test_global_add1\n";
cout << "-------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt a('+'), b('+'), c;
cout << "a = "; a.display();
cout << "b = "; b.display();
add1(a,b,c);
cout << "c = "; c.display();
cout << endl;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
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 << (*this)._sign;
//cout << this->_sign;
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();
}
/*
*/
|