iota-0.1.0.0
Safe HaskellSafe-Inferred
LanguageGHC2021

Math.Modulus

Synopsis

Documentation

powMod :: Integral a => a -> Int -> a -> a Source #

>>> powMod 2 0 1000000007
1
>>> powMod 0 0 1000000007
1
>>> powMod 2 1000000005 1000000007
500000004
>>> powMod 2 (-1) 1000000007
500000004
>>> powMod 123456789 998244353 998244353
123456789
>>> powMod (-2) 2 1000000007
4
>>> powMod (-2) 3 1000000007
999999999

recipMod :: Integral a => a -> a -> a Source #

>>> recipMod 2 1000000007
500000004
>>> recipMod 10 1000000007
700000005
>>> recipMod 0 1000000007
0
\x m -> not (m >= 1) || mod (x * recipMod x m) m == mod (gcd x m) m

+++ OK, passed 100 tests.

extGCD :: Integral a => a -> a -> (a, a, a) Source #

Extended Euclidean algorithm

(x, y, g) = extGCD a b (a * x + b * y = g)
>>> extGCD 3 5
(2,-1,1)
>>> extGCD 4 6
(-1,1,2)
\a b -> not (a > 0 && b > 0) || let (_, _ , g) = extGCD a b in g == gcd a b

+++ OK, passed 100 tests.

\a b -> not (a > 0 && b > 0) || let (x, y, g) = extGCD a b in a * x + b * y == g

+++ OK, passed 100 tests.

\a b -> not (a > 0 && b > 0) || let (x, y, g) = extGCD a b in abs x <= div b g && abs y <= div a g

+++ OK, passed 100 tests.

linearDiophantine :: Integral a => a -> a -> a -> Maybe (a, a) Source #

Solve a * x + b * y == c

If multiple solutions exists then return the minimum non-negative x.

If a /= 0, b /= 0, a * x + b * y == c then a (x - k * b / g) + b * (y + k * a / g) == c

>>> linearDiophantine 3 5 1
Just (2,-1)
>>> linearDiophantine 3 5 3
Just (1,0)
>>> linearDiophantine 4 6 2
Just (2,-1)
>>> linearDiophantine 4 6 3
Nothing
prop> \a b c -> maybe True (\(x, y) -> a * x + b * y == c) $ linearDiophantine a b c
+++ OK, passed 100 tests.

crt :: Integral a => (a, a) -> (a, a) -> Maybe (a, a) Source #

Chinese Remainder Theorem

x = r0 (mod m0), x = r1 (mod m1) ==> x (mod (lcm m0 m1))
>>> crt (10, 20) (10, 30)
Just (10,60)
>>> crt (10, 20) (10, 20)
Just (10,20)
>>> crt (10, 20) (11, 20)
Nothing

crt' :: Integral a => (a, a) -> (a, a) -> a Source #

  • p0, p1 are prime
  • p0 /= p1 or r0 == r1
>>> crt' (2,3) (3,5)
8
>>> crt' (3,5) (3,7)
3
>>> crt' (3,7) (3,7)
3

crts :: Integral a => [(a, a)] -> Maybe (a, a) Source #

>>> crts [(20,30),(30,50),(20,70)]
Just (230,1050)
>>> crts []
Just (0,1)
>>> crts [(1, 10), (2, 20), (3, 30)]
Nothing

garner :: Integral a => [(a, a)] -> a -> a Source #

x (mod m) (x = r[i] (mod m[i]))
gcd m[i] m[j] == 1

O(n^2)

>>> garner [(2, 3), (3, 5), (2, 7)] 999
23
>>> garner [(2, 3), (3, 5), (2, 7)] 10
3