1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
3 12687dd9 2023-08-04 jrmu #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname |26.3|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
4 12687dd9 2023-08-04 jrmu ;gcd-structural : N[>=1] N[>=1] -> N
5 12687dd9 2023-08-04 jrmu ;Determine the greatest common divisor between n and m by testing every number between 1 and (min m n), starting at (min m n).
7 12687dd9 2023-08-04 jrmu ;check-divisible : N[>=1] -> N
8 12687dd9 2023-08-04 jrmu ;Given x, check to see if m and n are divisible by x. m and n are passed into check-divisible by a binding variable outside of check-divisible.
13 12687dd9 2023-08-04 jrmu (gcd-structural 5 10)
15 12687dd9 2023-08-04 jrmu (gcd-structural 1 10)
17 12687dd9 2023-08-04 jrmu (gcd-structural 1750 150)
22 12687dd9 2023-08-04 jrmu (define (gcd-structural m n)
23 12687dd9 2023-08-04 jrmu (local ((define (check-divisible x)
26 12687dd9 2023-08-04 jrmu [(and (= (remainder m x) 0)
27 12687dd9 2023-08-04 jrmu (= (remainder n x) 0)) x]
28 12687dd9 2023-08-04 jrmu [else (check-divisible (sub1 x))])))
29 12687dd9 2023-08-04 jrmu (check-divisible (min m n))))
31 12687dd9 2023-08-04 jrmu ;gcd-generative : N N -> N
32 12687dd9 2023-08-04 jrmu ;Uses generative recursion to determine the greatest common divisor between m and n. Reduces the main problem of finding the gcd of larger and smaller into the simpler problem of finding the gcd of smaller and the remainder of the larger divided by smaller. Only one new problem is generated each recursion, resulting in no net increase in problems. The solution to the new problem is the same as the old problem. No problems need to be combined. A trivially solvable problem is the case (gcd-generative x 0) where x is a number. In this case, the answer is simply x.
34 12687dd9 2023-08-04 jrmu ;Termination Argument: gcd-algol takes in larger and smaller and produces a new problem with the two new parameters smaller and (remainder larger smaller). Clearly, smaller is less than larger, and (remainder larger smaller) must necessarily be less than smaller. Hence, each new recursion produces numbers that tend to get smaller. At some point, (remainder larger smaller) must necessarily equal 0 for any given value since the recursion is strictly monotonic decreasing. At this point the generative recursion answers the trivially solvable problem.
37 12687dd9 2023-08-04 jrmu ;(gcd-generative 10 20)
40 12687dd9 2023-08-04 jrmu ;gcd-algol : N N -> N
41 12687dd9 2023-08-04 jrmu ;Given larger and smaller, finds the greatest common divisor.
43 12687dd9 2023-08-04 jrmu (define (gcd-generative m n)
44 12687dd9 2023-08-04 jrmu (local ((define (gcd-algol larger smaller)
46 12687dd9 2023-08-04 jrmu [(= smaller 0) larger]
47 12687dd9 2023-08-04 jrmu [else (gcd-algol smaller (remainder larger smaller))])))
48 12687dd9 2023-08-04 jrmu (gcd-algol (max m n) (min m n))))
