Why is my cubic root algorithm wrong? Exercise 1.8 in SICP

Question

> Fixed,

it was not a huge number but a fraction of two huge numbers, so I got a false alarm. The algorithm was right; modifying the last input parameter now the interpreter retrieves it as a decimal comma, and looks like the small number it always was.

I'm doing Exercise 1.8 from SICP and Scheme's interpreter ̵f̵̵r̵̵e̵̵e̵̵z̵̵e̵s̵ returns wrong answers when I evaluate my algorithm. Does anybody know why?

Newton’s method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by the value (x/(y^2)+(2*y))/3. Use this formula to implement a cube-root procedure analogous to the square-root procedure.

(define (cubert x)
        (cubert-iter x x 1))

(define (cubert-iter x previous guess)
        (if (good-enough previous guess)
             guess
             (cubert-iter x guess (improve x guess))))

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

(define (good-enough previous guess)
        (< (/ (max (square previous)
                   (square guess))
              (min (square previous)
                   (square guess)))
           tolerance))

(define tolerance 2)

(cubert 1000) ̴f̴̴r̴̴e̴̴e̴̴z̴̴e̴s̴ gives an huge 100-digit number (cubert 27) returns something like 3049534534593845092305345 It may have an evaluation order mistake, but I can't see it

Is there a specific input that causes your algorithm to freeze? — David Eisenstat
(improve 1000) produces 334, but running the whole algorithm (cubert 1000) freezes It may have an infinite loop or an evaluation order mistake, but I can't see it — Andres Massigoge
Fixed, it was not a huge number but a fraction of two huge numbers, so false alarm. The algorithm was right; modifying the last input parameter now the interpreter retrieves it as a decimal comma, and looks like the small number it always was. — Andres Massigoge

Sylwester Sylwester · Accepted Answer · 2017-01-05T15:33:01

Scheme will in most implementations that has exact fixnums try to keep these numbers exact during the whole execution. If you were to do division of something that would never be able to have an exact float, like 1 divided by 3:

(/ 1 3)
; ==> 1/3

You get the exact value 1/3. The result of (cubert 27) is totally fixnum operations so it also will yield a fraction result:

(cubert 27)
; ==> 3 5164693972157389706641814378288819200000000/10804364367444398305386468912180491314165089

If you want a less exact number, like a float, you can either force it by starting off with an inexact value or you can convert the exact result with exact->inexact afterwards:

(cubert #i27)                ; ==> 3.48
(exact->inexact (cubert 27)) ; ==> 3.48

You may also forece it in your algorithm by using inexact 2, ie. #i2 or `2.02, when you multiply. That will force an inexact result.

Why is my cubic root algorithm wrong? Exercise 1.8 in SICP

> Fixed,

1 Answers