Math.NumberTheory.ArithmeticFunctions.SieveBlock

Bulk evaluation of arithmetic functions over continuous intervals without factorisation.

Documentation

runFunctionOverBlock :: ArithmeticFunction Word a -> Word -> Word -> Vector a

runFunctionOverBlock f x l evaluates an arithmetic function for integers between x and x+l-1 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 non-commutative 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

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               = (*)
  }

Constructors

SieveBlockConfig

Fields

• sbcEmpty :: a

  value of a function on 1

• sbcFunctionOnPrimePower :: Word -> Word -> a

  how to evaluate a function on prime powers

• sbcAppend :: a -> a -> a

  how to combine values of a function on coprime arguments

multiplicativeSieveBlockConfig :: Num a => (Word -> Word -> a) -> SieveBlockConfig a

Create a config for a multiplicative function from its definition on prime powers.

additiveSieveBlockConfig :: Num a => (Word -> Word -> a) -> SieveBlockConfig a

Create a config for an additive function from its definition on prime powers.

sieveBlock :: SieveBlockConfig a -> Word -> Word -> Vector a

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 use-cases its time complexity is O(x^(1+ε)).

sieveBlock is similar to sieveBlockUnboxed up to flavour of Vector, but is typically 7x-10x 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

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 use-cases 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

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]