CSE 701: Final Project
McMaster University, Fall 2023

Table of contents

Project description ^

Your final project is to write a C++ class for arbitrary-precision integers. This class should be viewed as an extension of the usual C++ signed integer types, except that your class will allow signed integers of unlimited range - limited only by the computer's memory.

The project submission will consist of three files:

  • bigint.hpp: A header file containing the entire code for the class. Do not split the class into multiple files.
  • demo.cpp: A program that demonstrates every single thing your class can do. It should use each constructor and overloaded operator, but how it uses them is up to you.
  • README.md: The complete documentation for your class, in Markdown format.
  • Do not include any executable files in your submission.

Your arbitrary-precision integer class must contain the following 3 constructors:

  1. A default constructor, creating the integer 0.
  2. A constructor that takes a signed 64-bit integer and converts it to an arbitrary-precision integer.
  3. A constructor that takes a string of digits and converts it to an arbitrary-precision integer. The reason we need this is that signed 64-bit integers only go up to 9,223,372,036,854,775,807, or around 9.2×1018. If I want to enter the number 1020, for example, I can't enter it as a 64-bit integer, or as any other integer type for that matter - such a number simply cannot be represented using the fundamental integer types available in C++, which is exactly why we need to create an arbitrary-precision class in the first place. Therefore, you need to be able to take a string like "100000000000000000000" and then convert it to the internal storage format of your arbitrary-precision integers.

Your class must overload the following operators:

  • Addition (+ and +=)
  • Subtraction (- and -=)
  • Multiplication (* and *=)
  • Negation (unary -)
  • Comparison (==, !=, <, >, <=, and >=)
  • Assignment (=)
  • Insertion (<<, to print the integer to a stream such as std::cout or a file)

Please note that these operators only need to be defined for arbitrary-precision integers, you do not need to include any operators for combinations of arbitrary-precision integers and normal integers, such as bigint(1) + 2.

Of course, how you actually implement these operations, and how your class stores the number internally, is up to you. Here are a few suggestions:

  1. Store the number as a string, and implement the operations character by character.
  2. Store the number as a vector of 32-bit or 64-bit unsigned integers - essentially, as a number in "base 232" or "base 264". This will be much faster and take much less memory compared to option 1, but will be harder to implement and may require more complicated math.
  3. Store the number as a vector of 8-bit unsigned integers, which only take values from 0 to 9, that is, a single decimal digit in base 10. This will be a bit faster than the option 1, since we eliminate the string and deal directly with integers, but still much simpler than option 2.

Your code should make use of all the C++ concepts we learned, in particular:

  • References: Avoid using pointers unless you absolutely have to. Use references instead. Functions should take arguments as a (constant) reference whenever possible to avoid copying (as explained in the notes), unless the arguments are fundamental types.
  • Containers: Make sure to use containers such as std::string and std::vector instead of C-style strings and arrays.
  • Exceptions: Make sure that any "illegal" operations or errors throw an exception, and that your demo program appropriately catches and handles these exceptions. When the constructors get invalid input (e.g., the string "gk%45#^$#!" is not a valid integer) they should throw an appropriate exception. Another example of an operation that should throw an exception is division by zero (if you implement division).
  • Encapsulation and class invariants: Make sure to make all the member variables private, and that all the member functions preserve the class invariants.
  • Constant variables: Use const variables, member variables, and member functions whenever appropriate.

Your final project will be graded based on the guidelines listed below. Please make sure to follow all the guidelines closely in order to get a good grade!

Mandatory guidelines (automatic zero if not satisfied) ^

  • Your code must be original, that is, written by you in its entirety from scratch. Please note that if you submit code that you did not write yourself, you will receive a grade of 0 and will be charged with academic dishonesty.
    • To be perfectly clear, code generated by tools such as GitHub Copilot and ChatGPT does not count as "original code".
    • You may include short code snippets copied from my lecture notes or other sources, but only under the following conditions:
      • The code is short, up to a few lines.
      • The code is not central to the project. For example, it can be a few lines of error checking code, not an important algorithm that your entire project is based on.
      • You clearly mark where the copied code starts and ends in a comment and indicate where it was copied from, including a URL if applicable.
  • All code must be written in C++. You cannot use C, and certainly not any other programming languages, not even as a small part of the project.
  • Each project must consist of a self-contained C++ program, which can optionally be split into multiple source and header files, but must compile and run by itself without any additional requirements or dependencies. I should not be required to download or install anything in order to compile and/or run your project.
  • Your code must compile using the latest versions of GCC and/or Clang with the compiler argument -std=c++20 without any errors. If I cannot compile your project, then obviously I cannot test it.
  • Your code should be fully portable. This means it should compile successfully with any standards-compliant C++ compiler and run on any operating system and CPU architecture. Therefore, you must use only standard C++, and must not use any features that are compiler- or OS-specific. Note that all code used in the lecture notes is standards-compliant. If you want to use something that is not in the lecture notes, please look it up on cppreference.com to verify that it is standards-compliant.
  • Your program must accept user input only via files and/or command line arguments. It must not accept input via the terminal at runtime. Your program must run from start to finish without requiring any user interaction.

If any of the above guidelines are not satisfied, I will notify you by email, and you will get 24 hours to fix your submission. If it is not fixed by then, your grade will be an automatic zero. The reason is that if you program does not satisfy these guidelines, then grading it would be either impossible (e.g. if your program does not compile) or just extremely time consuming (e.g. if your program takes input during runtime, I would have to sit down and type the input all over again single every time I run it).

The program itself ^

  • Your code must compile using the latest versions of GCC and/or Clang with the compiler arguments -Wall -Wextra -Wconversion -Wsign-conversion -Wshadow -Wpedantic -std=c++20 without warnings. If you get a warning, you must eliminate the mistake that led to it, not the warning itself. For example, a warning about an unused variable x could technically be eliminated by writing something like (void)x, but the actual solution should be to not define that variable in the first place.
  • Your program must avoid all of the common errors that I mention in the lecture notes, especially those inside big red boxes!
  • Your program should never make use of any user-defined macros. The reasons for this, as well as suggested alternatives, are explained in the lecture notes.
  • Your program must be able to detect and handle errors, including: user errors (e.g. the user entered a string where they should have entered a number), file errors (e.g. invalid file format), and system errors (e.g. out of memory), and terminate the program with an informative error message, e.g. "Invalid input on line 7 of input.txt: Expected a number".
  • Do not use dynamic memory allocation (new and delete - see chapter 9 of the notes). Instead, only use standard containers like std::vector that manage their own memory. (Advanced students may, at their peril, ask permission from the professor to use dynamic memory allocation, but even then, they must utilize only smart pointers.)
  • For maximum portability, you must use fixed-width integer types whenever possible, as we learned in class.
  • The code must be fully object-oriented, which means objects and their member variables and functions should be used whenever possible, and correctly implement the object-oriented techniques we learned in class, such as encapsulation and class invariants.

Presentation ^

  • The project must be submitted via GitHub. You do not have to make your repository public, you can also make it private and provide me with access, but ideally this will be a public repository that will contain code that other people might want to download and use.
  • Your code must include clear and detailed Doxygen comments for all functions and classes, including member functions and variables. Additional comments should be added as needed within the code itself to clarify the purpose of some local variables or non-trivial lines of code.
  • Your project submission must include clear and detailed Markdown documentation in a file named README.md in the GitHub repository. The documentation should explain what your code does and how it works, including any relevant equations, algorithms, and concepts. The documentation must include several examples of possible inputs of interest and the outputs they generate. Only Markdown documentation will be accepted; LaTeX, Word, or other formats are not allowed.
  • Your code and documentation should be free of typos. This includes any output generated by the program as well as the names of variables, functions, and other symbols in the code itself. I highly recommend using the Code Spell Checker extension for VS Code for this purpose.
  • All code must be properly formatted for maximum readability. I highly recommend using VS Code's automatic formatting feature (Shift+Alt+F) and even set it up to automatically format code on save, as explained in the lecture notes. Poorly formatted code will result in deducted points even if the code itself works perfectly.

Additional guidelines ^

  • It is important to clarify that just writing a working program is not enough to get a 100% grade. Other aspects of programming mentioned above, such as portability, presentation, and readability, are just as important.
  • Ideally, your code should be a high-quality production-level program that people could actually use, at least in principle if not in practice. Potential users should be able to understand how the program works, use it for their own needs, and possibly modify the code themselves - without needing any additional information beyond what's in the documentation, comments, and output of the program itself.
  • Make sure to use the C++ static code checkers mentioned on the course website. They will help ensure that your code is correct and avoids many common mistakes.

The deadline for submitting this project is December 27 by 23:59. As indicated in the guidelines, the project should be submitted via GitHub. Once you upload it to GitHub, please send me a link to the repository by email to baraksh@gmail.com. If the repository is private, please share it with me first and then email me the link.

I recommend starting the project right now, since we already learned most of the material needed to write this project. If you need an extension, please email me at baraksh@gmail.com as soon as possible.

If you have any questions, please feel free to ask on Teams or by email!

© 2024 Barak Shoshany