chimera-0.4.1.0: Lazy infinite streams with O(1) indexing and applications for memoization

Copyright | (c) 2017 Andrew Lelechenko
License | BSD3
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | None
Language | Haskell2010

Data.Chimera.WheelMapping

Description

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`)

Synopsis

- fromWheel2 :: Word -> Word
- toWheel2 :: Word -> Word
- fromWheel6 :: Word -> Word
- toWheel6 :: Word -> Word
- fromWheel30 :: Word -> Word
- toWheel30 :: Word -> Word
- fromWheel210 :: Word -> Word
- toWheel210 :: Word -> Word

# Documentation

fromWheel2 :: Word -> Word Source #

`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]

Since: 0.2.0.0

toWheel2 :: Word -> Word Source #

Left inverse for `fromWheel2`. Monotonically non-decreasing function.

    toWheel2 . fromWheel2 == id

Since: 0.2.0.0

fromWheel6 :: Word -> Word Source #

`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]

Since: 0.2.0.0

toWheel6 :: Word -> Word Source #

Left inverse for `fromWheel6`. Monotonically non-decreasing function.

    toWheel6 . fromWheel6 == id

Since: 0.2.0.0

fromWheel30 :: Word -> Word Source #

`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]

Since: 0.2.0.0

toWheel30 :: Word -> Word Source #

Left inverse for `fromWheel30`. Monotonically non-decreasing function.

    toWheel30 . fromWheel30 == id

Since: 0.2.0.0

fromWheel210 :: Word -> Word Source #

`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]

Since: 0.2.0.0

toWheel210 :: Word -> Word Source #

Left inverse for `fromWheel210`. Monotonically non-decreasing function.

    toWheel210 . fromWheel210 == id

Since: 0.2.0.0