-3

这是以下代码，我尝试在其中找到一些素数除数。我曾尝试将 TAOCP 算法转换为 Haskell 程序，但我可以理解什么时候会懒惰或急切地评估：

modof2 n = let a0 = shiftR n 1
           a1 = shiftL a0 1
       in n-a1
iseven n = modof2 n == 0

factoringby2 n = let s=(lastf (takeWhile f [1..])) + 1
                 d=n `quot` powerof2 s
             in (s,d)
  where f s = let d = n `quot` (powerof2 s)
            in if isodd d 
               then False
               else True
      lastf [] = 0
      lastf xs = last xs

miller_rabin_prime_test n 0 result=return result
miller_rabin_prime_test n k result| (isodd n) && n>3 = do
                                            a<-randomRIO(2,n-2)
                                            let z = basic_step n a (fst sd) (snd sd)
                                            miller_rabin_prime_test n (k-1) z
  where sd=factoringby2 n
basic_step:: Integer->Integer->Int->Integer->Bool
basic_step n a s d =any (\x-> x==1 || x==n-1) (map x (map u [0..s-1]))
  where u j=powerof2(j)*d 
        x j=modular_pow a j n 1

isprime n = if n==2 || n==3
        then return True
        else if n<2
             then return False
             else if iseven n
                  then return False
                  else miller_rabin_prime_test n 5 True
x_m :: Double->Integer->Integer
x_m 0 n = 2
x_m m n = f (x_m (m-1) n) `mod` n
where f x = x^2 +1
l::Double->Double
l m = 2 ^ (floor (log2 m))
where log2 m = log m / log 2
g m n = let a = x_m m n
        b = x_m ((l m)-1) n
     in gcd (a-b) n

gg n = [g m n|m<-[1..]]


algorithmB n = do
            testprime<-isprime n
            let a = head (filter (1>) (gg n))
            c<-algorithmB (n `div` a)
            if testprime
            then return []
            else return (a:c)

算法 B 不会终止。为什么会发生这种情况？我认为这就是原因，因为它不会懒惰地评估。真的吗？谢谢c<-algorithmB (n div a)

4

1 回答 1

1

algorithmB在无限循环中调用自己。当然回不去了！

于 2013-02-07T20:29:17.430 回答