Project description ^

Your final project is to write a C++ class named bigint 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 the following files:

• bigint.hpp: A header file containing the entire code for the class bigint. Do NOT split the class into multiple files, and do NOT use any other name for the header file or the class.
• README.md: The complete documentation for your class, in Markdown format. Do NOT use any format other than Markdown.
• test.cpp: A program that comprehensively and thoroughly tests every single feature of your class to make sure it works properly. If your test program requires any files as input, they must be included in your submission as well, in a folder named data, and your test program must read them from that folder. If your test program generates any output files, such as logs, they should NOT be included in your submission.

Your project submission must ONLY include the files listed above. Do NOT include executables, object files, the .vscode folder, other files generated or used by the compiler or the IDE, or any other files.

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×10¹⁸. If you want to enter the number 10²⁰, for example, you can't enter it as a 64-bit integer, or any other built-in integer type. Therefore, you need to be able to take a string like "100000000000000000000" and then convert it to the internal storage format of your class.

Your class must overload the following operators:

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

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.

In addition, the following features are optional, as they are significantly harder to implement, but will earn you bonus points for each one that you implement. Please note that I do NOT recommend attempting these features unless you are willing to spend considerably more time and effort on your project:

• Integer division (/ and /=)
• Modulus (% and %=)
• A constructor that takes a string and a base, and converts the string to an arbitrary-precision integer in that base. For example, bigint("FF", 16) should create the integer 255, since FF in hexadecimal (base 16) is 255 in decimal.
• A member function to_string() that converts the arbitrary-precision integer to a string in a given base. For example, bigint(255).to_string(16) should return the string "FF".

How you actually implement any of the above, and how your class stores the number internally, is up to you. Generally, operators should be implemented using the familiar grade school pen-and-paper calculation methods. Here are a few suggestions for how to store the numbers:

1. Store the number as a string, and implement the operations character by character. Note that this is the least efficient and most resource-heavy option, but it is also the simplest to implement.
2. Store the number as a vector of 32-bit unsigned integers - essentially, as a number in "base 2³²". This will be much faster and take much less memory compared to option 1, but will be harder to implement and will require more complicated math and algorithms.
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 and less memory-consuming than option 1, since we eliminate the string and deal directly with integers, but still much simpler than option 2.

Of course, you are welcome to come up with your own original ideas!

Your code should make use of relevant 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, 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 test 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.
• const correctness: Use const variables, member variables, and member functions whenever appropriate. Use constexpr for variables that are known at compile time.

Your final project will be graded based on the guidelines listed below. Please make sure to follow all these 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. If you submit code that was written by another person and/or an AI, 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, ChatGPT, Claude, and others does not count as "original code". While I understand that you may use these tools in real life, you are taking this course as part of your graduate degree, and the purpose of the final project is to demonstrate that you understand the material and that you can write code on your own.
  • You may include short code snippets copied from my lecture notes or other sources, but only under the following conditions:
    • The code must be short, up to a few lines.
    • The code must not be 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 must add comments clearly marking where the copied code starts and ends. You must indicate where it was copied from, including a URL if applicable. If the code came from an AI, indicate which model was used and what your prompt was.
• 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 be self-contained, and your test program 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++23 without any errors.
• Your code must 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 test program must accept user input, if any, 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 the deadline, your grade will be an automatic zero with no option of improving it.

Coding guidelines ^

• 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++23 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.
  • I recommend trying to compile your program using both compilers, as they can catch different issues.
• 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 if applicable (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 only fixed-width integer types. The only exception is if a function in the standard library specifically requires a particular built-in integer type.
• 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.
• Do not use using namespace std; in your code. This is used in the lecture notes only for pedagogical reasons (to make the code shorter). Instead, use the std:: prefix whenever you use anything from the standard library.

The test program ^

• Your test program must be comprehensive, which means it must test every single feature of your class, including all constructors, operators, and member functions. Essentially, every single line of your class should be executed at least once during the test.
• Your test program must be self-contained, that is, it should not require any additional files (beyond those you provided in the data folder) or user input to run.
• Your test program must be fully automated. This means that it should not require any user interaction to run. It should perform all the tests automatically and print out the results.
• I recommend the following strategies for performing reliable tests:
  • Unit tests: Write a separate test for each feature of your class, such as individual constructors, operators, and member functions. Compare the result of each operation with the expected output.
  • Integration tests: Write additional tests that combine two or more different features, such as both addition and subtraction, to ensure they work together correctly.
  • Edge cases: Test your class with edge cases. As an example, since your addition operation will involve a carry operation, test it explicitly with numbers that will cause a carry, to make sure it is handled correctly.
  • Error handling: Test your class with invalid inputs, such as strings that are not valid numbers, or operations that are not allowed, such as division by zero, and ensure that the class throws the correct exceptions.
  • Consistency tests: Make sure the operations you implement are consistent with each other. For example, given 3 numbers A, B, and C, the operations (A + B) - C and (A - C) + B should give the same result.
  • Randomizing: Using random data generated on the spot in at least some of your tests is very important, as it will help you uncover issues that may not arise with fixed data. A great place to do this is in consistency tests, as described above; generate random numbers, perform two different equivalent operations on them, and then check that the results of both operations are the same.
  • Comparison tests: Use another programming language which natively supports arbitrary-precision integers (such as Python) to generate a list of random numbers and operations, and store them in an input file in a suitable format. Then perform calculations using the same numbers and operations with your class, and compare the results.
  • Stress tests: Test your class with very large numbers (with thousands of digits) to make sure it can handle them without crashing or running out of memory and that operations on them produce the correct results.
  • Logging: For each individual test, print out whether it succeeded or failed. Keep track of the total number of successes and failures, and print out a summary at the end. You can also save the results to a file for later inspection.

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 (plus, it will look good on your CV).
• Your code must include clear and detailed Doxygen comments for all functions and classes, including member functions and variables. Additional comments should be added within the code itself as needed, to clarify the purpose of some local variables or non-trivial lines of code if it's not obvious.
• 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 correctly working code is not enough to get a 100% grade. Other aspects of programming mentioned above, such as proper testing, 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.
• Take a look at popular C++ libraries and projects on GitHub for examples of what a good C++ project should look like. A particularly good example is my own C++ thread pool library 😊

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. If the repository is private, please share it with me first and then email me the link.

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