aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/Utils.hs27
1 files changed, 27 insertions, 0 deletions
diff --git a/lib/Utils.hs b/lib/Utils.hs
index 56d9c69..e0f9d62 100644
--- a/lib/Utils.hs
+++ b/lib/Utils.hs
@@ -65,3 +65,30 @@ makeGrid s = (grid, width, height) where
65 grid = Map.fromList [((x, y), a) | (y, row) <- zip [0..] rows , (x, a) <- zip [0..] row] 65 grid = Map.fromList [((x, y), a) | (y, row) <- zip [0..] rows , (x, a) <- zip [0..] row]
66 width = length (head rows) 66 width = length (head rows)
67 height = length rows 67 height = length rows
68
69-- number theory
70
71egcd :: Int -> Int -> (Int, Int)
72egcd _ 0 = (1, 0)
73egcd a b = (t, s - q * t)
74 where
75 (s, t) = egcd b r
76 (q, r) = a `quotRem` b
77
78modInv :: Int -> Int -> Maybe Int
79modInv a b =
80 case egcd a b of
81 (x, y)
82 | a * x + b * y == 1 -> Just x
83 | otherwise -> Nothing
84
85-- from rosetta code
86chineseRemainder :: [(Int, Int)] -> Maybe Int
87chineseRemainder ls =
88 zipWithM modInv crtModulii modulii >>=
89 (Just . (`mod` modPI) . sum . zipWith (*) crtModulii . zipWith (*) residues)
90 where
91 residues = map fst ls
92 modulii = map snd ls
93 modPI = product modulii
94 crtModulii = (modPI `div`) <$> modulii