Source Code Listing

File layout of the sangi source code with a short description of each file.

Download as ZIP

sangi/
├── CMakeLists.txt— top-level CMake configuration
├── LICENSE— LGPL-3.0 license
├── README.md— project overview
│
├── examples/— sample programs
│   ├── CMakeLists.txt— sample build configuration
│   ├── example_int.cpp— Int API sample
│   ├── example_int_demo.cpp— Int demos (Fibonacci, RSA, Mersenne primes, factorial, GCD)
│   ├── example_float.cpp— Float API sample
│   ├── example_float_demo.cpp— Float demos (constants to 100 digits, π to 1M digits, Ramanujan, Machin)
│   ├── example_rational.cpp— Rational API sample
│   ├── example_rational_demo.cpp— Rational demos (floating-point pitfalls, continued fractions, Bernoulli, Stern-Brocot)
│   ├── example_complex.cpp— Complex API sample (basic ops, Mandelbrot, arbitrary-precision Complex<Float>)
│   ├── example_vector.cpp— Vector API sample
│   ├── example_vector_demo.cpp— Vector demos (PageRank, 3D reflection, cosine similarity)
│   ├── example_matrix.cpp— Matrix API sample
│   ├── example_linalg.cpp— LinAlg API sample (decompositions, eigenvalues, iterative methods)
│   ├── example_polynomial.cpp— Polynomial API sample (arithmetic, differentiation/integration, GCD, orthogonal polynomials)
│   ├── example_polynomial_factorization.cpp— polynomial factorization (Yun + rational roots + Kronecker)
│   ├── example_roots.cpp— root-finding API sample (Brent, Newton, all complex roots of polynomials)
│   ├── example_optimization.cpp— optimization API sample (Rosenbrock BFGS, curve fitting, linear programming)
│   ├── example_fft.cpp— FFT API sample (complex/real FFT, convolution, amplitude spectrum)
│   ├── example_precision_showdown.cpp— arbitrary-precision demo (double vs. Float precision comparison)
│   └── example_mp.cpp— combined arbitrary-precision sample (Int + Float + Rational)
│
├── include/— public headers
│   └── math/
│       ├── concepts/
│       │   └── algebraic_concepts.hpp— 50+ algebraic concepts (Ring, Field, VectorSpace, etc.)
│       │
│       ├── fft/— FFT (used by NTT multiplication)
│       │   ├── fft.hpp— FFT interface (complex FFT)
│       │   ├── fft2d.hpp— 2D FFT
│       │   ├── fft3d.hpp— 3D FFT
│       │   ├── fft_batch.hpp— batched FFT
│       │   ├── fft_simd.hpp— SIMD-accelerated FFT
│       │   └── fft_utils.hpp— FFT utilities
│       │
│       ├── roots/— root-finding algorithms
│       │   ├── root_finding.hpp— root-finding umbrella header
│       │   ├── root_finding_base.hpp— common foundation (RootResult, stopping criteria)
│       │   ├── root_finding_1d.hpp— 1D root finding (bisection, Brent, Newton, secant, TOMS748)
│       │   ├── root_finding_nd.hpp— multi-dimensional root finding (Newton, Broyden)
│       │   └── polynomial_roots.hpp— all complex polynomial roots (Jenkins-Traub, Laguerre, Aberth-Ehrlich)
│       │
│       ├── linalg/— linear algebra (decompositions, solvers, eigenvalues)
│       │   ├── decomposition.hpp— matrix decompositions (LU, QR, Cholesky, SVD)
│       │   ├── solvers.hpp— linear system solvers (direct methods)
│       │   ├── iterative_solvers.hpp— iterative solvers (CG, GMRES, BiCGSTAB)
│       │   ├── eigenvalues.hpp— eigenvalues/eigenvectors (QR algorithm, power iteration)
│       │   ├── matrix_functions.hpp— matrix functions (exp, log, sqrt, norm)
│       │   ├── blas.hpp— BLAS level 1/2/3 operations
│       │   ├── sparse_lu.hpp— sparse LU decomposition
│       │   ├── sparse_qr.hpp— sparse QR decomposition
│       │   ├── simplicial_cholesky.hpp— sparse Cholesky decomposition (simplicial)
│       │   ├── RandomizedSVD.hpp— randomized SVD (large-scale low-rank approximation)
│       │   └── vector_space_utilities.hpp— vector-space utilities (bases, orthogonalization)
│       │
│       ├── optimization/— optimization (1D/multi-D, linear programming, convex)
│       │   ├── optimization_base.hpp— common types (OptimizationOptions, OptimizationResult, LineSearchParams)
│       │   ├── optimization_1d.hpp— 1D minimization declarations (golden section, Brent)
│       │   ├── optimization_1d_impl.hpp— 1D minimization implementation
│       │   ├── optimization_nd.hpp— multi-D minimization declarations (BFGS, L-BFGS, Nelder-Mead, CMA-ES, jSO, etc.)
│       │   ├── optimization_nd_impl.hpp— multi-D minimization implementation
│       │   ├── linear_programming.hpp— linear programming declarations (simplex method)
│       │   ├── linear_programming_impl.hpp— linear programming implementation
│       │   ├── ConvexOptimization.hpp— convex optimization declarations (FISTA, ADMM)
│       │   ├── ConvexOptimization_impl.hpp— convex optimization implementation
│       │   └── SimulatedAnnealing.hpp— simulated annealing (generic version)
│       │
│       └── core/
│           ├── basic_types.hpp— basic type definitions (word_t, dword_t, etc.)
│           ├── common.hpp— shared utilities
│           ├── endian_utils.hpp— endianness conversion
│           ├── numeric_state.hpp— NaN/Infinity state management
│           ├── traits.hpp— type traits (umbrella header)
│           ├── traits_part1.hpp— type traits part 1 (numeric_traits)
│           ├── traits_part2.hpp— type traits part 2 (PacketTraits, etc.)
│           ├── power.hpp— generic exponentiation (pow template)
│           ├── expr_templates.hpp— expression-template foundation (VecExpr, operators)
│           ├── simd_traits.hpp— SIMD packet type traits (AVX2/SSE)
│           ├── vector.hpp— Vector, StaticVector, VectorMap classes
│           │
│           ├── vector/— Vector implementation details
│           │   ├── vector_base.hpp— Vector base class
│           │   ├── vector_operations.hpp— Vector operations (dot, cross, norm, etc.)
│           │   ├── vector_storage.hpp— Vector storage
│           │   └── vector_view.hpp— VectorView / ConstVectorView view classes
│           │
│           ├── matrix.hpp— Matrix class (dense, operators, transpose, block operations)
│           ├── Polynomial.hpp— Polynomial<T> class (Horner, division, GCD, orthogonal polynomials)
│           ├── Polynomial_factorization.hpp— polynomial factorization (Yun + rational roots + Kronecker), resultant, discriminant
│           ├── FactoredInteger.hpp— prime-factor/exponent pair representation (return type of factorize)
│           ├── Complex.hpp— Complex<T> class (arbitrary-precision complex)
│           ├── sparse_matrix.hpp— SparseMatrix class (CSR/CSC sparse matrix)
│           ├── sparse_matrix_algorithms.hpp— sparse-matrix algorithms (SpMV, conversions)
│           ├── convergence_criteria.hpp— convergence criteria (for iterative methods)
│           ├── computation_policy.hpp— computation policies (precision / parallelism control)
│           │
│           ├── computation/— computation backends
│           │   └── simd_backend.hpp— SIMD backend (AVX2/SSE dispatch)
│           │
│           ├── modular/— modular arithmetic (used by NTT)
│           │   ├── ModularInt.hpp— modular integer type ModularInt<P>
│           │   ├── ModularIntTraits.hpp— ModularInt type traits
│           │   └── CRT.hpp— Chinese Remainder Theorem (CRT)
│           │
│           └── mp/— arbitrary-precision arithmetic
│               ├── error.hpp— error types (NumericError enum)
│               ├── FFT.hpp— FFT interface
│               ├── ThreadPool.hpp— thread pool for NTT parallelization
│               │
│               ├── Int.hpp— Int class (umbrella header)
│               ├── Int/— Int implementation details
│               │   ├── IntBase.hpp— Int core: constructors, comparison, bit operations
│               │   ├── IntTraits.hpp— Int type traits and constants
│               │   ├── IntSpecialStates.hpp— NaN/Infinity factories and predicates
│               │   ├── IntOps.hpp— arithmetic operations (add, sub, abs, negate)
│               │   ├── IntMultiplication.hpp— multiplication (Basecase, Karatsuba, Toom-3/4/6/8, NTT)
│               │   ├── IntDivision.hpp— division (Schoolbook, Burnikel-Ziegler)
│               │   ├── IntGCD.hpp— GCD/LCM (Binary GCD), extended Euclidean
│               │   ├── IntModular.hpp— modular exponentiation (Montgomery), modular inverse
│               │   ├── IntPrime.hpp— primality testing (Miller-Rabin), nextPrime, Pollard rho
│               │   ├── IntSqrt.hpp— integer square root, n-th root, isSquare, isPerfectPower
│               │   ├── IntCombinatorics.hpp— factorial, double factorial, binomial, Fibonacci, Lucas
│               │   ├── IntIO.hpp— I/O (toString, fromString, std::format)
│               │   ├── IntFactorTable.hpp— small-prime tables (for sieving)
│               │   ├── IntRandom.hpp— random generation (uniform, ranged)
│               │   ├── IntNumberTheory.hpp— number-theoretic functions (Euler φ, Möbius μ, Jacobi, Legendre, etc.)
│               │   ├── IntFactorization.hpp— integer factorization (trial division, Pollard rho, ECM, etc.)
│               │   ├── IntSequence.hpp— number-theoretic sequences (Bernoulli, Stirling, etc.)
│               │   ├── MpnOps.hpp— mpn-level operations (limb-array arithmetic)
│               │   ├── PrimeNtt.hpp— prime-modulus NTT (AVX2 butterfly, Montgomery)
│               │   ├── SmallPrimeNtt.hpp— small-prime NTT
│               │   ├── DoubleFft.hpp— double-precision FFT multiplication
│               │   ├── GoldilocksNtt.hpp— Goldilocks-prime NTT
│               │   ├── SboWords.hpp— Small Buffer Optimization (SBO) word array
│               │   ├── ScratchArena.hpp— scratch memory arena
│               │   └── UInt128.hpp— 128-bit unsigned integer (MSVC/GCC compatible)
│               │
│               ├── Float.hpp— Float class (arbitrary-precision floating-point)
│               ├── Float/
│               │   └── FloatMath.hpp— Float math function declarations (exp, log, sin, cos, etc.)
│               ├── FloatOps.hpp— Float 3-argument operations (buffer reuse)
│               │
│               ├── Rational.hpp— Rational class (umbrella header)
│               └── Rational/— rational numbers
│                   ├── RationalBase.hpp— Rational core: arithmetic, comparison, conversion
│                   ├── RationalConstants.hpp— Bernoulli numbers, Stirling coefficients
│                   └── RationalTraits.hpp— Rational type traits
│
├── lib/
│   └── CMakeLists.txt— library build configuration (sangi_int, sangi_float, sangi_rational)
│
└── src/— implementation files
    └── math/core/mp/
        ├── Int/
        │   ├── IntBase.cpp— Int core implementation (constructors, bit operations)
        │   ├── IntOperators.cpp— operator overloads (+, -, *, /, %, <<, >>)
        │   ├── IntOps.cpp— arithmetic operations implementation
        │   ├── IntGCD.cpp— GCD/LCM/extended Euclidean implementation
        │   ├── IntModular.cpp— Montgomery modular exponentiation and inverse
        │   ├── IntPrime.cpp— Miller-Rabin, nextPrime, Pollard rho
        │   ├── IntSqrt.cpp— square root (Newton), n-th root, isPerfectPower
        │   ├── IntCombinatorics.cpp— factorial (sieve-based), Fibonacci (fast doubling), Lucas
        │   ├── IntIO.cpp— string conversion / I/O implementation
        │   ├── IntFactorTable.cpp— prime-table generation
        │   ├── IntSpecialStates.cpp— NaN/Infinity special-state implementation
        │   ├── IntFactorization.cpp— integer factorization (trial division, ECM dispatch)
        │   ├── mpn_x64.asm— x64 assembly (MULX/ADCX/ADOX mpn primitives)
        │   ├── mpn_x64_add.asm— x64 add/sub (addmul_1, submul_1)
        │   ├── mpn_x64_div.asm— x64 division (divmod_1)
        │   ├── mpn_x64_mont.asm— x64 Montgomery multiplication (512-bit specialized kernel)
        │   └── mpn_x64_mul.asm— x64 multiplication (mul_basecase)
        │
        ├── Float/
        │   ├── Float.cpp— Float implementation (operators, toDecimalString, rounding)
        │   └── FloatMath.cpp— math function implementations (exp, log, sin, cos, π, e, etc.)
        │
        └── Rational/
            ├── Rational.cpp— Rational implementation (I/O, conversion)
            └── RationalConstants.cpp— Bernoulli numbers and Stirling coefficients implementation

pro libraries (sangi_factorize, sangi_int_factorize)
        ├── Polynomial_factorization.cpp— polynomial factorization pro (Cantor-Zassenhaus + Hensel + van Hoeij)
        ├── IntPrimeMPQS.cpp— integer factorization MPQS/SIQS
        ├── IntPrimeGNFS.cpp— integer factorization GNFS (general number field sieve)
        └── IntAPRCL.cpp— deterministic primality test APR-CL