(define (expmod base exp m) (cond ((= exp 0) 1) ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m)) (else (remainder (* base (expmod base (- exp 1) m)) m)))) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a)) (try-it (+ 1 (random (- n 1))))) (define (fast-prime? n times) (cond ((= times 0) true) ((fermat-test n) (fast-prime? n (- times 1))) (else false)))

expmod base exp m | exp == 0 = 1 | even exp = mod (square (expmod base (exp`div`2) m)) m | otherwise = mod (base * (expmod base (exp-1) m)) m fermattest n = do pick <- rndm $ n-1 let a = 1 + pick return $ expmod a n n == a rndm x = do gen <- newStdGen return $ fst $ randomR (1, x-1) gen fastprime n times = do lst <- replicateM times $ fermattest n return $ and lst


sicp 1.2.6에 나오는 건데..

이거 스킴 구문 그대로 옮겨 적으려고 보니, 하스켈로는 일반 함수에 랜덤을 끼워 넣을 수가 없음. 함수의 순수성을 해치기 때문에..

그래서 do로 싸매야 하고, 바인딩은 그 안에서만 유효하고, 함수 결과값도 랩핑된 것만 가능함.

스킴 구문 그냥 무시하고 구현 결과만 같게 짰더니 잘 돌아간다.

하고 나니 별 것 아닌데, 할 때는 왜 이렇게 시간이 많이 걸리던지..