我的家庭作業,是提供了一個計算的功能,「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回)
非常感謝。
得使用 '擁抱',對不起。 –
@Steven,看我的編輯 – Ingo
完美的作品,非常感謝!任何它爲什麼會起作用的原因 - 它如何強制擁抱? –