1.28

secje posted @ 2010年5月17日 05:59 in sicp , 1637 阅读

 

(define (square x) (* x x))
(define (check-one count a m)
  (define (check-1? t)
    (cond ((and (not (= a (- m 1))) (= count 1)) t)
          ((< count 1) t)
          (else 0)))
  (check-1? (remainder (square a) m)))
(define (check-two count a m)
  (define (check-2? t)
    (cond ((and (not (= a 1)) (not (= a (- m 1))) (= count 0)) t)
          ((not (= count 0)) t)
          (else 0)))
  (check-2? (remainder (square a) m)))
(define (expmod base exp m count)
  (cond ((= exp 0) 1)
        ((and (even? exp) (even? (/ exp 2)))
         (check-one count (expmod base (/ exp 2) m count) m))
        ((and (even? exp) (not (even? (/ exp 2))))
         (check-two (- count 1) (expmod base (/ exp 2) m (- count 1)) m))
        (else
         (remainder (* base (expmod base (- exp 1) m count))
                    m))))
(define (prime-test m)
  (define (try-it a)
    (= (expmod a (- m 1) m 1) 0))
  (try-it (+ 1 (random (- m 1)))))
(define (miller-test m times)
  (cond ((= m 1) #f)
        ((= m 2) #t)
        ((even? m) #f)
        ((= times 0) #t)
        ((prime-test m) (miller-test m (- times 1)))
        (else #f)))

这个是了解miller-test之后写的

http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

然后这个是按照书上的要求写的

 

(define (square x) (* x x))
(define (check a n)
  (define (check-1? t)
    (if (and (> a 1)
             (< a (- n 1))
             (= t 1))
        0 t))
  (check-1? (remainder (square a) n)))
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (check (expmod base (/ exp 2) m) m))
        (else
         (remainder (* base (expmod base (- exp 1) m)) m))))
(define (prime-test m)
  (define (try-it a)
    (= (expmod a (- m 1) m) 1))
  (try-it (+ 1 (random (- m 1)))))
(define (miller-test m times)
  (cond ((= m 1) #f)
        ((= times 0) #t)
        ((prime-test m) (miller-test m (- times 1)))
        (else #f)))

 

 

 

 

carpet cleaning duba 说:
2019年10月24日 03:19

Practical experience in profound cleaning tile floors has become the most important explanation why business lovers and people trust qualified cleaners and you ought to too. It is far from enough to gain the cleaning up tools plus products with the store, but you must have in-depth is vital what products to implement for your unique type with tile. By way of example, what will work for ceramic tiles won't work to the granite tiles. Should you use the improper cleaner, it may well stain and perhaps permanently ruin your tiles. Its possible you have to altogether replace a person's tile floor covering, which costs you some huge cash.

cleaning services du 说:
2021年8月25日 19:28

Just about the most important items while carrying out the washing services is always to prioritize the cleaning career and manage it with all the cleaners. Depends upon the task you should arrange the particular cleaning career when it must be done where day or perhaps week. So your cleaning is manufactured easy simply by arranging purchasing which are usually convenient for your customers at the same time. Through the appropriate cleaning method and coordinating ensures to completely clean all the particular surfaces and maintain the things risk-free.

part time maids in d 说:
2021年9月30日 07:08

Organization cleaning nowadays might be of several unique types. A company might be contracted into the future in every month or so to do significant clean-up work opportunities like floorboards waxing, dusting, shades and various other major work opportunities. Often firms that use in professionals every month are having somebody maintain the exact property during the opposite parts in the month.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter