fcshel

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex1.9
;;
;;Procedure 1
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

;;This is O(a) in time and space, and is thus recursive

;;Procedure 2
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9

;;This is O(a) in time and O(1) in space.  Iterative

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex1.10

(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
.
.
.
(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 2^2))))))))
.
.
.
2^10
1024

(A 2 4)
(A 1 (A 2 3))
2^(A 2 3)
2^(A 1 (A 2 2))
2^(2^(A 2 2))
2^(2^(A 1 (A 2 1)))
2^2^2^2
65536
;; We will write this function at f(2,n) = 2_1^2_2^...^2_n so it becomes
f(2 4)
(A 3 3)
(A 2 (A 3 2))
f(2 (A 3 2))
f(2 (A 2 (A 3 1)))
f(2 f(2 (A 3 1)))
f(2 f(2 2)))
(2^2^...^2_(2^2))
(2^2^2^2)
65536

;;(f n) computes 2n
;;(g n) computes 2^n
;;(h n) computes 2\{up_arrow}^{2}n or the tetration of m with n

;;The function given here is slightly different than Ackermann's
;;function seen elsewhere (check wolfram and wiki) but seems cleaner

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.11

;;Recursive
(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1))
         (* 2 
            (f (- n 2)))
         (* 3
            (f (- n 3))))
      )
  )


;;Iterative
(define (f_iter n)
  (define (f_n fn-1 fn-2 fn-3)
      (+ fn-1
         (* 2
            fn-2)
         (* 3
            fn-3)))
  (define (iter fn-1 fn-2 fn-3 count)
    (if (= count n)
        (f_n fn-1 fn-2 fn-3)
        (iter (f_n fn-1 fn-2 fn-3)
              fn-1
              fn-2 (inc count))))
  (if (< n 3)
      n
      (iter 2 1 0 3)))

;;For n = 20, the recursive program can almost keep up, but for anything
;;over that, the difference is obvious, and by n = 50 they are
;;remarkable.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.12

(define (pascal row element)
  (if (or (= element 1) (= row element))
      1
      (+ (pascal (dec row)
                 (dec element))
         (pascal (dec row)
                 element))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.13

;;Fib(N) = \frac{\phi^N-\psi^N }{\sqrt{5}} clearly holds for Fib(0) and
;;Fib(1).  Now checking Fib(N) = Fib(N-1)+Fib(N-2), Fib(N) =
;;\frac{\phi^{N-1}-\psi^{N-1}}{\sqrt{5}}+\frac{\phi^{N-2}-\psi^{N-2}}{\sqrt{5}}
;;= \frac{(\phi^{N-1}+\phi^{N-2})-(\psi^{N-1}+\psi^{N-2})}{\sqrt{5}}.  As
;;\psi and \phi are both roots of the equation x^2-x-1 = 0, we can
;;multiply by x^{N-2} and rearrange to get x^N = x^{N-1} + x^{N-2}, thus
;;showing:
;;\frac{\phi^N-\psi^N }{\sqrt{5}} =
;;\frac{\phi^{N-1}-\psi^{N-1}}{\sqrt{5}}+\frac{\phi^{N-2}-\psi^{N-2}}{\sqrt{5}}.

;;Now, as \abs{\psi}<1, \abs{\frac{\psi}{\sqrt{5}}}<\frac{1}{2}.  As
;;\abs{\phi^N} is a positive decreasing function, for all N,
;;\frac{\psi^N}{\sqrt{5}}< \frac{1}{2}.  Thus \frac{\phi^N}{\sqrt{5}} is
;;the closest integer to Fib(N) and we can calculate Fib(N)  by
;;rounding this function.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.14

;;The tree diagram is large enough that I think I will skip drawing it
;;here.  I originally throught that this was O(e^amount) in time as the
;;branches approximately double each step.  However, Bill the Lizard gives
;;a nice discussion of this on his blog in which he shows that the
;;branching is moderated by the number of coins available, and thus,
;;exponential in that.  The program is actually O(amount^5).  In space is
;;is O(amount)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.15

;;a. 12.15/3^5 = 0.05 so (p x) is called 5 times.

;;b. Angle/3^n ~0.1, so n~ ln(angle/0.1/3).  Thus n~ln(angle).  As n
;;counts both the number of steps and the number of calls to (p x), this
;;program is O(log(angle)) in space and time.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.16

;;We define the transform a b n (n even)-> a (square b) (/ n 2)
;;				(n odd)-> (* b a) b (dec n)
;;This preserves the product a*b^n and will give us an process which is
;;O(1) in space and still O(log(n)) in time.

(define (exp-iter base exp)
  (define (iter a b n)
    (cond ((= n 0) a)
          ((even? n)
           (iter a (square b) (/ n 2)))
          (else (iter (* b a) b (dec n)))))
  (iter 1 base exp))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.17

(define (fast-mult a b)
  (cond ((= b 1) a)
        ((even? b)
         (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.18

;; For state variables a b c, equation of state is ab+c and the
transform is 
;;		 a b c (b even)-> (double a) (halve b) c
;;		 a b c (b odd)-> a (dec b) (+ c a)

;; do this until (= b 1) and return (+ a c)

(define(fast-mult-iter a b)
  (define (iter x y z)
    (cond ((= y 1) (+ x z))
          ((even? y) (iter (double x) (halve y) z))
          (else (iter x (dec y) (+ z x)))))
  (iter a b 0))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.19

(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))
                   (/ count 2)))
        (else (fib-iter (+ (* b p) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

;;Admittedly, I don't really understand this transformation.  Does
;;anyone have any insight into this?

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.20

;;Normal-order
(gcd 206 40)
(gcd 40 (remainder 206 40))
(remainder 206 40)->6
(gcd (remainder 206 40)
     (remainder 40 (remainder 206 40)))
(remainder 40 (remainder 206 40))->4
(gcd (remainder 40 (remainder 206 40))
     (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
(remainder (remainder 206 40)
           (remainder 40 (remainder 206 40)))->2
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
     (remainder (remainder 40 (remainder 206 40))
                (remainder (remainder 206 40)
		           (remainder 40 (remainder 206 40))))
(remainder (remainder 40 (remainder 206 40))
           (remainder (remainder 206 40)
           (remainder 40 (remainder 206 40))))->0
(remainder (remainder 206 40)
	   (remainder 40 (remainder 206 40)))->2
;;Counting up the (remainder ) calls gives 18

;;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

;;That's 4 calls

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.21

> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7
> (/ 19999 7)
2857

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.22

(define (search-for-primes a b)
  (cond ((> a b) )
        ((even? a) (if (= a 2)
		     ((timed-prime-test a) (search-for-primes (+ a 1) b))
		     (search-for-primes (+ a 1) b)))
        (else (timed-prime-test a)
              (search-for-primes (+ a 2) b))))

;;Editted to pull just the primes

> (search-for-primes 1000 1020)

1009 *** 15
1013 *** 14
1019 *** 14done
(/ (+ 15 14 14) 3)
14.33

(search-for-primes 10000 10100)

10007 *** 42
10009 *** 42
10037 *** 41
(/ (+ 42 42 41) 3)
41.67

(search-for-primes 100000 100050)

100003 *** 125
100019 *** 128
100043 *** 126
(/ (+ 125 128 126) 3)
126.33

(search-for-primes 1000000 1000050)

1000003 *** 407
1000033 *** 396
1000037 *** 395
(/ (+ 407 396 395) 3)
399.33

;;Given that this program grows O(sqrt(n)), we would expect our times to
;;increase as sqrt(10) with each step.  Checking this as a fractional
;;difference from sqrt(10), t_10n/t_n~sqrt(10) so the fractional
;;difference is 1-t_10n/(sqrt(10)t_n).

;;10000/1000    1-41.33/(sqrt(10)14.67)=0.11

;;100000/10000  1-126.33/(sqrt(10)41.33)=0.03

;;1000000/100000  1-399.33/(sqrt(10)126.33)=0.0004

;;These are all shorter than the O(sqrt(n)) however as n increases,
;;agreement improves.  As the O(sqrt(n)) part of our program grows
;;larger, it dominates over smaller terms, giving better agreement.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.23

(define (next n)
  (if (= n 2)
      3
      (+ n 2)))

;;Pluging this in gives:
> (search-for-primes 1000 1020)

1009 *** 12
1013 *** 11
1019 *** 11
(/ (+ 12 11 11) 3)
11.33

> (search-for-primes 10000 10050)

10007 *** 28
10009 *** 28
10037 *** 28
28

> (search-for-primes 100000 100050)

100003 *** 84
100019 *** 90
100043 *** 82
(/ (+ 84 90 82) 3)
85.33

> (search-for-primes 1000000 1000040)

1000003 *** 256
1000033 *** 272
1000037 *** 251
(/ (+ 256 272 251) 3)
259.67

;;With the answers from the last question, the ratios between the times of
;;the two programs are:

;;1000
(/ 14.33 11.33)
1.26

;;10000
(/ 41.67 28)
1.49

;;100000
(/ 126.33 85.33)
1.48

;;1000000
(/ 399.33 259.67)
1.54

;;These are all substantially less than 2. I suppose it is that we also
;; added n/2 function calls

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.24

;;This gave

1009 *** 44
1013 *** 48
1019 *** 46
	 46
10007 *** 60
10009 *** 52
10037 *** 54
	  55.33
100003 *** 59
100019 *** 60
100043 *** 62
	   60.33
1000003 *** 66
1000033 *** 71
1000037 *** 68
	    68.33

;;Given that the procedure displays O(log n) growth, I would expect each
;;of these to differ by a constant value which is approximately what we
;;see.  Times for 1000000 and 1000 should differ by O(log 1000), or
;;1000000 should be approximately twice the time we see for 1000.  As at
;;1000, lower terms contribute much more than they do at 1000000, The
;;ratio between them should be slightly less than two, which is what we
;;observe.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.25

While this procedure will work, it will be far from fast.  The remainder
calls which I believe grow in time with O(n) will be to the result of
the exponent rather than multiple calls to a value mod m.  This will
cause the program to slow down significantly.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.26

Louis's program will evaluate (expmod base (/ exp 2) m) twice.  Thus,
while in the original program we were halving out work each time, in
Josh's implementation we are preceding to do that work twice, and we end
up with a process that grows with O(n).

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.27


(define (carmichael-test n)
  (define (check-iter m)
    (cond ((= m n) true)
          ((= (expmod m n n) m) (check-iter (+ m 1)))
          (else false)))
  (check-iter 1))


> (carmichael-test 561)
#t
> (carmichael-test 1105)
#t
> (carmichael-test 1729)
#t
> (carmichael-test 2465)
#t
> (carmichael-test 2821)
#t
> (carmichael-test 6601)
#t

;;Ex. 1.1

;;* 10
;;* 12
;;* 8
;;* 3
;;* 6
;;*
;;*
;;*19
;;* #f
;;* 4
;;* 16
;;* 6
;;* 16

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.2

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
   (* 3 (- 6 2) (- 2 7)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.3

(define (SOS-2OF3 a b c)
	(- (+ (square a) (square b) (square c))
	   (square (cond ((and (<= a b) (<= a c)) a)
		      ((<= b c) b)
		      (else c)))))

;Don't forget about cases of equivalence!

;;or even simpler

(define (SOS-2LARGEST a b c)
	(- (+ (square a) (square b) (square c)) (square (min a b c))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.4

;;Given two numbers a and b, if b is greater than 0 it will return a+b and
;;if b is less than or equal to zero it will return a-b.


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.5

;;An applicative-order interpreter will first evaluate 0 and (p), sending
;;it into an infinite loop.  A normal-order interpreter will expand the
;;body of test before evaluating.  As the <alternative> of an if statement
;;does not evaluate if the <predicate> is true, (p) is never evaluated and
;;the program returns 0.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.6

;;If and cond are special forms such that all operands are not necessarily ;;evaluated.
;;As new-if is evaluated as a regular combination, square-iter is
;;evaluated before it is expanded into a cond and the program enters an
;;infinite loop.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex 1.7

;;Good enough clearly fails for numbers near .001.  For an example of a
;;square root we can easily do in our head:

(good-enough? .0001 .0001)
>#t

;;;;;;;;;;;;;;;;;
;;A different but related problem occurs with large numbers.  If the
;;square root of a number contains too many digits for scheme to store its
;;thousands place, good-enough? will not be able to reach the answer to
;;within .001 and our program will iterate forever.
;;
;;A better test might be:
;;;;;;;;;;;;;;;;;

(define (good_enough_imprv? old_guess new_guess)
  (< (abs (/ (- new_guess old_guess) old_guess)) .00001))

;; I gave it some extra precision as we are now talking relative
;;precision vs. absolute precision.  Generally, when talking about square
;;roots of order 10^3, I would like to be correct to .01, giving 10^-5 for
;;my desired precision

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

(define (improve guess x)
  (average guess (/ x guess)))
  
(define (sqrt-iter new_guess old_guess x)
  (if (good_enough_imprv? old_guess new_guess)
      new_guess
      (sqrt-iter (improve new_guess x) new_guess x)))

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

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;Ex. 1.8

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

(define (cbrt-iter new_guess old_guess x)
  (if (good_enough_imprv? old_guess new_guess)
      new_guess
      (cbrt-iter (improve-cbrt new_guess x) new_guess x)))
  
(define (my_cbrt x)
  (cbrt-iter 1.0 2.0 x))