CODEWITHSUNDEEP
schemelispsicpnewtons-method
AK-CHP
AK-CHP

Reputation: 101

Getting an wrong answer in scheme program

I am trying to find the cube root of a number using Newton's method. I wrote scheme procedures as follows:

(define (cbrt x)
    (cbrt-iter 1.0 x))

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

(define (good-enough? guess x)
    (< (- guess (improve guess x)) 0.00001))

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

(cbrt 27)
(cbrt 8)
(cbrt 64)

Actually I am working on Exercise 1.8 of the famous (or may be infamous) book SICP. then I run scheme < cuberoot.scm and got the following result:

MIT/GNU Scheme running under GNU/Linux
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2019 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Thursday September 5, 2019 at 11:51:46 AM
  Release 10.1.10 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/x86-64 4.118

1 ]=> (define (cbrt x)
    (cbrt-iter 1.0 x))
;Value: cbrt

1 ]=> (define (cbrt-iter guess x)
    (if (good-enough? guess x) guess (cbrt-iter (improve guess x) x)))
;Value: cbrt-iter

1 ]=> (define (good-enough? guess x)
    (< (- guess (improve guess x)) 0.00001))
;Value: good-enough?

1 ]=> (define (improve guess x)
    (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))
;Value: improve

1 ]=> (cbrt 27)
;Value: 1.

1 ]=> (cbrt 8)
;Value: 1.

1 ]=> (cbrt 64)
;Value: 1.

1 ]=> 
End of input stream reached.
Post proelium, praemium.

The program is always producing 1. as a result. I also tried adjusting the threshold value in good-enough? procedure from 0.00001 to 0.0001 and so on but that didn't worked. Please explain what went wrong and how to fix that.

Upvotes: 0

Views: 66

Answers (2)

coredump
coredump

Reputation: 38914

MIT-SCHEME can help you, see Tracing Procedures in MIT-Scheme. Tracing is a way for the interpreter to indicate what expression currently being computed, and what result it yields. After having entered your definitions, you can trace your procedures as follows:

(trace cbrt-iter)
(trace good-enough?)
(trace improve)
(trace cbrt)

Here is the interaction with input 64:

1 ]=> (cbrt 64)

[Entering #[compound-procedure 15 cbrt]
    Args: 64]
[Entering #[compound-procedure 12 cbrt-iter]
    Args: 1.
          64]
[Entering #[compound-procedure 13 good-enough?]
    Args: 1.
          64]
[Entering #[compound-procedure 14 improve]
    Args: 1.
          64]
[22.
      <== #[compound-procedure 14 improve]
    Args: 1.
          64]
[#t
      <== #[compound-procedure 13 good-enough?]
    Args: 1.
          64]
[1.
      <== #[compound-procedure 12 cbrt-iter]
    Args: 1.
          64]
[1.
      <== #[compound-procedure 15 cbrt]
    Args: 64]
;Value: 1.

Each time you call a traced procedure, you see:

[Entering ...]

Each time that procedure exits, its value is printed:

[XYZ
      <== <CALL THAT PRODUCED THE VALUE>]

Here, you can see that (improve 1. 64) returned 22, and that 22 is a good-enough value, from the result of (good-enough? 1. 64). Then you can see that (cbrt-iter 1. 64) returned 1.

Upvotes: 1

jthulhu
jthulhu

Reputation: 8678

You need to include an (abs ...) in good-enough?, otherwise you don't just see if two values are close enough, but just if one value is greater than another (approximately).

(define (good-enough? guess x)
  (< (abs (- guess (improve guess x))) 0.00001))

Upvotes: 1

Related Questions