CODEWITHSUNDEEP
haskellmodulo
Tarrasch
Tarrasch

Reputation: 10547

Calculating expressions modulo n

When doing calculations modulo n with large numbers, you will encounter huge performency penalties when doing for example mod (123456789^987654321) n. Instead you have to use your own ^ that internally calculates mod n also for intermedite calculations.

Sure, I can easily implement my own functions, but then I have to explicitly say "mod n" for each operation. Instead one could build an numeric expression tree and defer actual calculations, and in the end state modulo n only once. (see my code below)

I started on this to clearly show what I mean, but I wonder if there already exists implementations of this, it seems quite useful so somebody ought to have implemented it.

module Modulo where

data Expr =
    V Integer 
  | Plus Expr Expr
  | Mult Expr Expr
  deriving (Eq, Show)

instance Num Expr where
  (+) = Plus
  (*) = Mult
  fromInteger = V

eval :: Integer -> Expr -> Integer
eval m (V i) = i `mod` m
eval m (Plus e1 e2) = (eval m e1 + eval m e2) `mod` m
eval m (Mult e1 e2) = (eval m e1 * eval m e2) `mod` m

fifteen :: Expr
fifteen = 10 + 5

test = eval 13 fifteen

Upvotes: 7

Views: 2030

Answers (1)

augustss
augustss

Reputation: 23014

Oleg did something of this kind, where you make an instance for modulo arithmetic, but for a arbitrary modulus. Implicit configurations.

Upvotes: 3

Related Questions