Data.Chimera.WheelMapping

Helpers for mapping to rough numbers and back. This has various applications in number theory.

Example

Let isPrime be an expensive predicate, which checks whether its argument is a prime number. We can memoize it as usual:

isPrimeCache1 :: UChimera Bool
isPrimeCache1 = tabulate isPrime

isPrime1 :: Word -> Bool
isPrime1 = index isPrimeCache1

But one may argue that since the only even prime number is 2, it is quite wasteful to cache isPrime for even arguments. So we can save half the space by memoizing it for odd numbers only:

isPrimeCache2 :: UChimera Bool
isPrimeCache2 = tabulate (isPrime . (\n -> 2 * n + 1))

isPrime2 :: Word -> Bool
isPrime2 n
  | n == 2    = True
  | even n    = False
  | otherwise = index isPrimeCache2 ((n - 1) `quot` 2)

Here \n -> 2 * n + 1 maps n to the (n+1)-th odd number, and \n -> (n - 1) `quot` 2 takes it back. These functions are available below as fromWheel2 and toWheel2.

Odd numbers are the simplest example of numbers, lacking small prime factors (so called rough numbers). Removing numbers, having small prime factors, is sometimes called wheel sieving.

One can go further and exclude not only even numbers, but also integers, divisible by 3. To do this we need a function which maps n to the (n+1)-th number coprime with 2 and 3 (thus, with 6) and its inverse: namely, fromWheel6 and toWheel6. Then write

isPrimeCache6 :: UChimera Bool
isPrimeCache6 = tabulate (isPrime . fromWheel6)

isPrime6 :: Word -> Bool
isPrime6 n
  | n `elem` [2, 3] = True
  | n `gcd` 6 /= 1  = False
  | otherwise       = index isPrimeCache6 (toWheel6 n)

Thus, the wheel of 6 saves more space, improving memory locality.

(If you need to reduce memory consumption even further, consider using Bit wrapper, which provides an instance of unboxed vector, packing one boolean per bit instead of one boolean per byte for Bool)

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