Copyright | (c) 2011 Daniel Fischer 2018 Andrew Lelechenko |
---|---|
License | MIT |
Maintainer | Andrew Lelechenko <andrew.lelechenko@gmail.com> |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
Chinese remainder theorem
Safe interface
chinese :: forall a. (Eq a, Ring a, Euclidean a) => (a, a) -> (a, a) -> Maybe (a, a) Source #
chinese
(n1, m1)
(n2, m2)
returns (n, lcm m1 m2)
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 (-1, 6)>>>
chinese (3, 4) (5, 6)
Just (-1, 12)>>>
chinese (3, 4) (2, 6)
Nothing
chineseSomeMod :: SomeMod -> SomeMod -> Maybe SomeMod Source #
Same as chinese
, but operates on residues.
>>>
:set -XDataKinds
>>>
import Data.Mod
>>>
(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