如果事先不了解 Scheme 的底函数和舍入函数，如何完成 SICP 练习 1.45（计算 n 次方根函数）？

Question

正在完成 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。

但是，据我所知，Structure and Interpretation of Computer Programs 没有引入任何形式的舍入（例如 floor）直到在本练习出现的章节之后。这就提出了一个问题：我们对读者打算如何完成这个练习一无所知吗？或者做不到这一点，是否有任何明显的方法可以做到这一点（即向下舍入 (/ (log n) (log 2))）而无需事先了解 floor？

Answer 1

我认为您根本不需要了解 Scheme 程序 floor，因为练习说明明确指出您可以“假设您需要的任何算术运算都可以作为原语使用。" 如果您需要 floor，您可以假设它是可用的。

但事实证明，您根本不需要 floor。只需以浮点计数有效的方式定义 repeated：

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

将此与书中的其他定义相结合，您可以在没有 floor 过程的情况下定义 nth-root：

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

如果事先不了解 Scheme 的底函数和舍入函数，如何完成 SICP 练习 1.45（计算 n 次方根函数）？

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

scheme

lisp

rounding

sicp