Assignment 1: Very Large Integers¶

In this assignment, your task is to implement a class called Natural that can add and multiply non-negative integers (natural numbers) with hundreds of digits, or more.

Arithmetic with such big numbers is actually quite useful in applications such as cryptography. It’s possible to implement big number arithmetic very efficiently using clever, polished algorithms. However, for this assignment, it’s best to mimic the algorithms you learned in school for doing arithmetic.

The file Natural.h is provided for you below, and contains stubs of all the functions you need to implement. You should also create a file called, say, natural_test.cpp that #includes Natural.h and contains testing functions, e.g.:

// natural_test.cpp

#include "Natural.h"
// ... other #includes ...

// ... other helper functions for testing and development ...

int main() {
    test1();
    test2();
    test3();
    // ...
}

When the marker marks your code, they will #include Natural.h into their own natural_test.cpp with their own test function.

Example Code¶

Here’s a function you can put in natural_test.cpp to help test your code:

void factorial_test() {
    Natural result{1};
    for(int i = 0; i < 1000; i++) {
        result = result + result * Natural(i);
    }
    cout << result << "\n";
}

This calculates and prints 1000!. On an ordinary modern computer, and using -O2 optimization (see below), calculating 1000! should take around 10 seconds or less. If your program is slower than this, then you should try to make it faster.

What to Submit¶

On Canvas, submit just your Natural.h file that contains all your code needed to use your Natural class. The marker will #include this file into their own testing program with its own main().

You can assume that cmpt_error.h will be in the same folder, and so you can (should!) use it.

See Canvas for the due date and details of the marking scheme.

Please note that if you’re program doesn’t compile, or does not follow the rules of this assignment, then you will get 0.

Advice¶

Use the “by hand” algorithms for addition and multiplication you learned in elementary school. It’s not worth the effort to use more sophisticated algorithms for this assignment.
You can add any other helper methods and functions you need for your program.
Testing is an important part of a making sure a program like this works correctly. Here are some suggestions:
- Use automated testing! Don’t check test by hand: you’ll soon get bored of it, and make mistakes and skip tests.
  
  For example, here is a testing function you could use for checking multiplication:
```
void test_mult(const string& sa,
               const string& sb,
               const string& expected)
{
    Natural a{sa}, b{sb};
    Natural actual = a * b;
    cout << a << " * " << b << " == " << actual
         << " (expected " << expected << ")\n";
    assert(actual.to_string() == expected);
}
```
  For example, this statement will check that 12 times 11 is 132:
```
test_mult("12", "11", "132");
```
  If Natural doesn’t return the correct result, then test_mult will fail, and then you can trace your code with this example.
- Values near a boundary are often good tests for finding bugs. For example:
```
test_mult("0", "0", "0");
test_mult("1", "0", "0");
test_mult("0", "1", "0");
test_mult("1", "1", "1");
test_mult("2", "11", "22");
test_mult("11", "2", "22");
```
- When you are developing your program, use a few small test cases that are easy to check. Then after you are sure those work, test your program with bigger numbers.
- When you discover a test case that fails, try to reduce it to smaller numbers that also fail. This makes it easier to understand and trace the failure.
- The bc Linux command-line calculator is an easy way to test basic arithmetic of big numbers, e.g.:
```
$ bc
...

452734859743578 * 5458947859375389754
2471455993461822439725868248499812

(ctrl-d to exit)
```
  Python also supports arithmetic with big numbers, e.g.:
```
$ python

...

>>> 2 ** 1000
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376L
```
  ** is the exponentiation operator in Python, so 2 ** 1000 calculates $2^{`1000}$. Notice that Python 2 puts an L on the end of very large integers, so be sure to not include that if you are cutting-and-pasting these numbers for testing. Or, you could use Python 3, which never prints the L.
  
  Here’s a one-line Python expression for calculating factorials:
```
>>> reduce(lambda i,j : i*j, range(1,1000+1))
# ... big number ...
```
  Replace with 1000 with the integer you want the factorial of.
You can probably speed up your program using the -O3 optimization flag for g++. For example, our reference implementation of Natural calculated 1000! in about 8.5 seconds using -O3, and 54 seconds without it.

General Advice¶

Don’t put a main function in Natural.h — that will cause it to fail to when it is marked!
If you compile your program with the -B option, make will re-compile your code every time, e.g.:
```
$ make -B natural_test
```
If natural_test.cpp includes Natural.h, then calling just make natural_test.cpp will not re-compile natural_test.cpp if you’ve only made changes to Natural.h.
Use valgrind to help ensure your program has no memory leaks, e.g.:
```
$ make -B natural_test

$ valgrind ./natural_test

// ... lots of output ...
```
A program is considered to have no memory leaks or problems if:
- In the LEAK SUMMARY, definitely lost, indirectly lost, and possibly lost must all be 0.
- The ERROR SUMMARY must report 0 errors.
- It is usually okay if still reachable reports a non-zero number of bytes.
Use only new and delete to allocate and de-allocate memory. Do not use malloc and free.
Do not use C++ smart pointers, such as unique_ptr or shared_ptr. Stick to raw pointers, and use new and delete (or delete[]) and constructors/destructors (plus valgrind) to manage memory.

Natural.h¶

As described in the instructions above, use the following as the start of your own Natural.h file:

// Natural.h

/////////////////////////////////////////////////////////////////////////
//
// Student Info
// ------------
//
// Name : <put your full name here!>
// St.# : <put your full SFU student number here>
// Email: <put your SFU email address here>
//
//
// Statement of Originality
// ------------------------
//
// All the code and comments below are my own original work. For any non-
// original work, I have provided citations in the comments with enough detail
// so that someone can see the exact source and extent of the borrowed work.
//
// In addition, I have not shared this work with anyone else, and I have not
// seen solutions from other students, tutors, websites, books, etc.
//
/////////////////////////////////////////////////////////////////////////


/////////////////////////////////////////////////////////////////////////
//
// - Implement each of the following constructors and methods.
//
// - The details of the implementation of Natural are up to you.
//
// - **Do not** change the signatures of any of the constructors or methods
//   that are given (if you do, then the testing program will give you 0)
//
// - **Do not** add any more #includes.
//
// - You can add member initialization lists to the given constructors if you
//   like.
//
//  - You can add any other useful constructors, methods, or functions. Keep
//    all the code in this one file.
//
/////////////////////////////////////////////////////////////////////////

#include "cmpt_error.h"  // don't add any more #includes
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

class Natural {
private:

    //
    // ... implementation details go here ...
    //

    //
    // ... you can also add other helper methods here ...
    //

public:
    // Pre-condition:
    //    none
    // Post-condition:
    //    constructs a new Natural with value 0
    Natural() {  // default constructor
        // ...
    }

    // Pre-condition:
    //    n >= 0
    //    (call cmpt:error if this is not satisfied)
    // Post-condition:
    //    constructs a new Natural with value n
    Natural(int n) {
        // ...
    }

    // Pre-condition:
    //    s consists of 1, or more, digit characters
    //    (call cmpt:error if this is not satisfied)
    // Post-condition:
    //    constructs a Natural representation of s so that
    //    this->to_string() == s
    Natural(const string& s) {
        // ...
    }

    // Pre-condition:
    //    none
    // Post-condition:
    //    constructs a new Natural whose value is the same as other
    Natural(const Natural& other) {  // copy constructor
        // ...
    }

    // Pre-condition:
    //    none
    // Post-condition:
    //    returns the number of digits in this Natural
    int num_digits() const {
        // ...
    }

    // Pre-condition:
    //    none
    // Post-condition:
    //    returns true if this Natural is 0, and false otherwise
    bool is_zero() const {
        // ...
    }

    // Pre-condition:
    //    none
    // Post-condition:
    //    returns a new Natural equal to the sum of a and this Natural
    Natural operator+(const Natural& a) const {
        // ...
    }

    // Pre-condition:
    //    none
    // Post-condition:
    //    returns a new Natural equal to the product of a and this Natural
    Natural operator*(const Natural& a) const {
        // ...
    }

    // Pre-condition:
    //    none
    // Post-condition:
    //    returns a string representation of this Natural
    string to_string() const {
        // ...
    }

    //
    // ... you can add other helper methods here ...
    //

}; // class Natural

//
// the following methods are provided for convenience
//

ostream& operator<<(ostream& os, const Natural& b) {
    os << b.to_string();
    return os;
}

bool operator==(const Natural& a, const Natural& b) {
    return a.to_string() == b.to_string();
}

bool operator!=(const Natural& a, const Natural& b) {
    return !(a == b);
}

bool operator==(const Natural& a, const string& b) {
    return a.to_string() == b;
}

bool operator!=(const Natural& a, const string& b) {
    return !(a == b);
}

Table Of Contents

Previous topic

Next topic