以n爲模的表達式計算

以大數字進行模n的計算時，例如在執行mod (123456789^987654321) n時會遇到巨大的執行懲罰。相反，您必須使用自己的^，它也可以在內部計算mod 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

來源

2011-11-17 Tarrasch

您是否需要'mod m'中的'm'在運行時可以更改，還是足夠讓它在編譯時修復？如果編譯時足夠的話，你可以簡單地爲一些新類型的Integer定義一個modulo-arithemtic的'Num'-instance ... – hvr

我希望它在運行時可以改變。對不起，我應該提到它。 – Tarrasch

奧列格做這種，在何處進行實例模運算的東西，但對於一個任意的模量。 Implicit configurations.

來源

2011-11-17 15:11:25 augustss

我不明白。你是鏈接到科學論文還是實際實施？如果它是一個實現，你能提供一個代碼示例嗎？ – Tarrasch

您是否打擾檢查鏈接？它有論文，也是一個實現。還有一個README文件，它描述了這些文件包含的內容。 – augustss

我瀏覽了網頁上的摘要，並沒有發現任何關於模數的內容，顯然這個理論比第一次見到的更深。現在我找到了實施和論文。你絕對正確，這正是我正在尋找的。對不起，我最初的皺眉，我非常認爲有人會鏈接到github回購，而不是紙。 – Tarrasch

以n爲模的表達式計算

回答

相關問題