Exercise1-14 <---> Exercise1-16
Exercise 1.15
The sine of an angle (specified in radians) can be computed by making use of the approximation sin x ~ x if x is sufficiently small, and the trigonometric identity
to reduce the size of the argument of sin. (For purposes of this exercise an angle is considered "sufficiently small" if its magnitude is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
a. How many times is the procedure p applied when (sine 12.15) is evaluated?
b. What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure when (sine a) is evaluated?
Ru: Синус угла (заданного в радианах) можно вычислить, если воспользоваться приближением sin x ~ x при малых x и употребить тригонометрическое тождество
для уменьшения значения аргумента sin. (В этом упражнении мы будем считать, что угол «достаточно мал», если он не больше 0.1 радиана.) Эта идея используется в следующих процедурах:
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
а. Сколько раз вызывается процедура p при вычислении (sine 12.15)?
б. Каковы порядки роста в терминах количества шагов и используемой памяти (как функция a) для процесса, порождаемого процедурой sine при вычислении (sine a)?
Solution: a.
(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))
(p (p (p (p (p 0.05)))))
P is applied 5 times.
b. The process is O(log(a)) in both space and time. Specifically it’s O(log3(n)).
Exercise1-14 <---> Exercise1-16