# sangi

A modern C++23 arbitrary-precision arithmetic library.

## Overview

sangi provides three core arbitrary-precision types — **Int**, **Float**, and **Rational** — plus **Vector**, **Matrix**, and **LinAlg** (linear algebra) modules, with full operator overloading, NaN/Infinity propagation, and high-performance algorithms. No external dependencies required.

The name derives from **sangi**, the wooden calculation rods used in Japanese *wasan* mathematics from the 8th to 19th century. Mathematicians including Seki Takakazu (1642-1708) employed them in works such as *Hatsubi Sanpou* (1674) - Japan's indigenous mathematical computing instrument. The sangi numeral block was standardised in Unicode 5.0 at U+1D360-U+1D37F.

### Key Features

- **Int** — Arbitrary-precision integer with GCD (Lehmer + HGCD), primality testing (Miller-Rabin), factorization (Trial, Pollard rho, ECM), modular exponentiation (Montgomery), and 5-tier multiplication (Basecase → Karatsuba → Toom-3 → Toom-4 → NTT)
- **Float** — Arbitrary-precision floating-point with all mathematical functions (exp, log, sin, cos, sqrt, etc.), mathematical constants (π, e, γ via Chudnovsky/Brent-McMillan), and correct rounding for basic operations
- **Rational** — Exact rational arithmetic with automatic reduction, continued fractions, Bernoulli numbers, Stern-Brocot tree, and Farey sequences
- **Vector** — Dense vector with dot product, norms, cross product, and expression templates
- **Matrix** — Dense matrix with transpose, inverse, determinant, block views, and rotation matrices
- **LinAlg** — LU/QR/SVD/Cholesky/LDL/Schur decompositions, eigenvalues, iterative solvers (CG, GMRES, BiCGSTAB), matrix functions (expm, sqrtm, logm), sparse solvers, BLAS, LLL lattice reduction
- **NaN/Infinity safe** — All three types propagate NaN and Infinity consistently; division by zero never crashes
- **C++23** — `operator<=>`, `[[nodiscard]]`, move semantics, concepts, `std::format` support
- **No external dependencies** — Pure C++ implementation, no GMP/MPIR required
- **High performance** — MASM assembly (BMI2/ADX), AVX2 NTT, comparable to GMP for most operations

## Quick Start

```cpp
#include <math/core/mp/Int.hpp>
#include <math/core/mp/Float.hpp>
#include <math/core/mp/Rational.hpp>
#include <iostream>

using namespace sangi;

int main() {
    // Arbitrary-precision integer
    Int a("123456789012345678901234567890");
    Int b("987654321098765432109876543210");
    std::cout << "a * b = " << a * b << std::endl;
    std::cout << "gcd   = " << gcd(a, b) << std::endl;

    // Primality test (Miller-Rabin)
    Int p = pow(Int(2), 127u) - Int(1);
    std::cout << p << " is prime: " << std::boolalpha
              << isProbablePrime(p) << std::endl;

    // Arbitrary-precision floating point
    Float pi = Float::pi(100);   // π to 100 digits
    Float e  = Float::e(100);    // e to 100 digits
    std::cout << "pi = " << pi.toDecimalString(50) << std::endl;
    std::cout << "e  = " << e.toDecimalString(50) << std::endl;

    // Exact rational arithmetic
    Rational r1(1, 3);
    Rational r2(1, 6);
    std::cout << "1/3 + 1/6 = " << r1 + r2 << std::endl;  // 1/2

    return 0;
}
```

## Building

### Requirements

- 64-bit OS (x86_64)
- C++23 compatible compiler (tested with **MSVC 17.x / Visual Studio 2022**)
- CMake 3.20 or later

### Build Steps

```bash
mkdir build
cd build
cmake .. -G "Visual Studio 17 2022" -A x64
cmake --build . --config Release
```

### Running Examples

```bash
examples\Release\example-int.exe
examples\Release\example-int-demo.exe
examples\Release\example-float.exe
examples\Release\example-float-demo.exe
examples\Release\example-rational.exe
examples\Release\example-rational-demo.exe
examples\Release\example-vector.exe
examples\Release\example-vector-demo.exe
examples\Release\example-matrix.exe
examples\Release\example-linalg.exe
examples\Release\example-precision-showdown.exe
```

## Project Structure

```
sangi/
  include/
    math/
      core/
        mp/           # Int, Float, Rational
        modular/      # ModularInt, CRT
        vector.hpp    # Dense vector
        matrix.hpp    # Dense matrix
        Complex.hpp   # Complex number
      linalg/         # Linear algebra (decompositions, solvers, eigenvalues)
      fft/            # FFT (internal)
      concepts/       # 50+ algebraic concepts
  src/                # Implementation files (.cpp, .asm)
  lib/                # CMake library targets
  examples/           # Usage examples
```

## License

This library is licensed under the **GNU Lesser General Public License v3.0 (LGPL-3.0)**.

You may use this library in proprietary software as long as modifications to sangi itself are shared under the same license. See [LICENSE](LICENSE) for details.

## Author

Kiyotsugu Arai — [Allisone Inc.](https://www.allisone.co.jp/)
