sicpsgjd/1/2/jord/example.org

• 1.2.2 Counting Change
• 1.2.6 Testing for Primality
  • searching for divisors
  • fermat's theorem

1.2.2 Counting Change

How many different ways can we make change for $10, given half-dollars, quarters, dimes, nickels, pennies?

the number of ways to change a using n types of coins is:

• the number of ways to change a using all but the first coin type, plus

• the number of ways to change (- a d) using all n coin types, d being the denomination of first coin type

  (define (count-change amount)
    (cc amount 5))
  (define (cc amount kinds-of-coins)
    (cond ((= amount 0) 1)
          ((or (< amount 0) (= kinds-of-coins 0)) 0)
          (else (+ (cc amount
                       (- kinds-of-coins 1))
                   (cc (- amount (first-denomination kinds-of-coins))
                       kinds-of-coins)))))
  (define (first-denomination kinds-of-coins)
    (cond ((= kinds-of-coins 1) 1)
          ((= kinds-of-coins 2) 5)
          ((= kinds-of-coins 3) 10)
          ((= kinds-of-coins 4) 25)
          ((= kinds-of-coins 5) 50)))
  (count-change 100)

292

1.2.6 Testing for Primality

there are many ways to test for primeness

searching for divisors

  (define (smallest-divisor n)
    (find-divisor n 2))
  (define (find-divisor n test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor n (+ test-divisor 1)))))
  (define (divides? a b)
    (= (remainder b a) 0))
  (define (prime? n)
    (= n (smallest-divisor n)))
  (prime? 13)

fermat's theorem

if n is prime and a is any positive int less than n then a to the n is congruent to a modulo n

numbers are congruent modulo n if they both have the same remainder when divided by n

  (define (expmod base exp m)
    (cond ((= exp 0) 1)
          ((even? exp)
           (remainder (square (expmod base (/ exp 2) m))
                      m))
          (else
           (remainder (* base (expmod base (- exp 1) m))
                      m))))
  (define (fermat-test n)
    (define (try-it a)
      (= (expmod a n n) a))
    (try-it (+ 1 (random (- n 1)))))
  (define (fast-prime? n times)
    (cond ((= times 0) true)
          ((fermat-test n) (fast-prime? n (- times 1)))
          (else false)))
  (fast-prime? 6601 1)

the fermat test is a probabilistic algorithm, in that it gives you an answer that is likely to be correct but not guaranteed. the odds of fooling it however, are small.