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
Oleg did something of this kind, where you make an instance for modulo arithmetic, but for a arbitrary modulus. Implicit configurations.
链接地址: http://www.djcxy.com/p/9996.html下一篇: 计算表达式模n