Теорема китайского останова 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

Не вдаваясь в алгебре, вы можете решить эту проблему с грубой силой , Возможно, это то, что вас попросили сделать.

Для вашего примера создайте список для каждого мода, не зависящего от двух других (верхняя граница будет наименее распространенной кратной мода, предполагая, что они являются совместными как предварительное условие, произведение, т. Е. 105). Эти три списка должны иметь один общий элемент, который будет удовлетворять всем ограничениям.

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

вы можете использовать Data.Set, чтобы найти пересечение этих списков. Теперь распространите эту логику на n количество терминов, используя рекурсию или сгиб.

Update Возможно, более простой подход является определение фильтра для создания последовательности с фиксированным остатком для модуля и повторно применять для заданных пар

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