    -- |
    -- Module:      Math.NumberTheory.ArithmeticFunctions.Moebius
    -- Copyright:   (c) 2018 Andrew Lelechenko
    -- Licence:     MIT
    -- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
    --
    -- Values of <https://en.wikipedia.org/wiki/Möbius_function Möbius function>.
    --

    {-# LANGUAGE BangPatterns          #-}
    {-# LANGUAGE MagicHash             #-}
    {-# LANGUAGE MultiParamTypeClasses #-}
    {-# LANGUAGE TypeFamilies          #-}

    module Math.NumberTheory.ArithmeticFunctions.Moebius
      ( Moebius(..)
      , runMoebius
      , sieveBlockMoebius
      ) where

    import Control.Monad (forM_)
    import Control.Monad.ST (runST)
    import Data.Bits
    import Data.Int
    import Data.Word
    import qualified Data.Vector.Generic         as G
    import qualified Data.Vector.Generic.Mutable as M
    import qualified Data.Vector.Primitive as P
    import qualified Data.Vector.Unboxed         as U
    import qualified Data.Vector.Unboxed.Mutable as MU
    import GHC.Exts
    import GHC.Num.Integer
    import Unsafe.Coerce

    import Math.NumberTheory.Roots (integerSquareRoot)
    import Math.NumberTheory.Primes
    import Math.NumberTheory.Utils.FromIntegral

    import Math.NumberTheory.Logarithms

    -- | Represents three possible values of <https://en.wikipedia.org/wiki/Möbius_function Möbius function>.
    data Moebius
      = MoebiusN -- ^ -1
      | MoebiusZ -- ^  0
      | MoebiusP -- ^  1
      deriving (Moebius -> Moebius -> Bool
    (Moebius -> Moebius -> Bool)
    -> (Moebius -> Moebius -> Bool) -> Eq Moebius
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: Moebius -> Moebius -> Bool
    == :: Moebius -> Moebius -> Bool
    $c/= :: Moebius -> Moebius -> Bool
    /= :: Moebius -> Moebius -> Bool
    Eq, Eq Moebius
    Eq Moebius =>
    (Moebius -> Moebius -> Ordering)
    -> (Moebius -> Moebius -> Bool)
    -> (Moebius -> Moebius -> Bool)
    -> (Moebius -> Moebius -> Bool)
    -> (Moebius -> Moebius -> Bool)
    -> (Moebius -> Moebius -> Moebius)
    -> (Moebius -> Moebius -> Moebius)
    -> Ord Moebius
    Moebius -> Moebius -> Bool
    Moebius -> Moebius -> Ordering
    Moebius -> Moebius -> Moebius
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    $ccompare :: Moebius -> Moebius -> Ordering
    compare :: Moebius -> Moebius -> Ordering
    $c< :: Moebius -> Moebius -> Bool
    < :: Moebius -> Moebius -> Bool
    $c<= :: Moebius -> Moebius -> Bool
    <= :: Moebius -> Moebius -> Bool
    $c> :: Moebius -> Moebius -> Bool
    > :: Moebius -> Moebius -> Bool
    $c>= :: Moebius -> Moebius -> Bool
    >= :: Moebius -> Moebius -> Bool
    $cmax :: Moebius -> Moebius -> Moebius
    max :: Moebius -> Moebius -> Moebius
    $cmin :: Moebius -> Moebius -> Moebius
    min :: Moebius -> Moebius -> Moebius
    Ord, Int -> Moebius -> ShowS
    [Moebius] -> ShowS
    Moebius -> String
    (Int -> Moebius -> ShowS)
    -> (Moebius -> String) -> ([Moebius] -> ShowS) -> Show Moebius
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: Int -> Moebius -> ShowS
    showsPrec :: Int -> Moebius -> ShowS
    $cshow :: Moebius -> String
    show :: Moebius -> String
    $cshowList :: [Moebius] -> ShowS
    showList :: [Moebius] -> ShowS
    Show)

    -- | Convert to any numeric type.
    runMoebius :: Num a => Moebius -> a
    runMoebius :: forall a. Num a => Moebius -> a
    runMoebius Moebius
    m = Integer -> a
    forall a. Num a => Integer -> a
    fromInteger (Int# -> Integer
    IS (Moebius -> Int#
    forall a. DataToTag a => a -> Int#
    dataToTag# Moebius
    m Int# -> Int# -> Int#
    -# Int#
    1#))

    fromMoebius :: Moebius -> Int8
    fromMoebius :: Moebius -> Int8
    fromMoebius Moebius
    m = Int -> Int8
    intToInt8 (Int -> Int8) -> Int -> Int8
    forall a b. (a -> b) -> a -> b
    $ Int# -> Int
    I# (Moebius -> Int#
    forall a. DataToTag a => a -> Int#
    dataToTag# Moebius
    m)
    {-# INLINE fromMoebius #-}

    toMoebius :: Int8 -> Moebius
    toMoebius :: Int8 -> Moebius
    toMoebius Int8
    i = let !(I# Int#
    i#) = Int8 -> Int
    int8ToInt Int8
    i in Int# -> Moebius
    forall a. Int# -> a
    tagToEnum# Int#
    i#
    {-# INLINE toMoebius #-}

    newtype instance U.MVector s Moebius = MV_Moebius (P.MVector s Int8)
    newtype instance U.Vector    Moebius = V_Moebius  (P.Vector    Int8)

    instance U.Unbox Moebius

    instance M.MVector U.MVector Moebius where
      {-# INLINE basicLength #-}
      {-# INLINE basicUnsafeSlice #-}
      {-# INLINE basicOverlaps #-}
      {-# INLINE basicUnsafeNew #-}
      {-# INLINE basicInitialize #-}
      {-# INLINE basicUnsafeReplicate #-}
      {-# INLINE basicUnsafeRead #-}
      {-# INLINE basicUnsafeWrite #-}
      {-# INLINE basicClear #-}
      {-# INLINE basicSet #-}
      {-# INLINE basicUnsafeCopy #-}
      {-# INLINE basicUnsafeGrow #-}
      basicLength :: forall s. MVector s Moebius -> Int
    basicLength (MV_Moebius MVector s Int8
    v) = MVector s Int8 -> Int
    forall s. MVector s Int8 -> Int
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
    M.basicLength MVector s Int8
    v
      basicUnsafeSlice :: forall s. Int -> Int -> MVector s Moebius -> MVector s Moebius
    basicUnsafeSlice Int
    i Int
    n (MV_Moebius MVector s Int8
    v) = MVector s Int8 -> MVector s Moebius
    forall s. MVector s Int8 -> MVector s Moebius
    MV_Moebius (MVector s Int8 -> MVector s Moebius)
    -> MVector s Int8 -> MVector s Moebius
    forall a b. (a -> b) -> a -> b
    $ Int -> Int -> MVector s Int8 -> MVector s Int8
    forall s. Int -> Int -> MVector s Int8 -> MVector s Int8
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    Int -> Int -> v s a -> v s a
    M.basicUnsafeSlice Int
    i Int
    n MVector s Int8
    v
      basicOverlaps :: forall s. MVector s Moebius -> MVector s Moebius -> Bool
    basicOverlaps (MV_Moebius MVector s Int8
    v1) (MV_Moebius MVector s Int8
    v2) = MVector s Int8 -> MVector s Int8 -> Bool
    forall s. MVector s Int8 -> MVector s Int8 -> Bool
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> v s a -> Bool
    M.basicOverlaps MVector s Int8
    v1 MVector s Int8
    v2
      basicUnsafeNew :: forall s. Int -> ST s (MVector s Moebius)
    basicUnsafeNew Int
    n = MVector s Int8 -> MVector s Moebius
    forall s. MVector s Int8 -> MVector s Moebius
    MV_Moebius (MVector s Int8 -> MVector s Moebius)
    -> ST s (MVector s Int8) -> ST s (MVector s Moebius)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Int -> ST s (MVector s Int8)
    forall s. Int -> ST s (MVector s Int8)
    forall (v :: * -> * -> *) a s. MVector v a => Int -> ST s (v s a)
    M.basicUnsafeNew Int
    n
      basicInitialize :: forall s. MVector s Moebius -> ST s ()
    basicInitialize (MV_Moebius MVector s Int8
    v) = MVector s Int8 -> ST s ()
    forall s. MVector s Int8 -> ST s ()
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
    M.basicInitialize MVector s Int8
    v
      basicUnsafeReplicate :: forall s. Int -> Moebius -> ST s (MVector s Moebius)
    basicUnsafeReplicate Int
    n Moebius
    x = MVector s Int8 -> MVector s Moebius
    forall s. MVector s Int8 -> MVector s Moebius
    MV_Moebius (MVector s Int8 -> MVector s Moebius)
    -> ST s (MVector s Int8) -> ST s (MVector s Moebius)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Int -> Int8 -> ST s (MVector s Int8)
    forall s. Int -> Int8 -> ST s (MVector s Int8)
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    Int -> a -> ST s (v s a)
    M.basicUnsafeReplicate Int
    n (Moebius -> Int8
    fromMoebius Moebius
    x)
      basicUnsafeRead :: forall s. MVector s Moebius -> Int -> ST s Moebius
    basicUnsafeRead (MV_Moebius MVector s Int8
    v) Int
    i = Int8 -> Moebius
    toMoebius (Int8 -> Moebius) -> ST s Int8 -> ST s Moebius
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> MVector s Int8 -> Int -> ST s Int8
    forall s. MVector s Int8 -> Int -> ST s Int8
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> Int -> ST s a
    M.basicUnsafeRead MVector s Int8
    v Int
    i
      basicUnsafeWrite :: forall s. MVector s Moebius -> Int -> Moebius -> ST s ()
    basicUnsafeWrite (MV_Moebius MVector s Int8
    v) Int
    i Moebius
    x = MVector s Int8 -> Int -> Int8 -> ST s ()
    forall s. MVector s Int8 -> Int -> Int8 -> ST s ()
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> Int -> a -> ST s ()
    M.basicUnsafeWrite MVector s Int8
    v Int
    i (Moebius -> Int8
    fromMoebius Moebius
    x)
      basicClear :: forall s. MVector s Moebius -> ST s ()
    basicClear (MV_Moebius MVector s Int8
    v) = MVector s Int8 -> ST s ()
    forall s. MVector s Int8 -> ST s ()
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> ST s ()
    M.basicClear MVector s Int8
    v
      basicSet :: forall s. MVector s Moebius -> Moebius -> ST s ()
    basicSet (MV_Moebius MVector s Int8
    v) Moebius
    x = MVector s Int8 -> Int8 -> ST s ()
    forall s. MVector s Int8 -> Int8 -> ST s ()
    forall (v :: * -> * -> *) a s. MVector v a => v s a -> a -> ST s ()
    M.basicSet MVector s Int8
    v (Moebius -> Int8
    fromMoebius Moebius
    x)
      basicUnsafeCopy :: forall s. MVector s Moebius -> MVector s Moebius -> ST s ()
    basicUnsafeCopy (MV_Moebius MVector s Int8
    v1) (MV_Moebius MVector s Int8
    v2) = MVector s Int8 -> MVector s Int8 -> ST s ()
    forall s. MVector s Int8 -> MVector s Int8 -> ST s ()
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> v s a -> ST s ()
    M.basicUnsafeCopy MVector s Int8
    v1 MVector s Int8
    v2
      basicUnsafeMove :: forall s. MVector s Moebius -> MVector s Moebius -> ST s ()
    basicUnsafeMove (MV_Moebius MVector s Int8
    v1) (MV_Moebius MVector s Int8
    v2) = MVector s Int8 -> MVector s Int8 -> ST s ()
    forall s. MVector s Int8 -> MVector s Int8 -> ST s ()
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> v s a -> ST s ()
    M.basicUnsafeMove MVector s Int8
    v1 MVector s Int8
    v2
      basicUnsafeGrow :: forall s. MVector s Moebius -> Int -> ST s (MVector s Moebius)
    basicUnsafeGrow (MV_Moebius MVector s Int8
    v) Int
    n = MVector s Int8 -> MVector s Moebius
    forall s. MVector s Int8 -> MVector s Moebius
    MV_Moebius (MVector s Int8 -> MVector s Moebius)
    -> ST s (MVector s Int8) -> ST s (MVector s Moebius)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> MVector s Int8 -> Int -> ST s (MVector s Int8)
    forall s. MVector s Int8 -> Int -> ST s (MVector s Int8)
    forall (v :: * -> * -> *) a s.
    MVector v a =>
    v s a -> Int -> ST s (v s a)
    M.basicUnsafeGrow MVector s Int8
    v Int
    n

    instance G.Vector U.Vector Moebius where
      {-# INLINE basicUnsafeFreeze #-}
      {-# INLINE basicUnsafeThaw #-}
      {-# INLINE basicLength #-}
      {-# INLINE basicUnsafeSlice #-}
      {-# INLINE basicUnsafeIndexM #-}
      {-# INLINE elemseq #-}
      basicUnsafeFreeze :: forall s. Mutable Vector s Moebius -> ST s (Vector Moebius)
    basicUnsafeFreeze (MV_Moebius MVector s Int8
    v) = Vector Int8 -> Vector Moebius
    V_Moebius (Vector Int8 -> Vector Moebius)
    -> ST s (Vector Int8) -> ST s (Vector Moebius)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Mutable Vector s Int8 -> ST s (Vector Int8)
    forall s. Mutable Vector s Int8 -> ST s (Vector Int8)
    forall (v :: * -> *) a s. Vector v a => Mutable v s a -> ST s (v a)
    G.basicUnsafeFreeze MVector s Int8
    Mutable Vector s Int8
    v
      basicUnsafeThaw :: forall s. Vector Moebius -> ST s (Mutable Vector s Moebius)
    basicUnsafeThaw (V_Moebius Vector Int8
    v) = MVector s Int8 -> MVector s Moebius
    forall s. MVector s Int8 -> MVector s Moebius
    MV_Moebius (MVector s Int8 -> MVector s Moebius)
    -> ST s (MVector s Int8) -> ST s (MVector s Moebius)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Vector Int8 -> ST s (Mutable Vector s Int8)
    forall s. Vector Int8 -> ST s (Mutable Vector s Int8)
    forall (v :: * -> *) a s. Vector v a => v a -> ST s (Mutable v s a)
    G.basicUnsafeThaw Vector Int8
    v
      basicLength :: Vector Moebius -> Int
    basicLength (V_Moebius Vector Int8
    v) = Vector Int8 -> Int
    forall (v :: * -> *) a. Vector v a => v a -> Int
    G.basicLength Vector Int8
    v
      basicUnsafeSlice :: Int -> Int -> Vector Moebius -> Vector Moebius
    basicUnsafeSlice Int
    i Int
    n (V_Moebius Vector Int8
    v) = Vector Int8 -> Vector Moebius
    V_Moebius (Vector Int8 -> Vector Moebius) -> Vector Int8 -> Vector Moebius
    forall a b. (a -> b) -> a -> b
    $ Int -> Int -> Vector Int8 -> Vector Int8
    forall (v :: * -> *) a. Vector v a => Int -> Int -> v a -> v a
    G.basicUnsafeSlice Int
    i Int
    n Vector Int8
    v
      basicUnsafeIndexM :: Vector Moebius -> Int -> Box Moebius
    basicUnsafeIndexM (V_Moebius Vector Int8
    v) Int
    i = Int8 -> Moebius
    toMoebius (Int8 -> Moebius) -> Box Int8 -> Box Moebius
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Vector Int8 -> Int -> Box Int8
    forall (v :: * -> *) a. Vector v a => v a -> Int -> Box a
    G.basicUnsafeIndexM Vector Int8
    v Int
    i
      basicUnsafeCopy :: forall s. Mutable Vector s Moebius -> Vector Moebius -> ST s ()
    basicUnsafeCopy (MV_Moebius MVector s Int8
    mv) (V_Moebius Vector Int8
    v) = Mutable Vector s Int8 -> Vector Int8 -> ST s ()
    forall s. Mutable Vector s Int8 -> Vector Int8 -> ST s ()
    forall (v :: * -> *) a s.
    Vector v a =>
    Mutable v s a -> v a -> ST s ()
    G.basicUnsafeCopy MVector s Int8
    Mutable Vector s Int8
    mv Vector Int8
    v
      elemseq :: forall b. Vector Moebius -> Moebius -> b -> b
    elemseq Vector Moebius
    _ = Moebius -> b -> b
    forall a b. a -> b -> b
    seq

    instance Semigroup Moebius where
      Moebius
    MoebiusZ <> :: Moebius -> Moebius -> Moebius
    <> Moebius
    _ = Moebius
    MoebiusZ
      Moebius
    _ <> Moebius
    MoebiusZ = Moebius
    MoebiusZ
      Moebius
    MoebiusP <> Moebius
    a = Moebius
    a
      Moebius
    a <> Moebius
    MoebiusP = Moebius
    a
      Moebius
    _ <> Moebius
    _ = Moebius
    MoebiusP

    instance Monoid Moebius where
      mempty :: Moebius
    mempty  = Moebius
    MoebiusP

    -- | Evaluate the Möbius function over a block.
    -- Value of @f@ at 0, if zero falls into block, is undefined.
    --
    -- Based on the sieving algorithm from p. 3 of <https://arxiv.org/pdf/1610.08551.pdf Computations of the Mertens function and improved bounds on the Mertens conjecture> by G. Hurst. It is approximately 5x faster than 'Math.NumberTheory.ArithmeticFunctions.SieveBlock.sieveBlockUnboxed'.
    --
    -- >>> sieveBlockMoebius 1 10
    -- [MoebiusP,MoebiusN,MoebiusN,MoebiusZ,MoebiusN,MoebiusP,MoebiusN,MoebiusZ,MoebiusZ,MoebiusP]
    sieveBlockMoebius
      :: Word
      -> Word
      -> U.Vector Moebius
    sieveBlockMoebius :: Word -> Word -> Vector Moebius
    sieveBlockMoebius Word
    _ Word
    0 = Vector Moebius
    forall a. Unbox a => Vector a
    U.empty
    sieveBlockMoebius Word
    lowIndex' Word
    len'
      = (Vector Word8 -> Vector Moebius
    forall a b. a -> b
    unsafeCoerce :: U.Vector Word8 -> U.Vector Moebius) (Vector Word8 -> Vector Moebius) -> Vector Word8 -> Vector Moebius
    forall a b. (a -> b) -> a -> b
    $ (forall s. ST s (Vector Word8)) -> Vector Word8
    forall a. (forall s. ST s a) -> a
    runST ((forall s. ST s (Vector Word8)) -> Vector Word8)
    -> (forall s. ST s (Vector Word8)) -> Vector Word8
    forall a b. (a -> b) -> a -> b
    $ do
        as <- Int -> Word8 -> ST s (MVector (PrimState (ST s)) Word8)
    forall (m :: * -> *) a.
    (PrimMonad m, Unbox a) =>
    Int -> a -> m (MVector (PrimState m) a)
    MU.replicate Int
    len (Word8
    0x80 :: Word8)
        forM_ ps $ \Int
    p -> do
          let offset :: Int
    offset  = Int -> Int
    forall a. Num a => a -> a
    negate Int
    lowIndex Int -> Int -> Int
    forall a. Integral a => a -> a -> a
    `mod` Int
    p
              offset2 :: Int
    offset2 = Int -> Int
    forall a. Num a => a -> a
    negate Int
    lowIndex Int -> Int -> Int
    forall a. Integral a => a -> a -> a
    `mod` (Int
    p Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * Int
    p)
              l :: Word8
              l :: Word8
    l = Int -> Word8
    intToWord8 (Int -> Word8) -> Int -> Word8
    forall a b. (a -> b) -> a -> b
    $ Int -> Int
    intLog2 Int
    p Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .|. Int
    1
          [Int] -> (Int -> ST s ()) -> ST s ()
    forall (t :: * -> *) (m :: * -> *) a b.
    (Foldable t, Monad m) =>
    t a -> (a -> m b) -> m ()
    forM_ [Int
    offset, Int
    offset Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    p .. Int
    len Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
    forall a b. (a -> b) -> a -> b
    $
            MVector (PrimState (ST s)) Word8
    -> (Word8 -> Word8) -> Int -> ST s ()
    forall (m :: * -> *) a.
    (PrimMonad m, Unbox a) =>
    MVector (PrimState m) a -> (a -> a) -> Int -> m ()
    MU.unsafeModify MVector s Word8
    MVector (PrimState (ST s)) Word8
    as (Word8 -> Word8 -> Word8
    forall a. Num a => a -> a -> a
    + Word8
    l)
          [Int] -> (Int -> ST s ()) -> ST s ()
    forall (t :: * -> *) (m :: * -> *) a b.
    (Foldable t, Monad m) =>
    t a -> (a -> m b) -> m ()
    forM_ [Int
    offset2, Int
    offset2 Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    p Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * Int
    p .. Int
    len Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1] ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
    forall a b. (a -> b) -> a -> b
    $ \Int
    ix ->
            MVector (PrimState (ST s)) Word8 -> Int -> Word8 -> ST s ()
    forall (m :: * -> *) a.
    (PrimMonad m, Unbox a) =>
    MVector (PrimState m) a -> Int -> a -> m ()
    MU.unsafeWrite MVector s Word8
    MVector (PrimState (ST s)) Word8
    as Int
    ix Word8
    0
        forM_ [0 .. len - 1] $ \Int
    ix ->
          MVector (PrimState (ST s)) Word8
    -> (Word8 -> Word8) -> Int -> ST s ()
    forall (m :: * -> *) a.
    (PrimMonad m, Unbox a) =>
    MVector (PrimState m) a -> (a -> a) -> Int -> m ()
    MU.unsafeModify MVector s Word8
    MVector (PrimState (ST s)) Word8
    as (Int -> Word8 -> Word8
    mapper Int
    ix) Int
    ix
        U.unsafeFreeze as

      where
        lowIndex :: Int
        lowIndex :: Int
    lowIndex = Word -> Int
    wordToInt Word
    lowIndex'

        len :: Int
        len :: Int
    len = Word -> Int
    wordToInt Word
    len'

        highIndex :: Int
        highIndex :: Int
    highIndex = Int
    lowIndex Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    len Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1

        -- Bit fiddling in 'mapper' is correct only
        -- if all sufficiently small (<= 191) primes has been sieved out.
        ps :: [Int]
        ps :: [Int]
    ps = (Prime Int -> Int) -> [Prime Int] -> [Int]
    forall a b. (a -> b) -> [a] -> [b]
    map Prime Int -> Int
    forall a. Prime a -> a
    unPrime [Int -> Prime Int
    forall a.
    (Bits a, Integral a, UniqueFactorisation a) =>
    a -> Prime a
    nextPrime Int
    2 .. Int -> Prime Int
    forall a.
    (Bits a, Integral a, UniqueFactorisation a) =>
    a -> Prime a
    precPrime (Int
    191 Int -> Int -> Int
    forall a. Ord a => a -> a -> a
    `max` Int -> Int
    forall a. Integral a => a -> a
    integerSquareRoot Int
    highIndex)]

        mapper :: Int -> Word8 -> Word8
        mapper :: Int -> Word8 -> Word8
    mapper Int
    ix Word8
    val
          | Word8
    val Word8 -> Word8 -> Word8
    forall a. Bits a => a -> a -> a
    .&. Word8
    0x80 Word8 -> Word8 -> Bool
    forall a. Eq a => a -> a -> Bool
    == Word8
    0x00
          = Word8
    1
          | Word8 -> Int
    word8ToInt (Word8
    val Word8 -> Word8 -> Word8
    forall a. Bits a => a -> a -> a
    .&. Word8
    0x7F) Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int -> Int
    intLog2 (Int
    ix Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    lowIndex) Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    5
            Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - (if Int
    ix Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    lowIndex Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0x100000   then Int
    2 else Int
    0)
            Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - (if Int
    ix Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    lowIndex Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    0x10000000 then Int
    1 else Int
    0)
          = (Word8
    val Word8 -> Word8 -> Word8
    forall a. Bits a => a -> a -> a
    .&. Word8
    1) Word8 -> Int -> Word8
    forall a. Bits a => a -> Int -> a
    `shiftL` Int
    1
          | Bool
    otherwise
          = ((Word8
    val Word8 -> Word8 -> Word8
    forall a. Bits a => a -> a -> a
    .&. Word8
    1) Word8 -> Word8 -> Word8
    forall a. Bits a => a -> a -> a
    `xor` Word8
    1) Word8 -> Int -> Word8
    forall a. Bits a => a -> Int -> a
    `shiftL` Int
    1