ac-library-hs-1.1.0.0: Data structures and algorithms
Safe HaskellSafe-Inferred
LanguageGHC2021

AtCoder.Internal.Barrett

Description

Fast modular multiplication for Word32 using barrett reduction. Reference: https://en.wikipedia.org/wiki/Barrett_reduction

Example

Expand
>>> let bt = new32 10 -- mod 10
>>> umod bt
10

>>> mulMod bt 7 7
9

Since: 1.0.0.0

Synopsis

Barrett

data Barrett Source #

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

Since: 1.0.0.0

Instances

Instances details
Show Barrett Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Internal.Barrett

Methods

showsPrec :: Int -> Barrett -> ShowS #

show :: Barrett -> String #

showList :: [Barrett] -> ShowS #

Eq Barrett Source #

Since: 1.0.0.0

Instance details

Defined in AtCoder.Internal.Barrett

Methods

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

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

Constructor

new32 :: Word32 -> Barrett Source #

Creates a Barrett for a modulus value \(m\) of type Word32 value.

Since: 1.0.0.0

new64 :: Word64 -> Barrett Source #

Creates a Barrett for a modulus value \(m\) of type Word64 value.

Since: 1.0.0.0

Accessor

umod :: Barrett -> Word32 Source #

Retrieves the modulus \(m\).

Since: 1.0.0.0

Barrett reduction

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

Calculates \(a b \bmod m\).

Since: 1.0.0.0