Copyright | (c) 2011 Daniel Fischer 2018 Andrew Lelechenko |
---|---|
License | MIT |
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
Safe Haskell | None |
Language | Haskell2010 |
Chinese remainder theorem
Synopsis
- chinese :: forall a. Euclidean a => (a, a) -> (a, a) -> Maybe a
- chineseCoprime :: Euclidean a => (a, a) -> (a, a) -> Maybe a
- chineseSomeMod :: SomeMod -> SomeMod -> Maybe SomeMod
- chineseCoprimeSomeMod :: SomeMod -> SomeMod -> Maybe SomeMod
- chineseRemainder :: [(Integer, Integer)] -> Maybe Integer
- chineseRemainder2 :: (Integer, Integer) -> (Integer, Integer) -> Integer
Safe interface
chinese :: forall a. Euclidean a => (a, a) -> (a, a) -> Maybe a Source #
chinese
(n1, m1)
(n2, m2)
returns n
such that
n `mod` m1 == n1
and n `mod` m2 == n2
, if exists.
Moduli m1
and m2
are allowed to have common factors.
>>>
chinese (1, 2) (2, 3)
Just 5>>>
chinese (3, 4) (5, 6)
Just 11>>>
chinese (3, 4) (2, 6)
Nothing
chineseCoprime :: Euclidean a => (a, a) -> (a, a) -> Maybe a Source #
chineseCoprime
(n1, m1)
(n2, m2)
returns n
such that
n `mod` m1 == n1
and n `mod` m2 == n2
.
Moduli m1
and m2
must be coprime, otherwise Nothing
is returned.
This function is slightly faster than chinese
, but more restricted.
>>>
chineseCoprime (1, 2) (2, 3)
Just 5>>>
chineseCoprime (3, 4) (5, 6)
Nothing -- moduli must be coprime
chineseSomeMod :: SomeMod -> SomeMod -> Maybe SomeMod Source #
Same as chinese
, but operates on residues.
>>>
:set -XDataKinds
>>>
import Math.NumberTheory.Moduli.Class
>>>
(1 `modulo` 2) `chineseSomeMod` (2 `modulo` 3)
Just (5 `modulo` 6)>>>
(3 `modulo` 4) `chineseSomeMod` (5 `modulo` 6)
Just (11 `modulo` 12)>>>
(3 `modulo` 4) `chineseSomeMod` (2 `modulo` 6)
Nothing
chineseCoprimeSomeMod :: SomeMod -> SomeMod -> Maybe SomeMod Source #
Same as chineseCoprime
, but operates on residues.
>>>
:set -XDataKinds
>>>
import Math.NumberTheory.Moduli.Class
>>>
(1 `modulo` 2) `chineseCoprimeSomeMod` (2 `modulo` 3)
Just (5 `modulo` 6)>>>
(3 `modulo` 4) `chineseCoprimeSomeMod` (5 `modulo` 6)
Nothing
Unsafe interface
chineseRemainder :: [(Integer, Integer)] -> Maybe Integer Source #
Given a list [(r_1,m_1), ..., (r_n,m_n)]
of (residue,modulus)
pairs, chineseRemainder
calculates the solution to the simultaneous
congruences
r ≡ r_k (mod m_k)
if all moduli are positive and pairwise coprime. Otherwise
the result is Nothing
regardless of whether
a solution exists.