sicp chapter 1 half

; Exercise 1.4
define (sum-of-larger-two a b c)
  (cond   (((< a b) and (< a c)) (sum-of-squares b c))
          (((< b a) and (< b c)) (sum-of-squares a c))
          (((< c a) and (< c b)) (sum-of-squares a b)))

(define (sqrt-iter guess x)
  (if (good-enough? guess x) ;give predicates names ending in ?, a normal character
    guess
    (sqrt-iter (improve guess x)
                x)))


(define (improve guess x)
  (average guess (/ x guess)))

where

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

(sqrt 9)
;3.000091554...

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x)
                x)))

; will blow up as enter infinite loop
; new-if not a special form, will eval all operands, incl (sqrt-iter (improve guess x) x)

(define (sqrt-iter guess oldguess x)
  (if (good-enough? guess oldguess)
    guess
    (sqrt-iter (improve guess x) guess x)))

(define (good-enough? guess oldguess)
  (< (abs (- guess oldguess)) (*guess 0.001)))

(define (sqrt x)
  (sqrt-iter 1.0 2.0 x))

; sqrt-iter is recursive, and is defined in terms of itself
; 1. how to tell if guess is good-enough?
; 2. how to improve guess
; 3. how to create recursive procedure
; problem decomposed into subproblems
; sub-problem viewed as black box; a procedural abstraction; concerning what, not how
; user should not need to know how the procedure is implemented...

; exercise 1.8

(define (square x) (* x x))

(define (cube-root-iter guess oldguess x)
  (if (good-enough? guess oldguess)
    guess
    (cube-root-iter (improve guess x) guess x)))

(define (improve guess x)
  (/ (+ (/ x (square guess)) (* 2 guess)) 3))

(define (good-enough? guess oldguess)
  (< (abs (- guess oldguess)) (abs (* guess 0.001))))

(define (cube-root x)
  (cube-root-iter 1.0 0.0 x))

(define (cube-root x)
  ((if (< x 0) - +)(cube-root-iter (improve 1.0 (abs x)) 1 (abs x))))


(define (square x) (* x x))

; above and below separate definitions of square x

(define (square x)
  (exp (double (log x))))

(define (double x) (+ x x))


; block structure, nesting of definitions as solution to name-packaging problem

(define (sqrt x)
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess x)
    (average guess (/ x guess)))
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))
  (sqrt-iter 1.0 x))


; allow x to be a free variable in the internal definitions
; lexical scoping

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
      guess
      (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))


n! = n (n-1)!

(define (factorial n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))

; above has shape of expansion followed by contraction
; expansion when building up a chain of deferred operations
; contraction when operations are actually performed
; ^ recursive process
; requires interpreter keep track of operations to be performed later on
; info grows linearly with n
; ^ linear recursive process


; product = product * counter
; counter = counter + 1

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
      product
      (iter (* product counter) (+ counter 1))))
  (iter 1 1))

; keep track of variables only: product, counter
; fixed number of state variables
; state is captured completely by its state variables
; ^linear iterative process

(define (+ a b)
  (if (= a 0)
    b
    (inc (+ (dec a) b))))

(+ 4 5)
(inc (+ (dec 4) 5))
(inc (+ 3 5))
(inc (inc (+ dec (3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

; recursive process
; build up chain of deferred operations


(define (+ a b)
  (if (= a 0)
    b
    (+ (dec a) (inc b))))


(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9

; iterative process
; state variables a,b
; (+ 4 5) = (+ 3 6) = (+ 2 7) = (+ 1 8) = (+ 0 9)


(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
              (A x (- y 1)))))


(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8))
(A 0 (A 0 (A 0 (A 1 7)))
(A 0 (A 0 (A 0 (A 0 (A 1 6))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5)))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))
(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))
.
.
.
(A 0 512)
1024

(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2))))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 (A 0 (A 1 2))))
(A 1 (A 0 (A 0 (A 0 (A 1 1)))))
(A 1 (A 0 (A 0 (A 0 2))))
(A 1 (A 0 (A 0 4))
(A 1 (A 0 8))
(A 1 16)
.
.
.
65536

(A 2 4)
(A 1 (A 1 4))
(A 1 16)
2^16
2^(2^4)
2^(2^2^2)

(A 2 3)
(A 1 (A 2 2))
(A 1 (A 1 (A 2 1))))
(A 1 (A 1 2)
(A 1 (A 0 (A 1 1)))
(A 1 (A 0 2))
(A 1 4)
16

(A 2 3)
2^(2^2)


(A 3 3)
(A 2 (A 3 2))
(A 2)

(f n) = 2n
(g n) = 2^n
(h n) = 2^2^2 (n times)
(k n) = 5n^2


(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1))
        (else (+  (fib(n-1)
                  (fib(n-2))))))

(fib 5)
(+ (fib 4) (fib 3))
(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))
(+ (+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0))) (+ (+ (fib 1) (fib 0)) (fib 1)))
(+ (+ (+ (+ (fib 1) (fib 0)) (fib 1)) (+ (fib 1) (fib 0))) (+ (+ (fib 1) (fib 0)) (fib 1)))
(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (+ 1 0) 1))
(+ 3 2)
5

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
    b
    (fib-iter (+ a b) a (- count 1))))

; linear iteration; number of steps linear in n
; 3 state vars: a, b, count


1.00 , 0.50, 0.25, 0.10, 0.05, 0.01

make change of 1.00
more generally, write procedure to compute ways to change any given amt of money

change amount a using n kinds of coins:
  use 0 of coin d
  use >= 1 of coin d

(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)))

; first-denomination takes as input the number of coins available and returns the largest coin

(count-change 100)
292


(define (f n)
  (cond ((< n 3) n)
        (else (+ (f (- n 1))
                (* 2 (f (- n 2)))
                (* 3 (f (- n 3)))))))

(define (pascal r c)
  (if (or (= c 1) (= c r))
    1
    (+ (pascal (- r 1) (- c 1)) (pascal (- r 1) c))))


n measures size of problem
R(n) is amount of resources the process requires for problem of size n

; order of growth indicate how we may expect the behavior of the process to change as we
; change the size of the problem

sin x = 3*sin(x/3) - 4*(sin(x/3)^3)

(define (sine angle)
  (if   (not (> (abs angle) 0.1))
        angle
        (p (sine (/ angle 3.0)))))

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))


; how many times p interpreted

(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p (0.05))))))


(ceiling (/ (log (/ a 0.1)) (log 3)))


(define (expt b n)
  (if (= n 0)
    1
    (* b (expt b (- n 1)))))

; linear recursive process above - xn steps and yn space

; iterative process below - xn steps and y space

(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
    product
    (expt-iter b (- counter 1) (* b product))))

; successive squaring below

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

(define (even? n)
  (= remainder n 2) 0)

; logarithmic growth; computing b^2n is one more multiplication than b^n
; k log(n) growth

; below will be the successive squaring iterative algorithm

(define (fast-expt b n)
  (define (iter a b n)
    (cond  ((= n 0) a)
            ((even? n) (iter a (square b) (/ n 2)))
            (else (iter (* a b) b (- n 1)))))
  (iter 1 b n))

(define (square x) (* x x))


(define (* a b)
  (if (= b 0)
    0
    (+ a (* a (- b 1)))))

; linear recursive
; successive below

(define (* a b)
  (cond ((= b 0) 0)
        ((even? y) (* (double a) (halve b)))
        (else (+ a (* a (- b 1))))))

(define (double a) (+ a a))
(define (halve a) (/ a 2))

; iterative below

(define (fast-mult x y)
  (define (iter a x y)
    (cond ((= y 0) a)
          ((even? y) (iter a (* x 2) (/ y 2)))
          (else (iter (+ a x) x (- y 1)))))
  (iter 0 x y))

; revision of Fibonacci numbers

; start with tree recursion; f(5) branches into f(4) and f(3)...
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+  (fib (- n 1))
                  (fib (- n 2))))))

; next with iterative process
; after each step,
; a <- a + b
; b <- a

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
    b
    (fib-iter (+ a b) a (- count 1))))


; now for final logarithmic process

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
          (fib-iter a
                    b
                    (+ (square p) (square q))
                    (+ (square q) (* 2 p q))))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

GCD(206,40) = GCD(40,6)
            = GCD(6,4)
            = GCD(4,2)
            = GCD(2,0)
            = 2

(define (gcd a b)
  (if (= b 0)
    a
    (gcd b (remainder a b))))

(gcd 206 40)
(if (= 40 0)...)
(gcd 40 (remainder 206 40))
(if (= (remainder 206 40) 0))
(if (= 6 0))
(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
(if (= (remainder 40 (remainder 206 40)) 0) ...)
(gcd (remainder 40 (remainder 206 40) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
...


(define (count-remainders n)
  (define (loop n sum)
    (if (= n 0) (- sum 1)
        (loop (- n 1) (+ sum (fib n) (fib (- n 1))))))
  (loop n 0))

; whereas if it is applicative-order

(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 40 6)
(gcd 6 (remainder 40 6))
(gcd 6 4)
(gcd 4 (remainder 6 4))
(gcd 4 2)
(gcd 2 (remainder 4 2))
(gcd 2 0)
2

; if n is prime, smallest divisor greater than 1 is n; if n = 2, it is prime also


(define (prime? n)
  (= n (smallest-divisor n)))

(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 (smallest-divisor n (+ test-divisor 1)))))

(define (divides? test-divisor n)
  (= (remainder n test-divisor) 0))

(define (square x) (* x x))

(define (remainder n divisor)
  (if (< n divisor)
    n
    (remainder (- n divisor) divisor)))

(smallest-divisor 199)
(smallest-divisor 1999)
(smallest-divisor 19999)

; if n is not prime it must have a divisor less than or equal to sqrt(n)
; order of growth (k sqrt(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))) ; if true, repeat with times-1
        (else false)))


; search-for-primes 1000
; to find the three smallest primes larger than 1000, then 10,000, then 100,000, ...
; note the time needed to test each prime

(define (search-for-primes range-start)
  (if (even? start)
    (find-primes (+ start 1) 3) ; if even, plus one
    (find-primes (+ start 2) 3))) ; if odd, disregard starting number



(define (square x) (* x x))

(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)))

; auxiliary functions above, main functions below

(define (search-for-primes start)
  (if (even? start)
    (search-iter (+ start 1) 3) ; one of these will jump into search-iter function!
    (search-iter (+ start 2) 3)); supplied count = 3, current value depends on even/odd

(define (search-iter current count)
  (cond ((= count 0) 0)) ; below is multiple executions in single body clause????
        ((prime? current) ((timed-prime-test current) (search-iter (+ current 2) (- count 1))))
        (else (search-iter (+ current 2) count)))

(define (timed-prime-test n)
  (start-prime-test n runtime))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime n (- (runtime) start-time))))

(define (report-prime n elapsed-time)
  (newline)
  (display n)
  (display " *** ")
  (display elapsed-time))