SICP 1.2 exercises cont. 13Posted: January 19, 2013
Some life stuff going on today, so I’m posting much earlier than usual.
(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.