When performing modulo n calculations with large numbers, you will encounter huge fines when performing, for example, mod (123456789^987654321) n . Instead, you should use your own ^ , which internally computes mod n, also for intermediate calculations.
Of course, I can easily implement my own functions, but then I have to explicitly say "mod n" for each operation. Instead, one could construct a numerical expression tree and postpone the actual calculations, and in the final state modulo n only once. (see my code below)
I started from this to clearly show what I mean, but I wonder if there are already implementations of this, it seems very useful, so someone should implement 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
Tarrasch
source share