← Back to branch summary

~scompall/+junk/scheme-stuff

« back to all changes in this revision

Viewing changes to sicp-1.scm

  • Committer: Stephen Compall
  • Date: 2011-08-09 00:04:18 UTC
  • Revision ID: scompall@nocandysw.com-20110809000418-sf7ixffq4qbwo5lg
probabilistic prime test

Show diffs side-by-side

added added

removed removed

Lines of Context:
sicp-1.scm
78
78
           (lp (double a) (halve b) sum))
79
79
          (else
80
80
           (lp a (- b 1) (+ sum a))))))
 
81
 
 
82
;;; Ex 1.27
 
83
 
 
84
(define (expmod base exp m)
 
85
  (cond ((zero? exp) 1)
 
86
        ((even? exp)
 
87
         (modulo (square (expmod base (/ exp 2) m))
 
88
                 m))
 
89
        (else
 
90
         (modulo (* base (expmod base (- exp 1) m))
 
91
                 m))))
 
92
 
 
93
(define (fermat-test n)
 
94
  (let ((a (+ 1 (random (- n 1)))))
 
95
    (= (expmod a n n) a)))
 
96
 
 
97
(define (fast-prime? n times)
 
98
  (cond ((zero? times) #t)
 
99
        ((fermat-test n) (fast-prime? n (- times 1)))
 
100
        (else #f)))