-- |
-- 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 CPP                   #-}
{-# 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
#if __GLASGOW_HASKELL__ < 803
import Data.Semigroup
#endif
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.Integer.GMP.Internals
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
/= :: Moebius -> Moebius -> Bool
$c/= :: Moebius -> Moebius -> Bool
== :: Moebius -> Moebius -> Bool
$c== :: 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
min :: Moebius -> Moebius -> Moebius
$cmin :: Moebius -> Moebius -> Moebius
max :: Moebius -> Moebius -> Moebius
$cmax :: Moebius -> Moebius -> Moebius
>= :: Moebius -> Moebius -> Bool
$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
compare :: Moebius -> Moebius -> Ordering
$ccompare :: Moebius -> Moebius -> Ordering
$cp1Ord :: Eq 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
showList :: [Moebius] -> ShowS
$cshowList :: [Moebius] -> ShowS
show :: Moebius -> String
$cshow :: Moebius -> String
showsPrec :: Int -> Moebius -> ShowS
$cshowsPrec :: Int -> Moebius -> ShowS
Show)

-- | Convert to any numeric type.
runMoebius :: Num a => Moebius -> a
runMoebius :: Moebius -> a
runMoebius Moebius
m = Integer -> a
forall a. Num a => Integer -> a
fromInteger (Int# -> Integer
S# (Moebius -> Int#
forall 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. 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 :: MVector s Moebius -> Int
basicLength (MV_Moebius v) = MVector s Int8 -> Int
forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int
M.basicLength MVector s Int8
v
  basicUnsafeSlice :: Int -> Int -> MVector s Moebius -> MVector s Moebius
basicUnsafeSlice Int
i Int
n (MV_Moebius 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 (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 :: MVector s Moebius -> MVector s Moebius -> Bool
basicOverlaps (MV_Moebius v1) (MV_Moebius v2) = 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 :: Int -> m (MVector (PrimState m) Moebius)
basicUnsafeNew Int
n = MVector (PrimState m) Int8 -> MVector (PrimState m) Moebius
forall s. MVector s Int8 -> MVector s Moebius
MV_Moebius (MVector (PrimState m) Int8 -> MVector (PrimState m) Moebius)
-> m (MVector (PrimState m) Int8)
-> m (MVector (PrimState m) Moebius)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> m (MVector (PrimState m) Int8)
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
Int -> m (v (PrimState m) a)
M.basicUnsafeNew Int
n
  basicInitialize :: MVector (PrimState m) Moebius -> m ()
basicInitialize (MV_Moebius v) = MVector (PrimState m) Int8 -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> m ()
M.basicInitialize MVector (PrimState m) Int8
v
  basicUnsafeReplicate :: Int -> Moebius -> m (MVector (PrimState m) Moebius)
basicUnsafeReplicate Int
n Moebius
x = MVector (PrimState m) Int8 -> MVector (PrimState m) Moebius
forall s. MVector s Int8 -> MVector s Moebius
MV_Moebius (MVector (PrimState m) Int8 -> MVector (PrimState m) Moebius)
-> m (MVector (PrimState m) Int8)
-> m (MVector (PrimState m) Moebius)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> Int8 -> m (MVector (PrimState m) Int8)
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
Int -> a -> m (v (PrimState m) a)
M.basicUnsafeReplicate Int
n (Moebius -> Int8
fromMoebius Moebius
x)
  basicUnsafeRead :: MVector (PrimState m) Moebius -> Int -> m Moebius
basicUnsafeRead (MV_Moebius v) Int
i = Int8 -> Moebius
toMoebius (Int8 -> Moebius) -> m Int8 -> m Moebius
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState m) Int8 -> Int -> m Int8
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m a
M.basicUnsafeRead MVector (PrimState m) Int8
v Int
i
  basicUnsafeWrite :: MVector (PrimState m) Moebius -> Int -> Moebius -> m ()
basicUnsafeWrite (MV_Moebius v) Int
i Moebius
x = MVector (PrimState m) Int8 -> Int -> Int8 -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> a -> m ()
M.basicUnsafeWrite MVector (PrimState m) Int8
v Int
i (Moebius -> Int8
fromMoebius Moebius
x)
  basicClear :: MVector (PrimState m) Moebius -> m ()
basicClear (MV_Moebius v) = MVector (PrimState m) Int8 -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> m ()
M.basicClear MVector (PrimState m) Int8
v
  basicSet :: MVector (PrimState m) Moebius -> Moebius -> m ()
basicSet (MV_Moebius v) Moebius
x = MVector (PrimState m) Int8 -> Int8 -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> a -> m ()
M.basicSet MVector (PrimState m) Int8
v (Moebius -> Int8
fromMoebius Moebius
x)
  basicUnsafeCopy :: MVector (PrimState m) Moebius
-> MVector (PrimState m) Moebius -> m ()
basicUnsafeCopy (MV_Moebius v1) (MV_Moebius v2) = MVector (PrimState m) Int8 -> MVector (PrimState m) Int8 -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
M.basicUnsafeCopy MVector (PrimState m) Int8
v1 MVector (PrimState m) Int8
v2
  basicUnsafeMove :: MVector (PrimState m) Moebius
-> MVector (PrimState m) Moebius -> m ()
basicUnsafeMove (MV_Moebius v1) (MV_Moebius v2) = MVector (PrimState m) Int8 -> MVector (PrimState m) Int8 -> m ()
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> v (PrimState m) a -> m ()
M.basicUnsafeMove MVector (PrimState m) Int8
v1 MVector (PrimState m) Int8
v2
  basicUnsafeGrow :: MVector (PrimState m) Moebius
-> Int -> m (MVector (PrimState m) Moebius)
basicUnsafeGrow (MV_Moebius v) Int
n = MVector (PrimState m) Int8 -> MVector (PrimState m) Moebius
forall s. MVector s Int8 -> MVector s Moebius
MV_Moebius (MVector (PrimState m) Int8 -> MVector (PrimState m) Moebius)
-> m (MVector (PrimState m) Int8)
-> m (MVector (PrimState m) Moebius)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MVector (PrimState m) Int8 -> Int -> m (MVector (PrimState m) Int8)
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
v (PrimState m) a -> Int -> m (v (PrimState m) a)
M.basicUnsafeGrow MVector (PrimState m) Int8
v Int
n

instance G.Vector U.Vector Moebius where
  {-# INLINE basicUnsafeFreeze #-}
  {-# INLINE basicUnsafeThaw #-}
  {-# INLINE basicLength #-}
  {-# INLINE basicUnsafeSlice #-}
  {-# INLINE basicUnsafeIndexM #-}
  {-# INLINE elemseq #-}
  basicUnsafeFreeze :: Mutable Vector (PrimState m) Moebius -> m (Vector Moebius)
basicUnsafeFreeze (MV_Moebius v) = Vector Int8 -> Vector Moebius
V_Moebius (Vector Int8 -> Vector Moebius)
-> m (Vector Int8) -> m (Vector Moebius)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Mutable Vector (PrimState m) Int8 -> m (Vector Int8)
forall (v :: * -> *) a (m :: * -> *).
(Vector v a, PrimMonad m) =>
Mutable v (PrimState m) a -> m (v a)
G.basicUnsafeFreeze MVector (PrimState m) Int8
Mutable Vector (PrimState m) Int8
v
  basicUnsafeThaw :: Vector Moebius -> m (Mutable Vector (PrimState m) Moebius)
basicUnsafeThaw (V_Moebius v) = MVector (PrimState m) Int8 -> MVector (PrimState m) Moebius
forall s. MVector s Int8 -> MVector s Moebius
MV_Moebius (MVector (PrimState m) Int8 -> MVector (PrimState m) Moebius)
-> m (MVector (PrimState m) Int8)
-> m (MVector (PrimState m) Moebius)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Vector Int8 -> m (Mutable Vector (PrimState m) Int8)
forall (v :: * -> *) a (m :: * -> *).
(Vector v a, PrimMonad m) =>
v a -> m (Mutable v (PrimState m) a)
G.basicUnsafeThaw Vector Int8
v
  basicLength :: Vector Moebius -> Int
basicLength (V_Moebius 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 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 -> m Moebius
basicUnsafeIndexM (V_Moebius v) Int
i = Int8 -> Moebius
toMoebius (Int8 -> Moebius) -> m Int8 -> m Moebius
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Vector Int8 -> Int -> m Int8
forall (v :: * -> *) a (m :: * -> *).
(Vector v a, Monad m) =>
v a -> Int -> m a
G.basicUnsafeIndexM Vector Int8
v Int
i
  basicUnsafeCopy :: Mutable Vector (PrimState m) Moebius -> Vector Moebius -> m ()
basicUnsafeCopy (MV_Moebius mv) (V_Moebius v) = Mutable Vector (PrimState m) Int8 -> Vector Int8 -> m ()
forall (v :: * -> *) a (m :: * -> *).
(Vector v a, PrimMonad m) =>
Mutable v (PrimState m) a -> v a -> m ()
G.basicUnsafeCopy MVector (PrimState m) Int8
Mutable Vector (PrimState m) Int8
mv Vector Int8
v
  elemseq :: Vector Moebius -> Moebius -> b -> b
elemseq Vector Moebius
_ = Moebius -> 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
  mappend :: Moebius -> Moebius -> Moebius
mappend = Moebius -> Moebius -> Moebius
forall a. Semigroup a => a -> a -> a
(<>)

-- | 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
    MVector s Word8
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)
    [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int]
ps ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \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
    [Int] -> (Int -> ST s ()) -> ST s ()
forall (t :: * -> *) (m :: * -> *) a b.
(Foldable t, Monad m) =>
t a -> (a -> m b) -> m ()
forM_ [Int
0 .. 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
-> (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
    MVector (PrimState (ST s)) Word8 -> ST s (Vector Word8)
forall a (m :: * -> *).
(Unbox a, PrimMonad m) =>
MVector (PrimState m) a -> m (Vector a)
U.unsafeFreeze MVector s Word8
MVector (PrimState (ST s)) Word8
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