-- |
-- Module:      Data.BitStream.WheelMapping
-- Copyright:   (c) 2017 Andrew Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- Helpers for mapping to <http://mathworld.wolfram.com/RoughNumber.html rough numbers>
-- and back. Mostly useful in number theory.
--
-- __Example__
--
-- Let 'isPrime' be an expensive predicate, which checks whether its
-- argument is a prime number. We can improve performance of repetitive reevaluation by memoization:
--
-- > isPrimeBS :: BitStream
-- > isPrimeBS = tabulate isPrime
-- >
-- > isPrime' :: Word -> Bool
-- > isPrime' = index isPrimeBS
--
-- However, it is well-known that the only even prime is 2.
-- So we can save half of space by memoizing the predicate for odd
-- numbers only:
--
-- > isPrimeBS2 :: BitStream
-- > isPrimeBS2 = tabulate (\n -> isPrime (2 * n + 1))
-- >
-- > isPrime2' :: Word -> Bool
-- > isPrime2' n
-- >   | n == 2    = True
-- >   | even n    = False
-- >   | otherwise = index isPrimeBS2 ((n - 1) `quot` 2)
--
-- or, using 'fromWheel2' and 'toWheel2',
--
-- > isPrimeBS2 :: BitStream
-- > isPrimeBS2 = tabulate (isPrime . fromWheel2)
-- >
-- > isPrime2' :: Word -> Bool
-- > isPrime2' n
-- >   | n == 2    = True
-- >   | even n    = False
-- >   | otherwise = index isPrimeBS2 (toWheel2 n)
--
-- Well, we also know that all primes, except 2 and 3, are coprime to 6; and all primes, except 2, 3 and 5, are coprime 30. So we can save even more space by writing
--
-- > isPrimeBS6 :: BitStream
-- > isPrimeBS6 = tabulate (isPrime . fromWheel6)
-- >
-- > isPrime6' :: Word -> Bool
-- > isPrime6' n
-- >   | n `elem` [2, 3] = True
-- >   | n `gcd` 6 /= 1  = False
-- >   | otherwise       = index isPrimeBS6 (toWheel6 n)
--
-- or
--
-- > isPrimeBS30 :: BitStream
-- > isPrimeBS30 = tabulate (isPrime . fromWheel30)
-- >
-- > isPrime30' :: Word -> Bool
-- > isPrime30' n
-- >   | n `elem` [2, 3, 5] = True
-- >   | n `gcd` 30 /= 1    = False
-- >   | otherwise          = index isPrimeBS30 (toWheel30 n)

module Data.BitStream.WheelMapping
  ( fromWheel2
  , toWheel2
  , fromWheel6
  , toWheel6
  , fromWheel30
  , toWheel30
  , fromWheel210
  , toWheel210
  ) where

import Data.Bits
import qualified Data.Vector.Unboxed as U
import Data.Word

word2int :: Word -> Int
word2int :: Word -> Int
word2int = Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral

-- | Left inverse for 'fromWheel2'. Monotonically non-decreasing function.
--
-- prop> toWheel2 . fromWheel2 == id
toWheel2 :: Word -> Word
toWheel2 :: Word -> Word
toWheel2 Word
i = Word
i Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` Int
1
{-# INLINE toWheel2 #-}

-- | 'fromWheel2' n is the (n+1)-th positive odd number.
-- Sequence <https://oeis.org/A005408 A005408>.
--
-- prop> map fromWheel2 [0..] == [ n | n <- [0..], n `gcd` 2 == 1 ]
--
-- > > map fromWheel2 [0..9]
-- > [1,3,5,7,9,11,13,15,17,19]
fromWheel2 :: Word -> Word
fromWheel2 :: Word -> Word
fromWheel2 Word
i = Word
i Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` Int
1 Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
1
{-# INLINE fromWheel2 #-}

-- | Left inverse for 'fromWheel6'. Monotonically non-decreasing function.
--
-- prop> toWheel6 . fromWheel6 == id
toWheel6 :: Word -> Word
toWheel6 :: Word -> Word
toWheel6 Word
i = Word
i Word -> Word -> Word
forall a. Integral a => a -> a -> a
`quot` Word
3
{-# INLINE toWheel6 #-}

-- | 'fromWheel6' n is the (n+1)-th positive number, not divisible by 2 or 3.
-- Sequence <https://oeis.org/A007310 A007310>.
--
-- prop> map fromWheel6 [0..] == [ n | n <- [0..], n `gcd` 6 == 1 ]
--
-- > > map fromWheel6 [0..9]
-- > [1,5,7,11,13,17,19,23,25,29]
fromWheel6 :: Word -> Word
fromWheel6 :: Word -> Word
fromWheel6 Word
i = Word
i Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` Int
1 Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
i Word -> Word -> Word
forall a. Num a => a -> a -> a
+ (Word
i Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
1) Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
1
{-# INLINE fromWheel6 #-}

-- | Left inverse for 'fromWheel30'. Monotonically non-decreasing function.
--
-- prop> toWheel30 . fromWheel30 == id
toWheel30 :: Word -> Word
toWheel30 :: Word -> Word
toWheel30 Word
i = Word
q Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` Int
3 Word -> Word -> Word
forall a. Num a => a -> a -> a
+ (Word
r Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
r Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` Int
4) Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` Int
2
  where
    (Word
q, Word
r) = Word
i Word -> Word -> (Word, Word)
forall a. Integral a => a -> a -> (a, a)
`quotRem` Word
30
{-# INLINE toWheel30 #-}

-- | 'fromWheel30' n is the (n+1)-th positive number, not divisible by 2, 3 or 5.
-- Sequence <https://oeis.org/A007775 A007775>.
--
-- prop> map fromWheel30 [0..] == [ n | n <- [0..], n `gcd` 30 == 1 ]
--
-- > > map fromWheel30 [0..9]
-- > [1,7,11,13,17,19,23,29,31,37]
fromWheel30 :: Word -> Word
fromWheel30 :: Word -> Word
fromWheel30 Word
i = ((Word
i Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` Int
2 Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
i Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` Int
2) Word -> Word -> Word
forall a. Bits a => a -> a -> a
.|. Word
1)
              Word -> Word -> Word
forall a. Num a => a -> a -> a
+ ((Word
i Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` Int
1 Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
i Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftR` Int
1) Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
2)
{-# INLINE fromWheel30 #-}

-- | Left inverse for 'fromWheel210'. Monotonically non-decreasing function.
--
-- prop> toWheel210 . fromWheel210 == id
toWheel210 :: Word -> Word
toWheel210 :: Word -> Word
toWheel210 Word
i = Word
q Word -> Word -> Word
forall a. Num a => a -> a -> a
* Word
48 Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word8 -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word8
toWheel210Table Vector Word8 -> Int -> Word8
forall a. Unbox a => Vector a -> Int -> a
`U.unsafeIndex` Word -> Int
word2int Word
r)
  where
    (Word
q, Word
r) = Word
i Word -> Word -> (Word, Word)
forall a. Integral a => a -> a -> (a, a)
`quotRem` Word
210
{-# INLINE toWheel210 #-}

toWheel210Table :: U.Vector Word8
toWheel210Table :: Vector Word8
toWheel210Table = [Word8] -> Vector Word8
forall a. Unbox a => [a] -> Vector a
U.fromList [Word8
0, Word8
0, Word8
0, Word8
0, Word8
0, Word8
0, Word8
0, Word8
0, Word8
0, Word8
0, Word8
0, Word8
1, Word8
1, Word8
2, Word8
2, Word8
2, Word8
2, Word8
3, Word8
3, Word8
4, Word8
4, Word8
4, Word8
4, Word8
5, Word8
5, Word8
5, Word8
5, Word8
5, Word8
5, Word8
6, Word8
6, Word8
7, Word8
7, Word8
7, Word8
7, Word8
7, Word8
7, Word8
8, Word8
8, Word8
8, Word8
8, Word8
9, Word8
9, Word8
10, Word8
10, Word8
10, Word8
10, Word8
11, Word8
11, Word8
11, Word8
11, Word8
11, Word8
11, Word8
12, Word8
12, Word8
12, Word8
12, Word8
12, Word8
12, Word8
13, Word8
13, Word8
14, Word8
14, Word8
14, Word8
14, Word8
14, Word8
14, Word8
15, Word8
15, Word8
15, Word8
15, Word8
16, Word8
16, Word8
17, Word8
17, Word8
17, Word8
17, Word8
17, Word8
17, Word8
18, Word8
18, Word8
18, Word8
18, Word8
19, Word8
19, Word8
19, Word8
19, Word8
19, Word8
19, Word8
20, Word8
20, Word8
20, Word8
20, Word8
20, Word8
20, Word8
20, Word8
20, Word8
21, Word8
21, Word8
21, Word8
21, Word8
22, Word8
22, Word8
23, Word8
23, Word8
23, Word8
23, Word8
24, Word8
24, Word8
25, Word8
25, Word8
25, Word8
25, Word8
26, Word8
26, Word8
26, Word8
26, Word8
26, Word8
26, Word8
26, Word8
26, Word8
27, Word8
27, Word8
27, Word8
27, Word8
27, Word8
27, Word8
28, Word8
28, Word8
28, Word8
28, Word8
29, Word8
29, Word8
29, Word8
29, Word8
29, Word8
29, Word8
30, Word8
30, Word8
31, Word8
31, Word8
31, Word8
31, Word8
32, Word8
32, Word8
32, Word8
32, Word8
32, Word8
32, Word8
33, Word8
33, Word8
34, Word8
34, Word8
34, Word8
34, Word8
34, Word8
34, Word8
35, Word8
35, Word8
35, Word8
35, Word8
35, Word8
35, Word8
36, Word8
36, Word8
36, Word8
36, Word8
37, Word8
37, Word8
38, Word8
38, Word8
38, Word8
38, Word8
39, Word8
39, Word8
39, Word8
39, Word8
39, Word8
39, Word8
40, Word8
40, Word8
41, Word8
41, Word8
41, Word8
41, Word8
41, Word8
41, Word8
42, Word8
42, Word8
42, Word8
42, Word8
43, Word8
43, Word8
44, Word8
44, Word8
44, Word8
44, Word8
45, Word8
45, Word8
46, Word8
46, Word8
46, Word8
46, Word8
46, Word8
46, Word8
46, Word8
46, Word8
46, Word8
46, Word8
47]

-- | 'fromWheel210' n is the (n+1)-th positive number, not divisible by 2, 3, 5 or 7.
-- Sequence <https://oeis.org/A008364 A008364>.
--
-- prop> map fromWheel210 [0..] == [ n | n <- [0..], n `gcd` 210 == 1 ]
--
-- > > map fromWheel210 [0..9]
-- > [1,11,13,17,19,23,29,31,37,41]
fromWheel210 :: Word -> Word
fromWheel210 :: Word -> Word
fromWheel210 Word
i = Word
q Word -> Word -> Word
forall a. Num a => a -> a -> a
* Word
210 Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word8 -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Vector Word8
fromWheel210Table Vector Word8 -> Int -> Word8
forall a. Unbox a => Vector a -> Int -> a
`U.unsafeIndex` Word -> Int
word2int Word
r)
  where
    (Word
q, Word
r) = Word
i Word -> Word -> (Word, Word)
forall a. Integral a => a -> a -> (a, a)
`quotRem` Word
48
{-# INLINE fromWheel210 #-}

fromWheel210Table :: U.Vector Word8
fromWheel210Table :: Vector Word8
fromWheel210Table = [Word8] -> Vector Word8
forall a. Unbox a => [a] -> Vector a
U.fromList [Word8
1, Word8
11, Word8
13, Word8
17, Word8
19, Word8
23, Word8
29, Word8
31, Word8
37, Word8
41, Word8
43, Word8
47, Word8
53, Word8
59, Word8
61, Word8
67, Word8
71, Word8
73, Word8
79, Word8
83, Word8
89, Word8
97, Word8
101, Word8
103, Word8
107, Word8
109, Word8
113, Word8
121, Word8
127, Word8
131, Word8
137, Word8
139, Word8
143, Word8
149, Word8
151, Word8
157, Word8
163, Word8
167, Word8
169, Word8
173, Word8
179, Word8
181, Word8
187, Word8
191, Word8
193, Word8
197, Word8
199, Word8
209]