Programming Praxis - Modular Arithmetic

Yesterday’s Programming Praxis problem is about making a convenient way to do modular arithmetic. While the most elegant way to do this in Haskell is probably via a Num instance, my attempts at achieving this have failed because either the typechecker cannot infer everything anymore, or because you cannot use the same syntax for modular square roots, congruency and the rest of the operations. Maybe a better Haskell hacker than me can come up with a working solution.

In the meantime, we’re going to use a solution that’s consistent and plays nice with the type checker, even if it’s a tad less elegant.

First our imports:

import Data.Bits
import Data.List

We’ll be needing these two functions for divisions.

euclid :: Integral a => a -> a -> a
euclid x y = f 1 0 x 0 1 y where
    f a b g u v w | w == 0    = mod a y
                  | otherwise = f u v w (a-q*u) (b-q*v) (g-q*w)
                                where q = div g w

inv :: Integral a => a -> a -> a
inv x m | gcd x m == 1 = euclid x m
        | otherwise    = error "divisor must be coprime to modulus"

All the basic operations are pretty simple:

(<=>) :: Integral a => a -> a -> a -> Bool
a <=> b = \m -> mod a m == mod b m

(<+>), (<->), (<*>), (</>) :: Integral a => a -> a -> a -> a
a <+> b = \m -> mod (a + mod b m) m
a <-> b = a <+> (-b)
a <*> b = \m -> mod (a * mod b m) m
a </> b = \m -> (a <*> inv b m) m

For exponentiation we get to recycle the expm function, which was used in previous exercises.

expm :: Integer -> Integer -> Integer -> Integer
expm b e m = foldl' (\r (b', _) -> mod (r * b') m) 1 .
             filter (flip testBit 0 . snd) .
             zip (iterate (flip mod m . (^ 2)) b) $
             takeWhile (> 0) $ iterate (`shiftR` 1) e

And a little syntactic shortcut for expm:

(<^>) :: Integer -> Integer -> Integer -> Integer
(<^>) = expm

This modular square root implementation is undoubtedly a lot slower than the provided one. However, implementing that one would be boring (just translating Scheme to Haskell, with not much opportunity for size reduction) and would double or triple the size of the code. Therefore we use a more naive algorithm, that works well enough when the modulus is small. Copying the provided algorithm to Haskell is left as an exercise for the reader.

sqrtm :: Integral a => a -> a -> [a]
sqrtm x m = case [n | n <- [1..m], (n <*> n) m == mod x m] of
                (_:_:_:_) -> []
                s         -> s

The modulo function is just syntactic sugar for reverse function application.

modulo :: a -> (a -> b) -> b
modulo = flip ($)

This results in test code that looks as follows:

main :: IO ()
main = do mapM_ (modulo 12) [
              print . (17 <=> 5),
              print . (8 <+> 9),
              print . (4 <-> 9),
              print . (3 <*> 7),
              print . (9 </> 7)]
          mapM_ (modulo 13) [
              print . (6 <^> 2),
              print . (7 <^> 2),
              print . sqrtm 10]

Not terrible, but I believe a better solution exists. If anyone has one, please let me know.

About these ads

Tags: arithmetic, Haskell, kata, modular, praxis, programming