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.

>>> import Math.NumberTheory.ArithmeticFunctions
>>> 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 -> (unPrime p - 1) * unPrime p ^ (a - 1)
  , sbcAppend               = (*)
  }

Constructors

SieveBlockConfig

Fields

• sbcEmpty :: a

  value of a function on 1

• sbcFunctionOnPrimePower :: Prime 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 => (Prime Word -> Word -> a) -> SieveBlockConfig a

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

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

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

sieveBlock :: forall v a. Vector v a => SieveBlockConfig a -> Word -> Word -> v 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, following code lists smallest prime factors:

>>> sieveBlock (SieveBlockConfig maxBound (\p _ -> unPrime p) min) 2 10 :: Data.Vector.Vector Word
[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 -> [(unPrime p, k)]) (++)) 2 10 :: Data.Vector.Vector [(Word, Word)]
[[(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

This is sieveBlock specialized to unboxed vectors.

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