Without prior knowledge of Scheme's floor and rounding functions, how can SICP Exercise 1.45 (making an nth root function) be completed?

user_10319707 0
Viewed 150

While completing SICP's Exercise 1.45, one soon notices that the number of times that the average-damp procedure needs to be applied to find the nth root of a number is very well approximated by the base 2 logarithm of n, rounded down. In other words, we use (floor (/ (log n) (log 2))). Numerous online solutions take this exact approach, with the only exception that I can find being a complex and uncommented solution from the Schemewiki.

However, as far as I've been able to find, Structure and Interpretation of Computer Programs does not introduce any form of rounding (e.g. floor) until after the chapter where this exercise appears. This raises the question: do we know anything at all about how this exercise was intended to be completed by readers? Or failing that, is there any obvious way to do it (i.e. round down (/ (log n) (log 2))) without prior knowledge of floor?

sicp scheme lisp rounding
1 Answers

I don't see that you need to know about the Scheme procedure floor at all, because the instructions for the exercise say explicitly that you may "assume that any arithmetic operations you need are available as primitives." If you need floor, you may assume that it is available.

But as it turns out, you do not need floor anyway. Just define repeated in such a way that floating point counts are effectively floored:

(define (repeated f n)
  (if (< n 2)
      f
      (lambda (x) (f ((repeated f (- n 1)) x)))))

Combining this with the other definitions from the book lets you define nth-root with no floor procedure:

(define (nth-root x n)
  (fixed-point ((repeated average-damp
                          (/ (log n) (log 2)))
                (lambda (y) (/ x (expt y (- n 1)))))
               1.0))
user_68798260
Related