Crate comlib_math

Comlib Math Utilities

This library contains some commonly used math utilities.

Content

• Greatest common divisor
• Modular integers
• Sieve of Eratosthenes
• Primality test
• Factorization
• Modular exponentiation
• Finding next permutation of a list
• Iterating over subsets

Still missing

• Fourier Transform, both number theoretic and complex

Re-exports

pub use subsets::subsets;

Modules

subsets

Module containing functions and structs for iterating subsets.

Structs

Mod1e9p7

Commonly used modulus 10⁹ + 7.

ModInt

Integer type for which all computations are executed in modulo given by M::modulus.

PrimeSieve

Sieve of Eratosthenes.

Quot

A quotient. Represents a rational number as numerator/denominator.

RuntimeModulus

Modulus whose value can be selected at runtime.

RuntimePrimeModulus

Modulus whose value can be selected at runtime.

Enums

Sign

Sign of a number.

Traits

Float

Trait implemented by floating-point numbers.

Integer

Trait implemented by integral types.

InvertibleModulus

Marker trait for indicating that modular numbers in this modulo can be inverted.

Modulus

Modulus contains the modulus and the actual storage type of ModInt.

NonZero

Trait implemented by numeric types which cannot contain 0.

Numeric

Trait implemented by numeric types.

Signed

Trait implemented by signed numbers.

Functions

factorize

Factorizes the given integer into its prime factors.

gcd

Computes the greatest common divisor of the given numbers.

is_prime

Checks whether a given number is a prime.

lcm

Computes the least common multiple of the given numbers.

mod_pow

Raises base to given exponent in the given modulus.

next_permutation

Computes lexicographically next smallest permutation.