计算模n下的表达式

Question

当使用大数进行模n计算时，例如mod (123456789^987654321) n，将会遇到巨大的性能惩罚。相反，您需要使用自己的^，它在内部也会对中间计算进行模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

- Tarrasch

---

你需要在运行时更改mod m中的m吗？还是将其固定在编译时就足够了？如果编译时足够，那么你可以为一些新类型的Integer定义一个模数算术Num实例... - hvr

我希望它在运行时可以更改。抱歉，我应该提到这一点。 - Tarrasch

Answer 1

Oleg做了类似的事情，他创建了一个模数算术实例，但对于任意模数。 隐式配置。

- augustss

---

我不明白。你是在链接到一篇科学论文还是一个实际的实现？如果是实现，能否提供一个代码示例？ - Tarrasch

你有没有查看链接呢？它包括论文以及一个实现。还有一个README文件描述了文件的内容。 - augustss

我浏览了网页上的摘要，没有发现有关模数的内容，显然这个理论比表面看起来更深奥。现在我找到了实现和论文。你是完全正确的，这就是我要找的东西。对于我的初始不满，我很抱歉，我太过于假设有人会链接到一个 Github 存储库，而不是一篇论文。 - Tarrasch

我真的很惊讶在Hackage上没有找到其他东西。我曾经发誓在某个时候看到过什么......无论如何，Ekmett在这里提供了配置部分的整洁和支持版本：http://hackage.haskell.org/package/reflection - sclv