arithmoi-0.12.1.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.Prefactored

Description

Type for numbers, accompanied by their factorisation.

Synopsis

- data Prefactored a
- fromValue :: (Eq a, GcdDomain a) => a -> Prefactored a
- fromFactors :: Semiring a => Coprimes a Word -> Prefactored a

# Documentation

data Prefactored a Source #

A container for a number and its pairwise coprime (but not necessarily prime) factorisation. It is designed to preserve information about factors under multiplication. One can use this representation to speed up prime factorisation and computation of arithmetic functions.

For instance, let `p` and `q` be big primes:

    >>> let p = 1000000000000000000000000000057 :: Integer
    >>> let q = 2000000000000000000000000000071 :: Integer

It would be difficult to compute the totient function of their product as is, because once we multiplied them the information of factors is lost and `totient` (`p` * `q`) would take ages. Things become different if we simply change types of `p` and `q` to prefactored ones:

    >>> let p = 1000000000000000000000000000057 :: Prefactored Integer
    >>> let q = 2000000000000000000000000000071 :: Prefactored Integer

Now the `totient` function can be computed instantly:

    >>> import Math.NumberTheory.ArithmeticFunctions
    >>> prefValue $ totient (p^2 * q^3)
    8000000000000000000000000001752000000000000000000000000151322000000000000000000000006445392000000000000000000000135513014000000000000000000001126361040
    >>> prefValue $ totient $ totient (p^2 * q^3)
    2133305798262843681544648472180210822742702690942899511234131900112583590230336435053688694839034890779375223070157301188739881477320529552945446912000

Let us look under the hood:

    >>> import Math.NumberTheory.ArithmeticFunctions
    >>> prefFactors $ totient (p^2 * q^3)
    Coprimes {unCoprimes = [(1000000000000000000000000000057,1),(41666666666666666666666666669,1),(2000000000000000000000000000071,2),(111111111111111111111111111115,1),(2,4),(3,3)]}
    >>> prefFactors $ totient $ totient (p^2 * q^3)
    Coprimes {unCoprimes = [(39521,1),(227098769,1),(22222222222222222222222222223,1),(2000000000000000000000000000071,1),(361696272343,1),(85331809838489,1),(6046667,1),(199937,1),(5,3),(41666666666666666666666666669,1),(2,22),(3,8)]}

Pairwise coprimality of factors is crucial, because it allows us to process them independently, possibly even in parallel or concurrent fashion.

Following invariant is guaranteed to hold:

    abs (prefValue x) = abs (product (map (uncurry (^)) (prefFactors x)))

#### Instances

Instances details

(Eq a, GcdDomain a, UniqueFactorisation a) => UniqueFactorisation (Prefactored a) Source # |
Instance details Defined in Math.NumberTheory.Prefactored Methods factorise :: Prefactored a -> [(Prime (Prefactored a), Word)] Source # isPrime :: Prefactored a -> Maybe (Prime (Prefactored a)) Source #
(Eq a, Num a, GcdDomain a) => Num (Prefactored a) Source # |

Instance details

Defined in Math.NumberTheory.Prefactored

Methods

(+) :: Prefactored a -> Prefactored a -> Prefactored a Source #

(-) :: Prefactored a -> Prefactored a -> Prefactored a Source #

(*) :: Prefactored a -> Prefactored a -> Prefactored a Source #

negate :: Prefactored a -> Prefactored a Source #

abs :: Prefactored a -> Prefactored a Source #

signum :: Prefactored a -> Prefactored a Source #

fromInteger :: Integer -> Prefactored a Source #

Show a => Show (Prefactored a) Source # |
Instance details Defined in Math.NumberTheory.Prefactored Methods showsPrec :: Int -> Prefactored a -> ShowS Source # show :: Prefactored a -> String Source # showList :: [Prefactored a] -> ShowS Source #
Eq a => Eq (Prefactored a) Source # |
Instance details Defined in Math.NumberTheory.Prefactored Methods (==) :: Prefactored a -> Prefactored a -> Bool Source # (/=) :: Prefactored a -> Prefactored a -> Bool Source #
(Eq a, GcdDomain a) => Semiring (Prefactored a) Source # |
Instance details Defined in Math.NumberTheory.Prefactored Methods plus :: Prefactored a -> Prefactored a -> Prefactored a Source # zero :: Prefactored a Source # times :: Prefactored a -> Prefactored a -> Prefactored a Source # one :: Prefactored a Source # fromNatural :: Natural -> Prefactored a Source #

fromValue :: (Eq a, GcdDomain a) => a -> Prefactored a Source #

Create `Prefactored` from a given number.

    >>> fromValue 123
    Prefactored {prefValue = 123, prefFactors = Coprimes {unCoprimes = [(123,1)]}}

fromFactors :: Semiring a => Coprimes a Word -> Prefactored a Source #

Create `Prefactored` from a given list of pairwise coprime (but not necessarily prime) factors with multiplicities.

    >>> fromFactors (splitIntoCoprimes [(140, 1), (165, 1)])
    Prefactored {prefValue = 23100, prefFactors = Coprimes {unCoprimes = [(28,1),(33,1),(5,2)]}}
    >>> fromFactors (splitIntoCoprimes [(140, 2), (165, 3)])
    Prefactored {prefValue = 88045650000, prefFactors = Coprimes {unCoprimes = [(28,2),(33,3),(5,5)]}}