1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
-- |
-- 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 n0
| n0 < 7 = (0, 0)
| otherwise = (fromIntegral bytes0, rm3)
where
n = if fromIntegral n0 .&. 1 == (1 :: Int)
then n0 else n0 - 1
(bytes0,rm0) = (n-7) `quotRem` 30
rm1 = fromIntegral rm0
rm2 = rm1 `quot` 3
rm3 = min 7 (if rm2 > 5 then rm2-1 else rm2)
{-# INLINE toPrim #-}
toPrim :: Num a => Int -> a
toPrim ix = 30*fromIntegral k + fromIntegral (rho i)
where
i = ix .&. 7
k = ix `shiftR` 3
{-# INLINE rho #-}
rho :: Int -> Int
rho = unsafeAt residues
residues :: UArray Int Int
residues = listArray (0,7) [7,11,13,17,19,23,29,31]
|
