中国剩余定理Haskell

Question

我需要用Haskell写一个或几个函数来解决中国剩余定理。需要用以下定义创建它：

crt :: [(Integer, Integer)] -> (Integer, Integer)

答案看起来就像

>crt [(2,7), (0,3), (1,5)]
(51, 105)

我想我有一个整体的想法，我只是没有写它的知识。我知道crt函数必须是递归的。我创建了一个帮助函数，将元组列表拆分为两个列表的元组：

crtSplit xs = (map fst xs, product(map snd xs))

在这个例子中，它给了我：

([2,0,1],105)

我想我需要知道的是为第一个列表中的每个元素创建一个列表。我怎么开始这么做？

Answer 1

中国剩余定理有一个algebraic solution，基于x = r1 % m1和x = r2 % m2可以简化为一个模方程，如果m1和m2是coprime的话。

要做到这一点，您需要知道什么是modular inverse，以及如何使用extended Euclidean algorithm有效地计算它。

如果把这些部分放在一起，就可以用right fold来解决中国剩余定理。

crt :: (Integral a, Foldable t) => t (a, a) -> (a, a)
crt = foldr go (0, 1)
    where
    go (r1, m1) (r2, m2) = (r `mod` m, m)
        where
        r = r2 + m2 * (r1 - r2) * (m2 `inv` m1)
        m = m2 * m1

    -- Modular Inverse
    a `inv` m = let (_, i, _) = gcd a m in i `mod` m

    -- Extended Euclidean Algorithm
    gcd 0 b = (b, 0, 1)
    gcd a b = (g, t - (b `div` a) * s, s)
        where (g, s, t) = gcd (b `mod` a) a

然后：

\> crt [(2,7), (0,3), (1,5)]
(51,105)
\> crt [(2,3), (3,4), (1,5)]  -- wiki example
(11,60)

Answer 2

不用进入代数，你也可以用蛮力来解决这个问题。也许这就是你被要求做的事。

对于您的示例，为每个mod创建一个独立于其他两个模块的列表(上界将是mod的最小公共倍数，假设它们是作为前提条件的同素数，即105)。这三个列表应该有一个共同的元素，可以满足所有的约束条件。

m3 = [3,6,9,12,15,...,105]
m5 = [6,11,16,21,...,101]
m7 = [9,16,23,30,...,100]

您可以使用Data.Set找到这些列表的交集。现在，使用递归或折叠将此逻辑扩展到n个术语。

更新也许更简单的方法是定义一个过滤器，为模数创建一个具有固定余数的序列，并对给定的对反复应用

Prelude> let rm (r,m) = filter (\x -> x `mod` m == r)       

验证它是否有效，

Prelude> take 10 $ rm (1,5) [1..]                                               
[1,6,11,16,21,26,31,36,41,46]

现在，对于给定的示例，请重复使用它，

Prelude> take 3 $ rm (1,5) $ rm (0,3) $ rm (2,7) [1..]        
[51,156,261]

当然，我们只需要第一个元素，改为头。

Prelude> head $ rm (1,5) $ rm (0,3) $ rm (2,7) [1..]       
51

我们可以用折叠来概括

Prelude> head $ foldr rm [1..] [(1,5),(0,3),(2,7)]                            
51