cplib::BarrettModInt< Context > Class Template Reference

Modular integer using Barrett reduction. More...

#include <bmint.hpp>

Public Types
using	mint = BarrettModInt
using	int_type = typename Context::int_type
using	br_type = typename Context::br_type
using	int_double_t = typename br_type::int_double_t

Public Member Functions
template<typename T , std::enable_if_t< std::is_integral_v< T > &&std::is_signed_v< T > > * = nullptr>
	BarrettModInt (T x)
	Converts a plain integer to a Barrett modular integer.
template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr>
	BarrettModInt (T x)
	Converts a plain integer to a Barrett modular integer.
int_type	val () const
	Converts back to a plain integer in the range \([0,N)\).
int_type	residue () const
	Returns a number that is the same for the same residue class modulo the modulus.
mint &	operator++ ()
mint	operator++ (int)
mint	operator+ () const
mint	operator+ (const mint &rhs) const
mint &	operator+= (const mint &rhs)
mint &	operator-- ()
mint	operator-- (int)
mint	operator- () const
mint	operator- (const mint &rhs) const
mint &	operator-= (const mint &rhs)
mint	operator* (const mint &rhs) const
mint &	operator*= (const mint &rhs)
mint	inv () const
	Returns the modular inverse.
mint	operator/ (const mint &rhs) const
mint &	operator/= (const mint &rhs)
bool	operator== (const mint &rhs) const
bool	operator!= (const mint &rhs) const

Static Public Member Functions
static Guard	set_mod_guard (int_type mod)
	Set the dynamic modint's modulus.
static constexpr int_type	mod ()
	Returns the modulus.

Related Functions
(Note that these are not member functions.)
template<uint32_t Mod>
using	BMInt = BarrettModInt< impl::StaticBarrettReductionContext< uint32_t, Mod > >
	Type alias for 32-bit BarrettModInt with compile-time constant modulus.
template<uint64_t Mod>
using	BMInt64 = BarrettModInt< impl::StaticBarrettReductionContext< uint64_t, Mod > >
	Type alias for 64-bit BarrettModInt with compile-time constant modulus.
using	DynamicBMInt = BarrettModInt< impl::DynamicBarrettReductionContext< uint32_t > >
	Type alias for dynamic BarrettModInt with modulus less than \(2^{32}\).
using	DynamicBMInt64 = BarrettModInt< impl::DynamicBarrettReductionContext< uint64_t > >
	Type alias for dynamic BarrettModInt with modulus less than \(2^{64}\).

Detailed Description

template<typename Context>
class cplib::BarrettModInt< Context >

Modular integer using Barrett reduction.

Your code should generally use the type alias BMInt or BMInt64 for compile-time static modulus, and DynamicBMInt or DynamicBMInt64 for run-time dynamic modulus.

Barrett reduction is used for modular multiplication to avoid costly division. Unlike Montgomery reduction, it works for any modulus, but is slightly slower.

See also

MontgomeryModInt

Constructor & Destructor Documentation

BarrettModInt() [1/2]

template<typename Context >

template<typename T , std::enable_if_t< std::is_integral_v< T > &&std::is_signed_v< T > > * = nullptr>

cplib::BarrettModInt< Context >::BarrettModInt ( T  x )

inlineexplicit

Converts a plain integer to a Barrett modular integer.

This constructor is marked explicit because the cost of conversion is non-trivial (requires one Barrett reduction) and thus implicit conversion is discouraged.

BarrettModInt() [2/2]

template<typename Context >

template<typename T , std::enable_if_t< std::is_unsigned_v< T > > * = nullptr>

cplib::BarrettModInt< Context >::BarrettModInt ( T  x )

inlineexplicit

Converts a plain integer to a Barrett modular integer.

This constructor is marked explicit because the cost of conversion is non-trivial (requires one Barrett reduction) and thus implicit conversion is discouraged.

Member Function Documentation

inv()

template<typename Context >

mint cplib::BarrettModInt< Context >::inv ( ) const

inline

Returns the modular inverse.

The underlying value must be non-zero.

residue()

template<typename Context >

int_type cplib::BarrettModInt< Context >::residue ( ) const

inline

Returns a number that is the same for the same residue class modulo the modulus.

This is the same as val(), unlike MontgomeryModInt.

set_mod_guard()

template<typename Context >

static Guard cplib::BarrettModInt< Context >::set_mod_guard ( int_type  mod )

inlinestatic

Set the dynamic modint's modulus.

Calling this for static modint would be a compile error.

It maintains a stack of moduli. Push stack when it is called, and pop stack when the returned guard object is destructed. This allows recursively calling functions that use different moduli. However at any given moment you can only use one modulus.

Parameters

mod	Must be 2 or greater.

Friends And Related Function Documentation

BMInt

template<typename Context >

template<uint32_t Mod>

using BMInt = BarrettModInt<impl::StaticBarrettReductionContext<uint32_t, Mod> >

related

Type alias for 32-bit BarrettModInt with compile-time constant modulus.

Template Parameters

Mod	The modulus. Must be within \([2,2^{32})\).

BMInt64

template<typename Context >

template<uint64_t Mod>

using BMInt64 = BarrettModInt<impl::StaticBarrettReductionContext<uint64_t, Mod> >

related

Type alias for 64-bit BarrettModInt with compile-time constant modulus.

Template Parameters

Mod	The modulus. Must be within \([2,2^{64})\).

---

The documentation for this class was generated from the following file:

• src/cplib/num/bmint.hpp