Copyright  (c) 2017 Andrew Lelechenko 

License  MIT 
Maintainer  Andrew Lelechenko <andrew.lelechenko@gmail.com> 
Stability  Provisional 
Portability  Nonportable (GHC extensions) 
Safe Haskell  None 
Language  Haskell2010 
Bulk evaluation of arithmetic functions over continuous intervals without factorisation.
Synopsis
 runFunctionOverBlock :: ArithmeticFunction Word a > Word > Word > Vector a
 data SieveBlockConfig a = SieveBlockConfig {
 sbcEmpty :: a
 sbcFunctionOnPrimePower :: Word > Word > a
 sbcAppend :: a > a > a
 multiplicativeSieveBlockConfig :: Num a => (Word > Word > a) > SieveBlockConfig a
 additiveSieveBlockConfig :: Num a => (Word > Word > a) > SieveBlockConfig a
 sieveBlock :: SieveBlockConfig a > Word > Word > Vector a
 sieveBlockUnboxed :: Unbox a => SieveBlockConfig a > Word > Word > Vector a
 sieveBlockMoebius :: Word > Word > Vector Moebius
Documentation
runFunctionOverBlock :: ArithmeticFunction Word a > Word > Word > Vector a Source #
runFunctionOverBlock
f
x
l
evaluates an arithmetic function
for integers between x
and x+l1
and returns a vector of length l
.
It completely avoids factorisation, so it is asymptotically faster than
pointwise evaluation of f
.
Value of f
at 0, if zero falls into block, is undefined.
Beware that for underlying noncommutative monoids the results may potentially
differ from pointwise application via runFunction
.
This is a thin wrapper over sieveBlock
, read more details there.
>>>
runFunctionOverBlock carmichaelA 1 10
[1,1,2,2,4,2,6,2,6,4]
data SieveBlockConfig a Source #
A record, which specifies a function to evaluate over a block.
For example, here is a configuration for the totient function:
SieveBlockConfig { sbcEmpty = 1 , sbcFunctionOnPrimePower = (\p a > (p  1) * p ^ (a  1) , sbcAppend = (*) }
SieveBlockConfig  

multiplicativeSieveBlockConfig :: Num a => (Word > Word > a) > SieveBlockConfig a Source #
Create a config for a multiplicative function from its definition on prime powers.
additiveSieveBlockConfig :: Num a => (Word > Word > a) > SieveBlockConfig a Source #
Create a config for an additive function from its definition on prime powers.
sieveBlock :: SieveBlockConfig a > Word > Word > Vector a Source #
Evaluate a function over a block in accordance to provided configuration.
Value of f
at 0, if zero falls into block, is undefined.
Based on Algorithm M of Parity of the number of primes in a given interval and algorithms of the sublinear summation by A. V. Lelechenko. See Lemma 2 on p. 5 on its algorithmic complexity. For the majority of usecases its time complexity is O(x^(1+ε)).
sieveBlock
is similar to sieveBlockUnboxed
up to flavour of Vector
,
but is typically 7x10x slower and consumes 3x memory.
Use unboxed version whenever possible.
For example, following code lists smallest prime factors:
>>>
sieveBlock (SieveBlockConfig maxBound (\p _ > p) min) 2 10
[2,3,2,5,2,7,2,3,2,11]
And this is how to factorise all numbers in a block:
>>>
sieveBlock (SieveBlockConfig [] (\p k > [(p,k)]) (++)) 2 10
[[(2,1)],[(3,1)],[(2,2)],[(5,1)],[(2,1),(3,1)],[(7,1)],[(2,3)],[(3,2)],[(2,1),(5,1)],[(11,1)]]
sieveBlockUnboxed :: Unbox a => SieveBlockConfig a > Word > Word > Vector a Source #
Evaluate a function over a block in accordance to provided configuration.
Value of f
at 0, if zero falls into block, is undefined.
Based on Algorithm M of Parity of the number of primes in a given interval and algorithms of the sublinear summation by A. V. Lelechenko. See Lemma 2 on p. 5 on its algorithmic complexity. For the majority of usecases its time complexity is O(x^(1+ε)).
For example, here is an analogue of divisor function tau
:
>>>
sieveBlockUnboxed (SieveBlockConfig 1 (\_ a > a + 1) (*)) 1 10
[1,2,2,3,2,4,2,4,3,4]
sieveBlockMoebius :: Word > Word > Vector Moebius Source #
Evaluate the Möbius function over a block.
Value of f
at 0, if zero falls into block, is undefined.
Based on the sieving algorithm from p. 3 of Computations of the Mertens function and improved bounds on the Mertens conjecture by G. Hurst. It is approximately 5x faster than sieveBlockUnboxed
.
>>>
sieveBlockMoebius 1 10
[MoebiusP, MoebiusN, MoebiusN, MoebiusZ, MoebiusN, MoebiusP, MoebiusN, MoebiusZ, MoebiusZ, MoebiusP]