Skip to content

Latest commit

 

History

History
47 lines (39 loc) · 2.01 KB

Readme.md

File metadata and controls

47 lines (39 loc) · 2.01 KB
Raw

Arbitrary Precision Number Implementation

This project is a C++ class implementation of BigInteger and BigRational. It's designed not only as a numerical tool but also as a resource for profiling, testing, and fuzzing your own implementations.

Prerequisites

  • CMake version 3.14 or higher.
  • Clang compiler (or modify the CMakeLists.txt if using a different compiler).

Getting Started

Clone the repository and navigate to the project directory. Initialize the project using CMake:

cmake .

Features

  • BigInteger Storage: BigInteger is stored as a vector of digits. The digit size is configurable from uint8_t to uint32_t.

  • BigRational Representation: BigRational is composed of two BigIntegers, a numerator and a denominator.

  • Safety: The implementation handles overflows/underflows, and casts are performed statically.

  • Testing: Basic operations and edge cases are covered by tests. Run tests in release mode:

    make run

    For debug mode:

    make debug

  • Fuzz Testing: The code has passed basic tests (e.g., a + a = a * 2) with over 200,000 inputs from fuzzing when compiled with UB and Address sanitizers. Run fuzz tests for both string and int64_t constructors:

    make fuzz

    This process is resource-intensive and may take some time (~20 min). For separate runs (~10 min each):

    make fuzz_str_addr_ub_finite
make fuzz_int_addr_ub_finite

  • Profiling: Profile the execution to analyze performance:

    make profile

    My average test execution time is between 0.5s-0.8s in release mode and 2.0-2.3s in debug mode.

  • Implementation Details: Basic operators (*, +, /, -) are implemented with a focus on simplicity, incorporating optimizations where feasible.

Acknowledgments

Inspiration for the project was drawn from the V8 JavaScript engine's bigint implementation, which can be found at V8 GitHub repository.