Chapter 14 Exercise Set 1: BigInt Case Study¶

This exercise set is a case study inspired by the Large Integer Case Study in C++ that was part of the AP Computer Computer Science A curriculum from 1994 to 1999.

So as we are now beginning to understand, when we want to write new software, the first thing to do is to write a test! We’ll get you started by walking you through the first test case.

Note

If you successfully completed Chapter 13 Exercise Set 1: Introducing Make, you can use the following Makefile (after moving your source code to a src subdirectory) to continue using Make here:

CC=g++
STD=c++11

build/%.o: src/%.cpp
	@mkdir -p build
	@$(CC) -MM -MT $@ $< > build/$*.d
	$(CC) -c -o $@ $< -std=$(STD)

build/test_bigints: build/test_bigints.o build/BigInt.o
	$(CC) -o $@ $^ -std=$(STD)

-include build/*.d

.PHONY: test all clean

test: build/test_bigints
	./build/test_bigints

clean:
	rm -rf build

You can then run make test to build and run the tests, and make clean to remove the build directory. Don’t forget to add build to your .gitignore file, by the way!

Create a file named test_bigints.cpp with the following:

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include <doctest.h>
#include <string>
#include "BigInt.h"
using namespace std;

TEST_CASE("Test can create and render BigInts") {
    BigInt bi;
    CHECK(bi.to_string() == "0");
    BigInt bi2(42);
    CHECK(bi2.to_string() == "42");
    BigInt bi3(-42);
    CHECK(bi3.to_string() == "-42");
    BigInt bi4("123456789012345678901234567890");
    CHECK(bi4.to_string() == "123456789012345678901234567890");
    BigInt bi5("-923456789012345678901234567890");
    CHECK(bi5.to_string() == "-923456789012345678901234567890");
}

These tests require us to create three contructors - one taking no arguments, one taking an integer argument, and a third taking a string - and a member function to render a BigInt as a string.

The largest signed 64 bit integer value is 9223372036854775807 and the largest unsigned 64 bit integer value is 18446744073709551615, which has 20 decimal digits. By writing a test for our third constructor for a BigInt with 30 digits, we are starting out handling a number that can not be stored in a C++ int.

Create a header file named BigInt.h with the following:

#include <string>
using namespace std;

class BigInt
{
    bool negative;
    string digits;

    public:
    // constructors
    BigInt();
    BigInt(int);
    BigInt(string);

    // member functions
    string to_string() const;
};

and a source file named BigInt.cpp with the following implementations of each of the required functions:

#include <iostream>
#include <string>
#include "BigInt.h"
using namespace std;

BigInt::BigInt()
{
    negative = false;
    digits = "0";
}

BigInt::BigInt(int i)
{
    negative = (i >= 0) ? false : true;
    digits = (i >= 0) ? std::to_string(i) : std::to_string(-i);
}

BigInt::BigInt(string n)
{
    negative = (n.front() == '-') ? true: false;
    digits = (n.front() == '-') ? n.substr(1, n.size() - 1) : n;
}

string BigInt::to_string() const
{
    return (!negative) ? digits : "-" + digits;
}

You should now be able to compile and run the tests, and they should pass.

Now that we can create and display BigInts, let’s compare them, starting with equality.

TEST_CASE("Test can compare BigInts for equality") {
    BigInt i1("12345");
    BigInt i2("54321");
    BigInt i3("123456");
    BigInt i4("-654321");
    BigInt i5("54321");
    BigInt i6("-54321");
    CHECK((i2 == i5) == true);
    CHECK((i1 == i2) == false);
    CHECK((i1 == i3) == false);
    CHECK((i2 == i6) == false);
}

Now let’s add inequality.

TEST_CASE("Test can compare BigInts for inequality") {
    BigInt i1("12345");
    BigInt i2("54321");
    BigInt i3("123456");
    BigInt i4("-654321");
    BigInt i5("54321");
    BigInt i6("-54321");
    CHECK((i2 > i5) == false);
    CHECK((i2 > i1) == true);
    CHECK((i4 > i1) == false);
    CHECK((i6 > i4) == true);
}

Add tests for !=, <=, <, and <=, and then add the functions to make the tests pass.

Here is where the real fun begins. We’ll add tests to use the + operator with BigInts.

TEST_CASE("Test can add BigInts") {
    BigInt i1("123");
    BigInt i2("321");
    BigInt i3("43210");
    BigInt i4("9999");
    BigInt i5("1");
    CHECK((i1 + i2).to_string() == "444");
    CHECK((i1 + i3).to_string() == "43333");
}