learning-sicp

My embarrassing half assed SICP run.
git clone https://kaka.farm/~git/learning-sicp
Log | Files | Refs

exercise-21.scm (1296B)

      1 (define-library (sicp solutions chapter-1 exercise-21)
      2   (import (scheme base))
      3   (import (srfi srfi-1))
      4   (import (srfi srfi-64))
      5   (import (only (guile) random))
      6   (export
      7    prime?
      8    expmod
      9    fast-prime?
     10    smallest-divisor
     11    divides?
     12    )
     13 
     14   ;; XXX
     15 
     16   (begin
     17     (define (smallest-divisor n)
     18       (find-divisor n 2))
     19 
     20     (define (find-divisor n test-divisor)
     21       (cond
     22        ((> (square test-divisor) n)
     23         n)
     24 
     25        ((divides? test-divisor n)
     26         test-divisor)
     27 
     28        (else (find-divisor n (+ 1 test-divisor)))))
     29 
     30     (define (divides? a b)
     31       (= (remainder b a) 0))
     32 
     33     (define (prime? n)
     34       (= n (smallest-divisor n)))
     35 
     36     (define (expmod base exp m)
     37       (cond
     38        ((= exp 0) 1)
     39        ((even? exp)
     40         (remainder
     41          (square (expmod base
     42                          (/ exp 2)
     43                          m))
     44          m))
     45        (else
     46         (remainder
     47          (* base
     48             (expmod base
     49                     (- exp 1)
     50                     m))
     51          m))))
     52 
     53     (define (fermat-test n)
     54       (define (try-it a)
     55         (= (expmod a n n)
     56            a))
     57       (try-it (+ 1 (random (- n 1)))))
     58 
     59     (define (fast-prime? n times)
     60       (cond
     61        ((zero? times) #t)
     62        ((fermat-test n)
     63         (fast-prime? n (- times 1)))
     64        (else #f)))))