-- |
-- 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 :: 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 :: 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 (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]