國防部哈斯克爾作業

我的家庭作業，是提供了一個計算的功能，「X ^ÿ模N」 - 對於任意n <（開方maxint32）國防部哈斯克爾作業

所以我就開始寫這樣做：

modPow :: Int -> Int -> Int -> Int 
modPow x y n = (x `mod` n)^(y `mod` n) `mod` n

雖然我的下一個作業問題涉及到使用x^n mod n = x（Camichael數字），並且我永遠無法使modPow工作，但似乎對任何數量的n都正常工作。

modPow2 :: Int -> Int -> Int -> Int 
modPow2 x y n 
= loopmod 1 1 
    where 
    loopmod count total = if count > y 
          then total 
          else loopmod (count+1) ((total*x) `mod` n)

現在正確地產生正確的答案我的下一個問題，（X^N模N = X） - 用於檢查：

所以我使用僞代碼對mod冪，維基百科 - 從另一個製成modPow爲Camichael號碼。

雖然modPow2不爲「Y」的大數字工作（堆棧溢出！）

我怎麼能調整modPow2，使其不再獲得的情況下，Y> 10,000（但仍然是一個計算器小於sqrt 32的maxint 32-大約是46,000）

或者在我的原始modPow上有修復，所以它可以與x^n mod n = x一起使用？（我總是做560 561 561作爲輸入，這讓我回1不是560（561是卡邁克爾數，以便應該給560回）

非常感謝。

來源

2011-10-12 James Rattray

這可能是因爲參數total是懶洋洋地計算。

如果你使用GHC，你可以放置一個！在frontof的說法作出totalloopmod嚴格，即

loopmod count !total = ...

另一種方法是強制的，以評估TAL像這樣：替換最後一行與

else if total == 0 then 0 else loopmod (count+1) ((total*x) `mod` n)

這不會改變語義（因爲0*x是0，無論如何，所以提醒必須爲0也可以），它迫使擁抱每一個遞歸來評估總。

來源

2011-10-12 13:45:27 Ingo

得使用 '擁抱'，對不起。 –

@Steven，看我的編輯 – Ingo

完美的作品，非常感謝！任何它爲什麼會起作用的原因 - 它如何強制擁抱？ –

您的公式爲modPow是錯誤的，您不能只使用y mod n作爲指數，它會導致錯誤的結果。例如：

Prelude> 2^10 
1024 
Prelude> 2^10 `mod` 10 
4 
Prelude> 2^(10 `mod` 10) `mod` 10 
1

爲了更好地modPow功能，你可以使用x²ⁿ⁺¹ = x²ⁿ ⋅ x和x²ⁿ = xⁿ ⋅ xⁿ並且對於乘法你居然可以簡單地使用的因素mod。

來源

2011-10-12 13:48:16 sth

你從哪裏得到modPow的公式？

(x^y) `mod` n = ((x `mod` n)^(y `mod` φ n)) `mod` n其中φ is Euler's totient function。

來源

2011-10-12 13:57:30 dave4420

必須將它從表單中誤解釋出來。<:( –

如果您正在尋找實現（一^ d模N），那麼

powM::Integer->Integer->Integer->Integer 
powM a d n 
    | d == 0 = 1 
    | d == 1 = mod a n 
    | otherwise = mod q n where 
     p = powM (mod (a^2) n) (shiftR d 1) n 
     q = if (.&.) d 1 == 1 then mod (a * p) n else p

來源

2011-10-12 23:52:30

而不是'（。＆。）d 1 == 1'，只需使用'odd d'。 – hammar

國防部哈斯克爾作業

回答

相關問題