arithmoi-0.13.0.0: Efficient basic number-theoretic functions.

Copyright | (c) 2017 Andrew Lelechenko
License | MIT
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell | Safe-Inferred
Language | Haskell2010

Math.NumberTheory.ArithmeticFunctions.SieveBlock

Description

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 :: Prime Word -> Word -> a
  - sbcAppend :: a -> a -> a
  }
- multiplicativeSieveBlockConfig :: Num a => (Prime Word -> Word -> a) -> SieveBlockConfig a
- additiveSieveBlockConfig :: Num a => (Prime Word -> Word -> a) -> SieveBlockConfig a
- sieveBlock :: forall v a. Vector v a => SieveBlockConfig a -> Word -> Word -> v 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+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 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 -> (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 Source #

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

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

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 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 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 Source #

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