Copyright | (c) 2017 Andrew Lelechenko |
---|---|
License | MIT |
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]
toWheel2 :: Word -> Word Source #
Left inverse for fromWheel2
. Monotonically non-decreasing function.
toWheel2 . fromWheel2 == id
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]
toWheel6 :: Word -> Word Source #
Left inverse for fromWheel6
. Monotonically non-decreasing function.
toWheel6 . fromWheel6 == id
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]
toWheel30 :: Word -> Word Source #
Left inverse for fromWheel30
. Monotonically non-decreasing function.
toWheel30 . fromWheel30 == id
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]
toWheel210 :: Word -> Word Source #
Left inverse for fromWheel210
. Monotonically non-decreasing function.
toWheel210 . fromWheel210 == id