Data.BitStream.WheelMapping

Helpers for mapping to 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)

Documentation

fromWheel2 :: Word -> Word

fromWheel2 n is the (n+1)-th positive odd number. Sequence A005408.

map fromWheel2 [0..] == [ n | n <- [0..], n `gcd` 2 == 1 ]

> map fromWheel2 [0..9]
[1,3,5,7,9,11,13,15,17,19]

toWheel2 :: Word -> Word

Left inverse for fromWheel2. Monotonically non-decreasing function.

toWheel2 . fromWheel2 == id

fromWheel6 :: Word -> Word

fromWheel6 n is the (n+1)-th positive number, not divisible by 2 or 3. Sequence A007310.

map fromWheel6 [0..] == [ n | n <- [0..], n `gcd` 6 == 1 ]

> map fromWheel6 [0..9]
[1,5,7,11,13,17,19,23,25,29]

toWheel6 :: Word -> Word

Left inverse for fromWheel6. Monotonically non-decreasing function.

toWheel6 . fromWheel6 == id

fromWheel30 :: Word -> Word

fromWheel30 n is the (n+1)-th positive number, not divisible by 2, 3 or 5. Sequence A007775.

map fromWheel30 [0..] == [ n | n <- [0..], n `gcd` 30 == 1 ]

> map fromWheel30 [0..9]
[1,7,11,13,17,19,23,29,31,37]

toWheel30 :: Word -> Word

Left inverse for fromWheel30. Monotonically non-decreasing function.

toWheel30 . fromWheel30 == id

fromWheel210 :: Word -> Word

fromWheel210 n is the (n+1)-th positive number, not divisible by 2, 3, 5 or 7. Sequence A008364.

map fromWheel210 [0..] == [ n | n <- [0..], n `gcd` 210 == 1 ]

> map fromWheel210 [0..9]
[1,11,13,17,19,23,29,31,37,41]

toWheel210 :: Word -> Word

Left inverse for fromWheel210. Monotonically non-decreasing function.

toWheel210 . fromWheel210 == id