** NOTE: PLEASE ANSWER PART 4 THRU 9. MY ANSWER FOR PART 1 THRU 3 IS ILLUSTRATED, BELOW, FOR REFERENCE! **

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.

Factorial.cpp

#include using namespace std; #include "BigInt.h" int main() { int sym; for (;;) { cout << " Enter n: "; cin >> sym; if (sym < 0) break; BigInt fact(1); for (int i = 2; i <= sym; i++) fact = BigInt(i) * fact; cout << sym << "! is" << fact << endl; }

system("pause"); return 0; }

BigInt.h

#pragma once #include #include #include #include

#ifndef BIGINT #define BIGINT

const int dig = 3, mod_val = (short int)pow(10.0, dig);

class BigInt { public: BigInt() { }

BigInt(int n);

void read_num(istream & in);

void display_num(ostream & out) const; BigInt operator+(BigInt int2); bool operator==(BigInt int2); BigInt operator*(BigInt int2);

private: list order; };

inline BigInt::BigInt(int n) { do { order.push_front(n % mod_val); n /= mod_val; } while (n > 0); }

inline istream & operator>>(istream & in, BigInt & num) { num.read_num(in); return in; }

inline ostream & operator<<(ostream & out, const BigInt & num) { num.display_num(out); return out; }

inline bool BigInt::operator==(BigInt int2) { return order == int2.order; }

#endif

BigInt.cpp:

#include using namespace std; #include "BigInt.h"

void BigInt::read_num(istream & in) { static bool guide = true; if (guide) { guide = false; } short int set; for (;;) { in >> set; if (set < 0) return;

if (set >= mod_val) cerr << "Illegal block -- " << set << " -- ignoring "; else order.push_back(set); } }

void BigInt::display_num(ostream & out) const { int count = 0; const int line = 20;

for (list::const_iterator it = order.begin(); ; ) { out << setfill('0'); if (count == 0) out << setfill(' ');

if (it == order.end()) return;

out << setw(3) << *it; count++;

it++; if (it != order.end()) { out << ','; if (count > 0 && count % line == 0) out << endl; } } }

BigInt BigInt::operator+(BigInt int2) { BigInt add; short int one, two, fin, bal = 0;

list::reverse_iterator iter = order.rbegin(), iter2 = int2.order.rbegin();

while (iter != order.rend() || iter2 != int2.order.rend()) { if (iter != order.rend()) { one = *iter; iter++; } else one = 0; if (iter2 != int2.order.rend()) { two = *iter2; iter2++; } else two = 0;

short int dec = one + two + bal; fin = dec % mod_val; bal = dec / mod_val; add.order.push_front(fin); }

if (bal > 0) add.order.push_front(bal);

return add; }

BigInt BigInt::operator*(BigInt int2) { BigInt val_zero = BigInt(0); if ((*this) == val_zero || int2 == val_zero) return val_zero;

BigInt Res, sum_z, partial;

short int one, two, fin, bal = 0;

for (list::reverse_iterator iter2 = int2.order.rbegin(); iter2 != int2.order.rend(); iter2++) { bal = 0; two = *iter2; partial = sum_z;

for (list::reverse_iterator iter = order.rbegin(); iter != order.rend(); iter++) { one = *iter;

unsigned dec = one * two + bal; fin = dec % mod_val; bal = dec / mod_val;

partial.order.push_front(fin); } if (bal > 0) partial.order.push_front(bal);

Res = Res + partial;

sum_z.order.push_back(0);

}

return Res; }

**** PART 4 - PROBLEM OVERVIEW ****

In this lab you will create a class bigint that supports integers of arbitrary size (limited only by computer memory constraints). A simple way to represent a bigint is to use an array of base-10 digits. We will store the digits from least significant to most significant so, for example, the number 5, 912 would be stored in an array as

2

1

9

5

(so that the 2 is at index 0, 9 is at index 1 and so on).

PART 5 - INSTANCE VARIABLES

Your class should have the following instance variables (see bag2.h and bag2.cxx from CH 4 in textbook):

(1) uint8_t * digits - Pointer to base of dynamically allocated array

(2) size_t capacity - # of digits allocated in digits array

(3) size_t used - # of digits actually being used

(4) bool negative - True if this # is negative, False otherwise

Note: If you're using a C++ 2011 compliant compiler you'll need to include cstdlib to get uint8_t. If you're using an older compiler youll need to add typedef unsigned char uint8 t; to your header file.

PART 6- METHODS & FUNCTIONS

Your class must support (in no particular order):

 bigint (long long l = 0) - Create a bigint equal to the long long value l. Default to 0.  bigint (uint8 t d [], size t ndigits , bool is negative)  Construct bigint from array of digits from lowest to highest significance. That is d[0] is the one's place, d[1] is the ten's place and so on.  bigint (const bigint & other) - A copy constructor   bigint () - A destructor  bigint negate () const - Return the bigint that is the negative of this one  size_t get_digit_count () const - Return the number of digits in this number.  uint8_t get_digit (size_t i) const - Return the i-th digit of this number (i = 0 would be least significant digit)  bool is_negative () const - Return True if this # is negative, False otherwise  bigint abs () const - Return a bigint that is the absolute value of this one  bool operator < (const bigint & i1, const bigint & i2)  True if & only if i1 < i2  bool operator ==(const bigint & i1, const bigint & i2)  void operator += (const bigint & other)  Member function  void operator *= (const bigint & other)  Member function  void operator = (const bigint& other)  Member function  void operator =(const bigint & other)  Member function  bigint operator +(const bigint &i1, const bigint &i2)  bigint operator (const bigint &i1, const bigint &i2)  bigint operator *(const bigint&i1, const bigint&i2)  ostream & operator <<(ostream& out, const bigint & i) You may use member- or free-functions for your operators as you see fit but the signatures given above follow your books conventions.  

PART 7 - SOME HELP

We havent covered some of the methods on the list above. Below are implementations of a few of them (assuming that you have properly created and used the i-vars listed above).

bigint :: bigint(const bigint& other) {

digits = new uint8 t[other.capacity];

capacity = other . capacity ;

used = other . used

negative = other . negative ;

for(size_t i=0; i < other.used; i++) digits [ i ] = other.digits [ i ];

}

bigint :: bigint( ) {

delete [ ] digits ;

}

void bigint :: operator =(const bigint& other ) {

uint8_t new digits ;

// Check for possible selfassignment:

if (this == &other)

return ;

// If needed , allocate an array with a different size:

if ( capacity != other . capacity ) {

new digits = new uint8_t [ other . capacity ];

delete [ ] digits ;

digits = new digits ;

capacity = other . capacity ;

}

// Copy digits from the other array:

used = other . used ;

negative = other . negative ;

for(size_t i = 0; i < other.used; i++) digits [ i ] = other.digits [ i ]; }

PART 8 - MORE ABOUT TESTS

You should make sure that your methods are working correctly under non-exceptional circumstances. Some examples are:

// requires array constructor

TESTCASE(array constructor should not cause error, [bigint]) {

uint8_t input [ ] = {2, 1, 9, 5};

bigint v1(input, 4, false); bigint v2(input, 4, true);

}

// requires array constructor , get digit count , is negative and get digit

TESTCASE(array constructor should create correct digits, [bigint]) {

uint8_t input [ ] = {2, 1, 9, 5}; bigint value(input , 4, false );

REQUIRE( value . get_digit_count () == 4);

REQUIRE( value . is_negative () == false );

REQUIRE(value.get_digit(0) == 2);

REQUIRE(value.get_digit(1) == 1);

REQUIRE(value.get_digit(2) == 9);

REQUIRE(value.get_digit(3) == 5);

}

// requires long constructor , get digit count , is negative and get digit

TESTCASE(long constructor should create correct digits, [bigint]) {

bigint value (73421);

REQUIRE( value . get_digit_count () == 5);

REQUIRE( value . is_negative () == false );

REQUIRE(value.get_digit(0) == 1);

REQUIRE(value.get_digit(1) == 2);

REQUIRE(value.get_digit(2) == 4);

REQUIRE(value.get_digit(3) == 3);

REQUIRE(value.get_digit(4) == 7);

}

// requires long constructor , get digit count , is negative and get digit

TESTCASE(long constructor should use correct sign, [bigint]) {

bigint value(384591);

REQUIRE( value . get_digit_count () == 6);

REQUIRE(value.is_negative() == true);

REQUIRE(value.get_digit(0) == 1);

REQUIRE(value.get_digit(1) == 9);

REQUIRE(value.get_digit(2) == 5);

REQUIRE(value.get_digit(3) == 4);

REQUIRE(value.get_digit(4) == 8);

REQUIRE(value.get_digit(5) == 3);

}

Be sure to check things like carrying, borrowing etc (99999 + 1 is a recipe for a good test case, for example).

TEST CASE(add multiple digits no carry should add columns , [ bigint ]) {

bigint v1(15); bigint v2(12);

REQUIRE(v1+v2 == 27); // Note: 27 is coverted to bigint using long long constructor

}

TESTCASE(add carries into empty digit, [bigint]) {

bigint v1(9);

bigint v2(3); REQUIRE(v1+v2 == 12); // Note: 12 is coverted to bigint using long long constructor

}

TESTCASE(add carries across multiple digits, [bigint]) {

bigint v1(95);

bigint v2(38); REQUIRE(v1+v2 == 133); // note: 133 is coverted to bigint Using long long constructor

}

You also need to test more subtle things like making sure that the bigint array constructor copies the array rather than retaining a pointer to it:

TEST CASE(array constructor should copy array , [ bigint ]) {

uint8_t input [ ] = {2, 1, 9, 5}; bigint value(input , 4, false ); // change the arraY

input [0] = 7;

// this change should have had no impact on the bigint

REQUIRE(value.get digit(0) == 2);

}

and similarly for the copy constructor

TEST CASE(copy constructor should copy array , [ bigint ]) {

uint8_t input [ ] = {2, 1, 9, 5}; bigint v1(input , 4);

bigint v2(v1); // change v1

v1 += 9; // this change should have had no impact on v2

REQUIRE(v2. get_digit (0) == 2);

}

There should be several other tests of this form.

When you believe multiplication is working well, a nice performance test is to rewrite the factorial function so that it uses bigint -s rather than long long-s. Included with this lab are two files:

1000 factorial.txt

10000 factorial.txt

containing the corresponding numbers. Write unit tests that check the digits in these numbers against your computed factorials.

PART 9 - EXTRA CREDIT

For extra credit 2 points (each) you can implement that division and modulus operators. These operators must be efficient (able to take the quotient 10000!/19 in sub-second time, for example). That is, you cannot perform division by repeated subtraction.