Safe Haskell	None
Language	GHC2021

AtCoder.Internal.Barrett

Contents

Description

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

Expand

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

>>> mulMod bt 7 7
9

Since: 1.0.0.0

Synopsis

Barrett

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

Since: 1.0.0.0

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

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

Since: 1.0.0.0

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

Since: 1.0.0.0

\(O(1)\) Retrieves the modulus \(m\).

Since: 1.0.0.0

\(O(\log n)\) Calculates \(a b \bmod m\).

Since: 1.0.0.0