| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Math.NTT
Description
Number-theoretic transform (integer DFT).
Synopsis
- bitRevSort :: (Vector v a, Vector v (Int, a)) => v a -> v a
- ntt :: KnownNat p => Vector (ModInt p) -> Vector (ModInt p)
- intt :: KnownNat p => Vector (ModInt p) -> Vector (ModInt p)
- convoluteMod :: forall p. KnownNat p => Vector (ModInt p) -> Vector (ModInt p) -> Vector (ModInt p)
- type M1 = 754974721 :: Nat
- type M2 = 167772161 :: Nat
- type M3 = 469762049 :: Nat
- convolute64 :: Vector Int -> Vector Int -> Vector Int
- butterfly :: forall p m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (ModInt p) -> m ()
- butterfly1 :: forall p m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (ModInt p) -> ModInt p -> Int -> Int -> m ()
- invButterfly :: forall p m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (ModInt p) -> m ()
- invButterfly1 :: forall p m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (ModInt p) -> ModInt p -> Int -> Int -> m ()
- bitReverse :: Int -> Int
- grow2 :: forall a. (Num a, Unbox a) => Vector a -> Vector a
- primRoot :: Int -> Int
Documentation
bitRevSort :: (Vector v a, Vector v (Int, a)) => v a -> v a #
ntt :: KnownNat p => Vector (ModInt p) -> Vector (ModInt p) #
\(\Theta(N \log N)\) Number-theoretic transform (integer DFT).
>>>:set -XDataKinds>>>ntt $ U.fromList $ map (ModInt @998244353) [1, 1, 1, 1][4,0,0,0]>>>ntt $ U.fromList $ map (ModInt @469762049) [123, 0, 0, 0][123,123,123,123]
intt :: KnownNat p => Vector (ModInt p) -> Vector (ModInt p) #
\(\Theta(N \log N)\) Inverse number-theoretic transform (integer DFT).
convoluteMod :: forall p. KnownNat p => Vector (ModInt p) -> Vector (ModInt p) -> Vector (ModInt p) #
\(\Theta((N + M) \log (N + M))\) Convolution with mod.
\(\mathcal{F}[f*g](\omega) = \mathcal{F}[f](\omega) \mathcal{F}[g](\omega)\).
\(\mathbb{a} * \mathbb{b} = \mathcal{F^{-1}}(\mathcal{F}(\mathbb{a}) \mathcal{F}(\mathbb{b}))\)
>>>:set -XDataKinds>>>convoluteMod @998244353 (U.fromList [1, 1, 1, 0]) (U.fromList [1, 1, 1, 0])[1,2,3,2,1,0,0]>>>convoluteMod @998244353 (U.fromList [1, 1, 1]) (U.fromList [1, 1, 1, 0])[1,2,3,2,1,0]
Modulo type variable for CRT in convolute64.
Modulo type variable for CRT in convolute64.
Modulo type variable for CRT in convolute64.
convolute64 :: Vector Int -> Vector Int -> Vector Int #
\(\Theta((N+M)\log(N+M))\) Convolution without mod (much heavier than convoluteMod).
See also: convolution_ll (ACL).
butterfly :: forall p m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (ModInt p) -> m () #
\(\Theta(N \log N)\)
butterfly1 :: forall p m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (ModInt p) -> ModInt p -> Int -> Int -> m () #
\(\Theta(N)\) Butterfly calculation performed in-place.
iMaxBit: Length ofxsequals tobit iMaxBitiBit: The length of a pair equals to the length ofxs.
See also: my devlog post.
invButterfly :: forall p m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (ModInt p) -> m () #
\(\Theta(N \log N)\). Does not contain scaling and index sorting.
invButterfly1 :: forall p m. (KnownNat p, PrimMonad m) => MVector (PrimState m) (ModInt p) -> ModInt p -> Int -> Int -> m () #
\(\Theta(N)\) Inverse butterfly calculation performed in-place.
bitReverse :: Int -> Int #