sicp_1.28 解法简单 问题晦涩

sicp_1.28_expmode.scm

(define (miller-rabin-test n)
    (define (try-it a)
        ; 因为 1 小于n, 所以 a/n 的余数就是 1.
        (= (expmode a (- n 1) n) 1)
    )
    (try-it (+ 1 (random (- n 1))))
)

(define (expmod base exp m) 
   (define (squaremod-with-check x) 
     (define (check-nontrivial-sqrt1 x square) 
       (if (and (= square 1) 
                (not (= x 1)) 
                (not (= x (- m 1)))) 
           0 
           square)) 
     (check-nontrivial-sqrt1 x (remainder (square x) m))) 
   (cond ((= exp 0) 1) 
         ((even? exp) (squaremod-with-check 
                       (miller-rabin-expmod base (/ exp 2) m))) 
         (else 
          (remainder (* base (miller-rabin-expmod base (- exp 1) m)) 
                     m)))) 
  

; 辅助方法.
(define (square a)
    (* a a))

(define (fast-prime? n times)
    (cond ((= times 0) #t)
          ((miller-rabin-test n) (fast-prime? n (- times 1)))
          (else #f)
    )
)

 (define (prime? n)  
    ; Perform the test how many times?  
    ; Use 100 as an arbitrary value.  
    (fast-prime? n 100))  

问题本身有点晦涩. 最终还是参考了 http://community.schemewiki.org/?sicp-ex-1.28

与我自己的初版(错误)解法, 核心区别是: 是检查 取余后的结果, 还是检查取余的参数.

(define (expmode base exp m)
    (cond ((and (not (= base 1)) (not (= base (- m 1))) (= (remainder (square base) m) 1)) 0)
          ((= exp 0) 1)
          ((even? exp)
            (remainder (square (expmode base (/ exp 2) m)) m))
          (else 
            (remainder (* base (expmode base (- exp 1) m)) m))
    )
)