计算模数n

Question

当用大数字进行模数计算时,你会遇到巨大的性能惩罚mod (123456789^987654321) n.相反,你必须使用自己的^内部计算mod n进行中间计算.

当然,我可以很容易地实现自己的功能,但是我必须为每个操作明确说出"mod n".相反,可以构建一个数值表达式树并推迟实际计算,并且在最终状态模数n只有一次.(见下面的代码)

我开始这是为了清楚地表明我的意思,但我想知道是否已经存在这种实现,它看起来非常有用,所以有人应该实现它.

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

Answer 1

奥列格做了类似的事情，你为模算术创建了一个实例，但是对于任意模数。 隐式配置。