SICP Exercício 1.15 - Calculando o seno

O seno de um ângulo (especificado em radianos) pode ser computado fazendo uso da aproximação sin x ≈ x, se x é suficientemente pequeno, e da identidade trigonométrica
sin x = 3 sin x/3 - 4 sin3 x/3
para redzir o tamanho do argumento da função seno. (Para os propósitos deste exercício, um ângulo é considerado "suficientemente pequeno" se seu módulo não é maior que 0.1 radianos). Essas ideias são incorporadas nos seguintes procedures:

a. Quantas vezes o procedure p é aplicado quando (sine 12.15) é avaliado?
b. Qual é a ordem de crescimento em espaço e número de passos (como uma função de a) usada pelo processo gerado pelo procedure sine quando a expressão (sine a) é avaliada?
Solução:
a. O procedure p é aplicado 5 vezes. Vamos avaliar a expressão 12.15 manualmente:

De agora em diante, vamos pular as avaliações dos ifs.

Agora, a expansão acabou. Vai começar a redução. Desde já, podemos ver que o procedure p é chamado exatamente 5 vezes. Os passos a seguir são mostrados apenas para que possamos ver todo o cálculo.

b. A ordem de crescimento, em fumção de a, do processo gerado pelo procedure sine quando a expressão (sine a) é avaliada, é log a, tanto em espaço quanto em número de passos.
Primeiramente, vamos chamar de k(a) o número de vezes que o procedure p é chamado, em função de a.
Observando a estrutura do código, podemos chegar à seguinte fórmula.
k(a) = 0, se |a| ≤ 0.1
k(a) = 1 + k(a/3), caso contrário.
Vamos expandir k(a/3):
k(a/3) = 1, se |a|/3 ≤ 0.1, ou seja, se |a| ≤ 0.3
k(a/3) = 1+ k(a/32), caso contrário
Voltando para k(a), podemos dizer:
k(a) = 0, se |a| ≤ 0.1
k(a) = 1, se 1 < |a| ≤ 0.3
k(a/3) = 1+ k(a/32), caso contrário
Ora, tal expansão nos leva a pensar em um padrão. A fórmula fechada para k(a) é
k(a) = 0, se |a| ≤ 0.1
k(a) = teto(log(a/0.1, 3)), caso contrário.
Na fórmula anterior, log(x, y) significa o logaritmo de x na base y, e a função teto(x) é definida como o menor inteiro maior ou igual a x.
Assim, teto(0) = 0, mas teto(0.000001) = 1. De fato, para a=12.15 temos log(121.5, 3) = 4.369070246428542 e, portanto, k(12.15) = 5.
Para responder (finalmente) ao exercício, vamos considerar que as funções cube e p executam um número constante de passos. Isso só é verdade se os argumentos dessas funções não forem muito grandes, mas para o propósito desse exercício podemos assumir tal fato. Daí, fica fácil observar que:

1. k(a) é da ordem de log a
2. O espaço utilizado é proporcional a k(a), portanto sine também é da ordem de log a
   
3. O mesmo vale para o número de passos, uma vez que consideramos (cube a) e (p a) constantes em a