arithmoi-0.13.0.0: Efficient basic number-theoretic functions.

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

Math.NumberTheory.ArithmeticFunctions.Moebius

Description

Values of Möbius function.

Synopsis

- data Moebius
  - = MoebiusN
  - | MoebiusZ
  - | MoebiusP
- runMoebius :: Num a => Moebius -> a
- sieveBlockMoebius :: Word -> Word -> Vector Moebius

# Documentation

data Moebius Source #

Represents three possible values of Möbius function.

Constructors

MoebiusN

- 1

MoebiusZ | 0
MoebiusP | 1

#### Instances

Instances details

Monoid Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius Methods mempty :: Moebius Source # mappend :: Moebius -> Moebius -> Moebius Source # mconcat :: [Moebius] -> Moebius Source #
Semigroup Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius Methods (<>) :: Moebius -> Moebius -> Moebius Source # sconcat :: NonEmpty Moebius -> Moebius Source # stimes :: Integral b => b -> Moebius -> Moebius Source #
Show Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius Methods showsPrec :: Int -> Moebius -> ShowS Source # show :: Moebius -> String Source # showList :: [Moebius] -> ShowS Source #
Eq Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius Methods (==) :: Moebius -> Moebius -> Bool Source # (/=) :: Moebius -> Moebius -> Bool Source #
Ord Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius Methods compare :: Moebius -> Moebius -> Ordering Source # (<) :: Moebius -> Moebius -> Bool Source # (<=) :: Moebius -> Moebius -> Bool Source # (>) :: Moebius -> Moebius -> Bool Source # (>=) :: Moebius -> Moebius -> Bool Source # max :: Moebius -> Moebius -> Moebius Source # min :: Moebius -> Moebius -> Moebius Source #
Unbox Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius
Vector Vector Moebius Source # |

Instance details

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

basicUnsafeFreeze :: Mutable Vector s Moebius -> ST s (Vector Moebius) Source #

basicUnsafeThaw :: Vector Moebius -> ST s (Mutable Vector s Moebius) Source #

basicLength :: Vector Moebius -> Int Source #

basicUnsafeSlice :: Int -> Int -> Vector Moebius -> Vector Moebius Source #

basicUnsafeIndexM :: Vector Moebius -> Int -> Box Moebius Source #

basicUnsafeCopy :: Mutable Vector s Moebius -> Vector Moebius -> ST s () Source #

elemseq :: Vector Moebius -> Moebius -> b -> b Source #

MVector MVector Moebius Source # |

Instance details

Defined in Math.NumberTheory.ArithmeticFunctions.Moebius

Methods

basicLength :: MVector s Moebius -> Int Source #

basicUnsafeSlice :: Int -> Int -> MVector s Moebius -> MVector s Moebius Source #

basicOverlaps :: MVector s Moebius -> MVector s Moebius -> Bool Source #

basicUnsafeNew :: Int -> ST s (MVector s Moebius) Source #

basicInitialize :: MVector s Moebius -> ST s () Source #

basicUnsafeReplicate :: Int -> Moebius -> ST s (MVector s Moebius) Source #

basicUnsafeRead :: MVector s Moebius -> Int -> ST s Moebius Source #

basicUnsafeWrite :: MVector s Moebius -> Int -> Moebius -> ST s () Source #

basicClear :: MVector s Moebius -> ST s () Source #

basicSet :: MVector s Moebius -> Moebius -> ST s () Source #

basicUnsafeCopy :: MVector s Moebius -> MVector s Moebius -> ST s () Source #

basicUnsafeMove :: MVector s Moebius -> MVector s Moebius -> ST s () Source #

basicUnsafeGrow :: MVector s Moebius -> Int -> ST s (MVector s Moebius) Source #

newtype Vector Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius newtype Vector Moebius = V_Moebius (Vector Int8)
newtype MVector s Moebius Source # |
Instance details Defined in Math.NumberTheory.ArithmeticFunctions.Moebius newtype MVector s Moebius = MV_Moebius (MVector s Int8)

runMoebius :: Num a => Moebius -> a Source #

Convert to any numeric type.

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]