CODEWITHSUNDEEP
haskellcrt
eLemonnader
eLemonnader

Reputation: 85

Trouble w/ Haskell Implementation of Chinese Remainder Theorem

So I am having a problem trying to implement the Chinese Remainder Theorem into Haskell. So far I have this:

minv :: Integer -> Integer -> Integer
minv a m = let (1, x, _) = extGCD a m
           in x `mod` m


crt :: [Integer] -> [Integer] -> Integer
crt as ms = let
                    prod = product ms
                    big_m = [div prod i| i <- ms]
            in (zip as ms (\(ai,mi)) ((ai * big_m * (minv mi big_m)) `mod` prod))

Okay so I know the minv function works (I've tested it multiple times), but I can't get the crt function to work. So here is what I am trying to do:

I need to zip list as and ms together and then apply each one of the binaries to the equation that actually finds the Chinese Remainder Theorem. But I need to handle the binaries first and THEN apply `mod` prod to the ENTIRE number I get from working all the binaries.

Hopefully this make some form of sense.

Thanks in advance.

Upvotes: 1

Views: 650

Answers (1)

&#216;rjan Johansen
&#216;rjan Johansen

Reputation: 18199

Apart from your problems expressing this as Haskell, I see two plain mathematical problems here related to the Chinese Remainder Theorem formula itself:

  1. You probably want minv big_m mi, not minv mi big_m.
  2. You have no function for summing up the list of terms. For this you can use the Haskell function sum.

So, you first want to get the expression ai * big_m * (minv big_m mi) applied to each pair of elements in the lists as and ms. It is useful for clarity to define this as a named function by itself, let's call it term:

    term ai mi = ai * big_m * (minv big_m mi)

(Note I am not putting ai and mi in a tuple, as the function we will use to zip later does not use them.)

However, the way you have defined big_m it is not a number, but the list

    big_m = [div prod i| i <- ms]

What you actually need big_m to be is the particular element of that list that matches with ai and mi, and which is equal to div prod mi. Since this is a function of mi, it is simplest to define it inside the definition of term:

    term ai mi = let big_m = div prod mi
                 in ai * big_m * (minv big_m mi)

(I actually prefer where to let myself, but I've decided to use let since you did in the question.)

Now you need to apply the function term to all the corresponding elements from as and ms. You could fix your original method by combining zip with the map function, something like

map (\(ai,mi) -> term ai mi) (zip as ms)

Note the lambda function syntax, which @bheklilr pointed out you had wrong. Although the tuple confuses matters here, an ordinary lambda function needs no parentheses inside, and must have both \ and ->.

However, Haskell has a handy function zipWith that does both in one go (and doesn't need the function to take tuples):

zipWith term as ms

Then you need to use sum to sum the terms in the list thus constructed.

sum (zipWith term as ms)

Finally you can now apply the final `mod` prod to this:

sum (zipWith term as ms) `mod` prod

Combining all of this, the final crt function can become

crt :: [Integer] -> [Integer] -> Integer
crt as ms = let
                prod = product ms
                term ai mi = let big_m = div prod mi
                             in ai * big_m * (minv big_m mi)
            in sum (zipWith term as ms) `mod` prod

Upvotes: 6

Related Questions