PART 1 - INTRODUCTION

Integer arithmetic in C++ is limited by the number of bits used to represent integers. For many applications (banking etc), the primitive integer-like types in C++ are sufficient but for others (cryptography, combinatorics) they are woe- fully inadequate. Consider the following table showing the ranges of values available to the various C++ integer-like types1 :

Type	sizeof(type)	Max Value
uint8_t	1	255
unsigned short	2	65,535
unsigned int	4	4,294,967,295
unsigned long long int	8	18,446,744,073,709,551,615

While it seems like long long int should be large enough for most practical applications it only supports numbers up to about 20 digits whereas the typical values used in cryptographic applications are hundreds of digits long. Using floating point types like double will not fix this situation because doubles have limited precision (about 15 digits) and limited range (10308, typically). Our solution to this problem is to create a bigint data type that supports an arbitrary number of digits.

Consider the following program: #include

using namespace std ;

unsigned long long factorial ( int n) { unsigned long long answer = 1;

for(int i=2; i <= n; i++) answer = i; return answer ;

}

int main() { int n;

cout << Enter n: ; cin >> n; cout << n << ! is << factorial(n) << endl;

}

Heres a sample session running this program:

name@emaildomain Lab5 $ ./bad_factorial Enter n: 5 5! is 120 name@emaildomain Lab5 $ !! ./bad_factorial 

Enter n: 10 10! is 3628800 email@emaildomain Lab5 $ !! ./bad_factorial Enter n: 20 20! is 2432902008176640000 email@emaildomain Lab5 $ !! ./bad_factorial 

Enter n: 30 30! is 9682165104862298112 email@emaildomain Lab5 $ !! ./bad_factorial 

Enter n: 40 40! is 18376134811363311616 

Note that 30! = 265252859812191058636308480000000 so this program is silently computing incorrect results. With our bigint data type this program will work correctly even for large values of n (I verified that I can compute 10, 000! without breaking a sweat and 100, 000! works fine as well but takes a little while to print).

PART 2 - FILES

You should create files for a class (bigint) and unit tests (bigint tests). No demo will be needed for this lab.

PART 3 - UNIT TESTS

Try to force yourself to work test first through this class. That is, write a test, verify that it fails, make it pass. Dont write code in your bigint class until you have a test that needs it. See section 8 below for some examples of tests and some help getting started on this lab.