Search This Blog

Wednesday, February 16, 2011

Clojure Dojo 2: What about numbers that aren't 10?

;; We've so far implemented Heron's method for finding the square root of
;; the number 10. The program looks like this:

(defn average [a b] 
  (/ (+ a b) 2))

(defn improve-guess [guess]
  (average guess (/ 10 guess)))

(defn abs[x] 
  (if (< x 0) (- x) x))

(defn good-enough? [guess] 
  (< (abs (- 10 (* guess guess))) 1e-6))

(defn good-enough-guess [x]
  (if (good-enough? x) x
      (good-enough-guess (improve-guess x))))

;; At this point, it might be a good idea to put the functions in a file. 
;; If we use a lisp-conscious IDE (EMACS, the Editor for Middle Aged Computer Scientists, is my favourite)
;; Then we can carry on our conversational style of development.

;; In fact, this program is easily generalized. Our first task is to make a more general
;; iterative-improve function.  This function should take a guess, a function to improve guesses,
;; and a function to tell when guesses are good enough, and return an answer which is good enough,
;; which it should find by repeatedly improving the guesses.

;; We almost have this function already. We just need to make the constants in good-enough-guess into arguments.

(defn iterative-improve [x improve good?]
  (if (good? x) x
      (iterative-improve (improve x) improve good?)))

;; Let's test that: (In emacs, put the cursor at the end of the expression and type C-x C-e to evaluate the expression)

(iterative-improve 1.0 improve-guess good-enough?)

;; Or in fact, we can use C-u C-x C-e to evaluate it and paste it into the buffer.

(iterative-improve 1.0 improve-guess good-enough?)

;; (* 3.162277665175675 3.162277665175675) is 10.000000031668918, so we haven't broken our method.

;; Of course to find the square roots of numbers other than 10, we need functions that will make our guesses closer and tell whether the answers are good enough.

;; It would be a terrible thing to have to hand code them every time. But we can make functions which make functions:

(defn make-improver [n]
  (fn [guess] (average guess (/ n guess))))

(def f (make-improver 25))

(f 1.0)                                 ;13.0

(f (f 1.0))                             ;7.461538461538462
(take 10 (iterate f 1.0))               ;(1.0 13.0 7.461538461538462 5.406026962727994 5.015247601944898 5.000023178253949 5.000000000053722 5.0 5.0 5.0)

(defn make-good-enough? [n]
  (fn [guess] (< (abs (- n (* guess guess))) 1e-6)))

(def g? (make-good-enough? 25))

(take 10 (map g? (iterate f 1.0)))      ;(false false false false false false true true true true)

(iterative-improve 1.0 f g?)            ;5.000000000053722

;; So now we can find arbitrary square roots

(defn square-root [n]
     (iterative-improve 1.0 (make-improver n) (make-good-enough? n)))

(square-root 2)                         ;1.4142135623746899

1 comment:

  1. Just for the record, I'll repeat the comment from the previous post. You should use recur in iterative-improve.

    "Note that recur is the only non-stack-consuming looping construct in Clojure. There is no tail-call optimization and the use of self-calls for looping of unknown bounds is discouraged. recur is functional and its use in tail-position is verified by the compiler."