国防部哈斯克尔作业

我的家庭作业，是提供了一个计算的功能，“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

国防部哈斯克尔作业

回答

相关问题