# SICP - Solution: Exercise 1.15

##### October 10, 2018

## Exercise 1.15 #

The sine of an angle (specified in radians) can be computed by making use of the approximation ${\sin x\approx x}$ if $x$ is sufficiently small, and the trigonometric identity

$$\sin x = 3 \sin\frac x3-4 \sin^3\frac x3$$

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)))))`

- How many times is the procedure
`p`

applied when`(sine 12.15)`

is evaluated?- 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?

## Solution #

First, let’s just run the program with a `display`

in `sine`

so that we can see the details of each steps:

```
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle step)
(display step) (display ": ") (display angle) (newline)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0) (+ step 1)))))
(display (sine 12.15 1))
```

Which results in:

```
1: 12.15
2: 4.05
3: 1.3499999999999999
4: 0.44999999999999996
5: 0.15
6: 0.049999999999999996
-0.39980345741334
```

Based on that, we can just write a function that will display directly a table formatted in Markdown that I can just cut and paste:

```
(define (sine-count-step angle step)
(if (not (> (abs angle) 0.1))
step
(sine-count-step (/ angle 3.0) (+ step 1))))
(display "| ") (display "a ") (display " | ") (display "number of steps ") (display " |") (newline)
(display "| ") (display "----------") (display " | ") (display "-----------------------------") (display " |") (newline)
(display "| ") (display 12 ) (display " | ") (display (sine-count-step 12 1)) (display " |") (newline)
(display "| ") (display 120 ) (display " | ") (display (sine-count-step 120 1)) (display " |") (newline)
(display "| ") (display 1200 ) (display " | ") (display (sine-count-step 1200 1)) (display " |") (newline)
(display "| ") (display 12000 ) (display " | ") (display (sine-count-step 12000 1)) (display " |") (newline)
(display "| ") (display 120000 ) (display " | ") (display (sine-count-step 120000 1)) (display " |") (newline)
(display "| ") (display 1200000 ) (display " | ") (display (sine-count-step 1200000 1)) (display " |") (newline)
(display "| ") (display 12000000 ) (display " | ") (display (sine-count-step 12000000 1)) (display " |") (newline)
```

a | number of steps |
---|---|

12 | 6 |

120 | 8 |

1200 | 10 |

12000 | 12 |

120000 | 14 |

1200000 | 16 |

12000000 | 18 |

It is easy to see the trend: every time $a$ is multiplied by 10, the number of steps increase by 2. It looks like a logarithm. I could also have noticed that for every iteration, $a$ is divided by 3. So the iteration will stop when:

$$\frac a{3^n}<0.1$$

Which can be rewritten to take out the $n$ as:

$$\frac a{0.1}<3^n$$

$$\log\left(\frac{\displaystyle a}{\displaystyle0.1}\right)<\log\left(3^n\right)$$

$$\log(a)-\log(0.1)<n.\log\left(3\right)$$

$$\frac{\log(a)-\log(0.1)}{\log\left(3\right)}<n$$

Which means that the iteration are ${\mathrm\Theta(\log(a))}$