What's wrong with this Newton's Method implementation in Scheme?

Question

Where is my flaw in the following code?

(define (newtons-method2 f guess n)
(define (newton-transform f)
 (lambda (x)
  (- x (/ (f x) ((der f 0.5) x)))))
(let ((next (newton-transform guess)))
(if (= 0 n)
    next
    (newtons-method2 (f next (- n 1))))))

The method is named "newtons-method2" because this was my second attempt at writing newton's method in scheme

My derivative function is as follows:

(define (der f h)
 (lambda (x)
 (/ (- (f(+ x h)) (f x))
    h)))

Answer 1

There are probably several problems, I found these:

(newtons-method2 (f next (- n 1))
->
(f next (- n 1))

this is evaluating f with parameters next and n-1, but you want to pass all 3 as parameters:

(newtons-method2 f next (- n 1))

Be careful with parentheses, they fundamentally alter what the program does. Just because they balance, doesn't mean the program does anything meaningful.

0.5 for delta is a huge value, and likely will cause problems when calculating the approximations. how about 0.00001?

Learn to do proper indentation, so arguments line up below each other. Again, this is related to parentheses. It's almost impossible to read your code.

Also, here's a nice implementation with explanation from the SICP lectures (highly recommended, brilliant): http://www.youtube.com/watch?v=erHp3r6PbJk&list=PL8FE88AA54363BC46 (from 43:14)

Answer 2

You didn't ask this, but here is an alternate method for computing the square root:

(define (root n)
  (if (< n 1) (/ (root (* n 4)) 2)
    (if (<= 4 n) (* (root (/ n 4)) 2)
      (let ((x (/ (+ 2. n) 2)))
        (let ((x (/ (+ x (/ n x)) 2)))
          (let ((x (/ (+ x (/ n x)) 2)))
            (let ((x (/ (+ x (/ n x)) 2)))
              (let ((x (/ (+ x (/ n x)) 2)))
                (let ((x (/ (+ x (/ n x)) 2)))
                  x)))))))))

This normalizes n to the range 1 <= n < 4 then unrolls the loop and performs five iterations, with an initial estimate of 2 which is the geometric mean of the range; it is possible to prove that five iterations is sufficient for double-precision arithmetic because n is known to be within a limited range. The formula used is due to Heron, which predates Newton's method by 16 centuries.