bit-stream-0.1.0.2: Lazy, infinite, compact stream of Bool with O(1) indexing.

Data.BitStream.WheelMapping

Description

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)

Synopsis

# Documentation

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]

Left inverse for fromWheel2. Monotonically non-decreasing function.

toWheel2 . fromWheel2 == id

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]

Left inverse for fromWheel6. Monotonically non-decreasing function.

toWheel6 . fromWheel6 == id

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]

Left inverse for fromWheel30. Monotonically non-decreasing function.

toWheel30 . fromWheel30 == id

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]

Left inverse for fromWheel210. Monotonically non-decreasing function.

toWheel210 . fromWheel210 == id