    -- |
    -- Module:      Math.NumberTheory.Primes.Sieve.Indexing
    -- Copyright:   (c) 2011 Daniel Fischer
    -- Licence:     MIT
    -- Maintainer:  Daniel Fischer <daniel.is.fischer@googlemail.com>
    --
    -- Auxiliary stuff, conversion between number and index,
    -- remainders modulo 30 and related things.
    module Math.NumberTheory.Primes.Sieve.Indexing
        ( idxPr
        , toPrim
        , rho
        ) where

    import Data.Array.Base
    import Data.Bits

    {-# INLINE idxPr #-}
    idxPr :: Integral a => a -> (Int,Int)
    idxPr :: forall a. Integral a => a -> (Int, Int)
    idxPr a
    n0
        | a
    n0 a -> a -> Bool
    forall a. Ord a => a -> a -> Bool
    < a
    7    = (Int
    0, Int
    0)
        | Bool
    otherwise = (a -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral a
    bytes0, Int
    rm3)
      where
        n :: a
    n = if a -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral a
    n0 Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    1 Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == (Int
    1 :: Int)
                then a
    n0 else a
    n0 a -> a -> a
    forall a. Num a => a -> a -> a
    - a
    1
        (a
    bytes0,a
    rm0) = (a
    na -> a -> a
    forall a. Num a => a -> a -> a
    -a
    7) a -> a -> (a, a)
    forall a. Integral a => a -> a -> (a, a)
    `quotRem` a
    30
        rm1 :: Int
    rm1 = a -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral a
    rm0
        rm2 :: Int
    rm2 = Int
    rm1 Int -> Int -> Int
    forall a. Integral a => a -> a -> a
    `quot` Int
    3
        rm3 :: Int
    rm3 = Int -> Int -> Int
    forall a. Ord a => a -> a -> a
    min Int
    7 (if Int
    rm2 Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    5 then Int
    rm2Int -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1 else Int
    rm2)

    {-# INLINE toPrim #-}
    toPrim :: Num a => Int -> a
    toPrim :: forall a. Num a => Int -> a
    toPrim Int
    ix = a
    30a -> a -> a
    forall a. Num a => a -> a -> a
    *Int -> a
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral Int
    k a -> a -> a
    forall a. Num a => a -> a -> a
    + Int -> a
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Int -> Int
    rho Int
    i)
      where
        i :: Int
    i = Int
    ix Int -> Int -> Int
    forall a. Bits a => a -> a -> a
    .&. Int
    7
        k :: Int
    k = Int
    ix Int -> Int -> Int
    forall a. Bits a => a -> Int -> a
    `shiftR` Int
    3

    {-# INLINE rho #-}
    rho :: Int -> Int
    rho :: Int -> Int
    rho = UArray Int Int -> Int -> Int
    forall i. Ix i => UArray i Int -> Int -> Int
    forall (a :: * -> * -> *) e i.
    (IArray a e, Ix i) =>
    a i e -> Int -> e
    unsafeAt UArray Int Int
    residues

    residues :: UArray Int Int
    residues :: UArray Int Int
    residues = (Int, Int) -> [Int] -> UArray Int Int
    forall (a :: * -> * -> *) e i.
    (IArray a e, Ix i) =>
    (i, i) -> [e] -> a i e
    listArray (Int
    0,Int
    7) [Int
    7,Int
    11,Int
    13,Int
    17,Int
    19,Int
    23,Int
    29,Int
    31]