C++ Arbitrary-Precision Integer Arithmetic

Overview

This repository contains a fully custom, arbitrary-precision integer data type (BigInt) implemented in C++. The project provides an object-oriented wrapper allowing for arithmetic operations on numbers far exceeding standard 64-bit hardware limitations.

This project was originally developed as a successful partner project for a Computer Systems Fundamentals class. It demonstrates an understanding of low-level data representation, bitwise arithmetic, and algorithmic optimization for core arithmetic operations on massive datasets.

Architecture & Data Representation

The BigInt class represents an arbitrary-precision integer using an unbounded, sign-magnitude format:

• Magnitude: The absolute value is stored as a dynamically scaling std::vector<uint64_t>. It uses a little-endian scheme where index 0 holds the least-significant 64 bits, allowing the vector to grow iteratively for massive integers.
• Sign: A single boolean flag indicates whether the integer is negative.

This sign-magnitude approach is simpler to manage than two's-complement for arbitrary widths, allowing the arithmetic operations to be implemented using straightforward mathematical algorithms.

Arithmetic Core & Algorithmic Optimizations

The implementation includes custom logic for addition, subtraction, multiplication, division, and left-bit shifts. Several algorithmic choices were made to optimize performance:

• Multiplication: Implemented via a "grade-school" algorithm approach. To prevent hardware overflows during intermediate 64-bit multiplication steps, the operands are logically split into 32-bit chunks before processing.
• Division: Solved using a binary-search algorithm over the magnitude bounds, making finding the quotient much faster than using repeated subtraction.
• Base Conversions: Base-10 (decimal) conversions process 4 digits at a time to reduce the amount of computation required by repeatedly dividing by 10. The std::stringstream and <iomanip> libraries are used to generate clean hexadecimal and decimal strings.

Verification

The design includes an extensive verification suite built using the provided bigint_tests.cpp.

• Comprehensive testing handles edge cases like zero vs. non-zero, negative vs. non-negative, and varied magnitudes.
• Automated loops process thousands of randomly generated configurations to guarantee the operations are robust. This testing proved particularly vital for getting the complicated boundary conditions right during division.
• Relying strictly on the standard library, the project uses tctest.h and tctest.c to construct a standalone unit-test environment without external dependencies like gtest.

Repository Structure

• bigint.cpp & bigint.h - Core C++ implementation of the BigInt class, its private helper algorithms, and its overloaded arithmetic operators. The original assignment code files are preserved.
• bigint_tests.cpp - Software unit tests targeting individual operator behaviors.
• tctest.h, tctest.c - Standalone C unit-testing framework.
• Makefile - Command-line build configuration.

Technologies & Tools

• Programming Language: C++
• Concepts: Arbitrary-Precision Arithmetic, Little-Endian Storage, Operator Overloading, Bitwise Operations, Algorithmic Optimization.
• Environment: Tested and compiled on x86 Linux servers (University environments).