44210

Trouble w/ Haskell Implementation of Chinese Remainder Theorem

Question:

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.

Answer1:

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

<ol><li>You probably want minv big_m mi, not minv mi big_m.</li> <li>You have no function for summing up the list of terms. For this you can use the Haskell function sum.</li> </ol>

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 <em>not</em> 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

Recommend

  • cmake MSYS Makefiles generator missing
  • Search Facebook by first name with Koala
  • How can I decompile Linux binaries from Windows?
  • OpenCL bytecode running on another card
  • Get highest value from a file using mSL and mIRC
  • How to enforce project-wide unique ids/error codes for easily finding the origin of the error in sou
  • Extract decision boundary with scikit-learn linear SVM
  • Finding max value in CUDA
  • Retrieving a double from a JTextArea while solving for X
  • Refresh other frame, from another frame. Jquery
  • Full 8 bit adder, illogical output
  • how to make vpython .exe using pyinstaller
  • C#: Import/Export Settings into/from a File
  • Dynamically switching connect in Modelica
  • Reduction and collapse clauses in OMP have some confusing points
  • How do I superscript characters in a UIButton?
  • MongoDb aggregation
  • Ionic 2 storage is not cleaning up on uninstall - Only for signed APK
  • How to use remove-erase idiom for removing empty vectors in a vector?
  • Django rest serializer Breaks when data exists
  • How to rebase a series of branches?
  • Repeat a vertical line on every page in Report Builder / SSRS
  • Android screen density dpi vs ppi
  • Azure Cloud Service Web Role web pages do not load
  • Bug in WPF DataGrid
  • How to recover from a Spring Social ExpiredAuthorizationException
  • ILMerge & Keep Assembly Name
  • what is the difference between the asp.net mvc application and asp.net web application
  • Large data - storage and query
  • WOWZA + RTMP + HTML5 Playback?
  • R: gsub and capture
  • jqPlot EnhancedLegendRenderer plugin does not toggle series for Pie charts
  • Comma separated Values
  • WPF Applying a trigger on binding failure
  • Turn off referential integrity in Derby? is it possible?
  • Add sale price programmatically to product variations
  • Unable to use reactive element in my shiny app
  • java string with new operator and a literal
  • How to load view controller without button in storyboard?
  • How do I use LINQ to get all the Items that have a particular SubItem?