SICP 1.2 exercises cont. 13

Some life stuff going on today, so I’m posting much earlier than usual.

1.28

(define (expmod-2 base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (check (expmod-2 base (/ exp 2) m) m))
        (else
         (remainder (* base (expmod-2 base (- exp 1) m))
                    m))))

(define (nontrivial-sq-root-1-mod-n test n)
  (and (not (or (= 1 test) (= (- n 1) test)))
       (= (remainder (square test) n) 1)))

(define (check value mod)
  (if (nontrivial-sq-root-1-mod-n value mod)
      0
    (remainder (square value) mod)))

(define (congruent-a-mod-n-2 n a)
  (= (expmod-2 a n n) (remainder a n)))

(define (passes-mr n)
  (passes-mr-iter n (- n 1)))

(define (passes-mr-iter n a)
  (if (> a 1)
      (if (congruent-a-mod-n-2 n a) (passes-mr-iter n (- a 1)) #f)
    #t))

Comments: Finally completed 1.2! 1.1 took 2 days and 1.2 took 2 weeks. Hopefully that doesn’t mean that 1.3 will take 2 months.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s