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_matrix_demo.cpp— Matrix demo (3 scenarios showcasing capabilities)
│   ├── 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)
│   │
│   ├── example_doc_int_samples.cpp— verification harness for code in api/Int.html
│   ├── example_doc_float_samples.cpp— verification harness for code in api/Float.html
│   ├── example_doc_rational_samples.cpp— verification harness for code in api/Rational.html
│   ├── example_doc_complex_samples.cpp— verification harness for code in api/Complex.html
│   ├── example_doc_vector_samples.cpp— verification harness for code in api/Vector.html
│   ├── example_doc_matrix_samples.cpp— verification harness for code in api/Matrix.html
│   ├── example_doc_linalg_samples.cpp— verification harness for code in api/LinAlg.html
│   ├── example_doc_polynomial_samples.cpp— verification harness for code in api/Polynomial.html
│   ├── example_doc_roots_samples.cpp— verification harness for code in api/Roots.html
│   ├── example_doc_optimization_samples.cpp— verification harness for code in api/Optimization.html
│   ├── example_doc_fft_samples.cpp— verification harness for code in api/FFT.html
│   ├── example_doc_tensor_samples.cpp— verification harness for code in api/Tensor.html
│   └── example_doc_concepts_samples.cpp— verification harness for code in api/Concepts.html
│
├── 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
│       │   └── ntt.hpp— NTT (Number Theoretic Transform) public API
│       │
│       ├── 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)
│       │   ├── sylvester.hpp— Sylvester equation A·X + X·B = C solver
│       │   ├── HNF.hpp— Hermite Normal Form (HNF)
│       │   ├── RationalMatrix.hpp— rational matrix (single common denominator, Bareiss determinant, Dixon exact solve)
│       │   ├── dixon_solve.hpp— exact solution of integer linear systems via Dixon p-adic lifting
│       │   ├── 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)
│       │   ├── sparse_ordering.hpp— fill-reducing ordering for sparse matrices (AMD)
│       │   ├── RandomizedSVD.hpp— randomized SVD (large-scale low-rank approximation)
│       │   ├── vector_space_utilities.hpp— vector-space utilities (bases, orthogonalization)
│       │   ├── balance.hpp— matrix balancing (eigenvalue preprocessing, ~dgebal)
│       │   ├── balance_sparse.hpp— sparse matrix balancing (Osborne)
│       │   ├── static_dims.hpp— dimension helpers for static-size matrices
│       │   └── linalg.hpp— linear-algebra umbrella header (include everything)
│       │
│       ├── 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)
│       │   └── robust_lp.hpp— robust linear programming (LP under uncertainty)
│       │
│       ├── random/— random numbers & probability distributions (Random)
│       │   ├── random.hpp— probability distributions and RNG engines (umbrella header)
│       │   ├── distributions.hpp— various probability distributions
│       │   ├── distributions_extra.hpp— noncentral and additional continuous distributions
│       │   ├── normal.hpp— fast normal-distribution sampling
│       │   ├── quasi_random.hpp— quasi-random (low-discrepancy) sequences
│       │   └── random_sampling.hpp— standard / arbitrary-precision sampling
│       │
│       ├── approx/— Approximation
│       │   └── approximation.hpp— function approximation (regression, Chebyshev, Padé, continued fractions, rational interpolation)
│       │
│       ├── interpolation/— Interpolation
│       │   ├── Interpolation.hpp— interpolation (Lagrange, Newton, cubic spline, PCHIP, barycentric)
│       │   └── BSpline.hpp— B-spline basis, interpolation, regression (De Boor)
│       │
│       ├── special/— special functions
│       │   ├── airy.hpp— Airy functions Ai, Bi and their derivatives
│       │   ├── anger_weber.hpp— Anger function Jν, Weber function Eν
│       │   ├── bessel.hpp— Bessel functions Jν, Yν, Iν, Kν, spherical Bessel, Hankel
│       │   ├── clausen.hpp— Clausen function Cl₂, generalized Cl_n / Sl_n
│       │   ├── coulomb.hpp— Coulomb wave functions F_L, G_L, normalization C_L
│       │   ├── coupling.hpp— angular-momentum coupling (Wigner 3-j/6-j/9-j, Clebsch-Gordan)
│       │   ├── dawson.hpp— Dawson function F(x)
│       │   ├── debye.hpp— Debye functions D_n(x) (solid-state physics)
│       │   ├── elliptic.hpp— elliptic integrals (Carlson/Legendre form), Jacobi elliptic functions
│       │   ├── error_function.hpp— error-function family (erf, erfc, erfcx, erfi, erfInv)
│       │   ├── exponential_integral.hpp— exponential integral Ei, trig integrals Si/Ci, dilogarithm
│       │   ├── factorial_utils.hpp— factorial utilities (double factorial, Pochhammer, binomial coefficient)
│       │   ├── fermi_dirac.hpp— Fermi-Dirac integrals F_s(x)
│       │   ├── fresnel.hpp— Fresnel integrals S(x), C(x)
│       │   ├── gamma.hpp— gamma-function family (Γ, lnΓ, digamma, etc.)
│       │   ├── hypergeometric.hpp— hypergeometric functions ₁F₁, ₂F₁, ₀F₁
│       │   ├── hypergeometric_pq.hpp— general ₚFq hypergeometric, Meijer G function
│       │   ├── kelvin.hpp— Kelvin functions ber, bei, ker, kei (order 0)
│       │   ├── lambert_w.hpp— Lambert W function W₀, W₋₁
│       │   ├── legendre.hpp— Legendre polynomials, spherical harmonics, Jacobi polynomials
│       │   ├── lerch.hpp— Lerch transcendent Φ(z,s,a) (unifies polylog/Hurwitz)
│       │   ├── mittag_leffler.hpp— Mittag-Leffler functions E_α, E_{α,β}
│       │   ├── orthogonal_classical.hpp— classical orthogonal polynomials (Hermite, Laguerre, Chebyshev)
│       │   ├── owens_t.hpp— Owen's T function T(h, a)
│       │   ├── special.hpp— special-functions aggregate header
│       │   ├── special_common.hpp— common foundation for special-function templates
│       │   ├── spheroidal.hpp— spheroidal wave functions (angular functions, eigenvalues)
│       │   ├── struve.hpp— Struve function H_ν, modified L_ν
│       │   ├── theta.hpp— Jacobi theta functions θ₁–θ₄
│       │   ├── transport.hpp— transport functions J_n, synchrotron functions F, G
│       │   ├── weierstrass.hpp— Weierstrass elliptic functions ℘, ζ_W, σ_W
│       │   └── zeta.hpp— Riemann/Hurwitz zeta, Dirichlet η
│       │
│       └── 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)
│           ├── generic_math.hpp— math-constant helpers for standard and arbitrary-precision floating-point
│           ├── expr_templates.hpp— expression-template foundation (VecExpr, operators)
│           ├── simd_traits.hpp— SIMD packet type traits (AVX2/SSE)
│           ├── vector.hpp— Vector, StaticVector, VectorMap classes
│           ├── BaseVector.hpp— common vector base class (parent of Vector)
│           │
│           ├── 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)
│           ├── BaseMatrix.hpp— common matrix base class (parent of Matrix/StaticMatrix)
│           ├── Tensor.hpp— Tensor class (arbitrary-rank tensor)
│           ├── Polynomial.hpp— Polynomial<T> class (Horner, division, GCD, orthogonal polynomials)
│           ├── Polynomial_factorization.hpp— polynomial factorization (Yun + rational roots + Kronecker), resultant, discriminant
│           ├── RationalFunction.hpp— rational function P(x)/Q(x) class
│           ├── RationalFunction_partialFractions.hpp— partial-fraction expansion (Heaviside's method)
│           ├── FactoredInteger.hpp— prime-factor/exponent pair representation (return type of factorize)
│           ├── Complex.hpp— Complex<T> class (arbitrary-precision complex)
│           ├── Quaternion.hpp— Quaternion<T> class
│           ├── 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)
│           │   └── mkl_backend.hpp— MKL backend (BLAS/LAPACK wrappers + non-MKL stubs)
│           │
│           ├── 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)
│               │   └── compiler_intrinsics.hpp— compiler-intrinsics compatibility layer (MSVC/GCC)
│               │
│               ├── 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/
        │   ├── matrix.cpp— explicit instantiation of Matrix<T> (float, double)
        │   ├── vector.cpp— explicit instantiation of Vector<T> (float, double)
        │   │
        │   └── mp/— arbitrary-precision arithmetic
        │       ├── 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
        │       │   ├── IntAPRCL.cpp— APR-CL deterministic primality proof (isProvablePrime)
        │       │   ├── 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)
        │       │   └── mpn_x64_mod1.asm— x64 single-limb remainder (preinv, ~mod_1_1)
        │       │
        │       ├── 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
        │
        └── fft/— FFT implementation
            ├── fft.cpp— FFT/RealFFT/FFTEngine explicit instantiation (float, double)
            ├── fft_batch_stub.cpp— batched-FFT stub
            └── fft_batch_avx2.asm— x64 batched FFT kernel (AVX2)