ac-library-hs-0.1.0.0: Data structures and algorithms
Safe HaskellNone
LanguageGHC2021

AtCoder.Internal.Barrett

Description

Fast modular multiplication by barrett reduction. Reference: https://en.wikipedia.org/wiki/Barrett_reduction

Example

>>> let bt = new32 10 -- mod 10
>>> umod bt
10
>>> mulMod bt 7 7
9

Since: 1.0.0

Synopsis

Barrett

data Barrett #

Fast modular multiplication by barrett reduction. Reference: https://en.wikipedia.org/wiki/Barrett_reduction

Since: 1.0.0

Instances

Instances details
Show Barrett #

Since: 1.0.0

Instance details

Defined in AtCoder.Internal.Barrett

Methods

showsPrec :: Int -> Barrett -> ShowS #

show :: Barrett -> String #

showList :: [Barrett] -> ShowS #

Eq Barrett #

Since: 1.0.0

Instance details

Defined in AtCoder.Internal.Barrett

Methods

(==) :: Barrett -> Barrett -> Bool #

(/=) :: Barrett -> Barrett -> Bool #

Constructors

new32 :: Word32 -> Barrett #

Creates barret reduction for modulus \(m\) from a Word32 value.

Since: 1.0.0

new64 :: Word64 -> Barrett #

Creates barret reduction for modulus \(m\) from a Word64 value.

Since: 1.0.0

Accessors

umod :: Barrett -> Word32 #

Retrieves the modulus \(m\).

Since: 1.0.0

Barrett reduction

mulMod :: Barrett -> Word64 -> Word64 -> Word64 #

Calculates \(a b \bmod m\).

Since: 1.0.0