SICP - Exercícios 1.16 a 1.19 - Exponenciação, Multiplicação, e Fibonacci em tempo logarítmico

Exercício 1.16
Projete um procedure que desenvolva um processo iterativo de exponenciação que use uma sucessão de quadrados e também use um número logarítmico de passos, assim como fast-expt. (Dica: usando a observação de que (b^n/2)² = (b²)^n/2, mantenha, junto com o expoente n e a base b, uma variável de estado adicional a, e defina a transformação de estado de tal maneira que o produto abⁿ se mantenha constante de estado para estado. No início, tem-se a igual a 1, e a resposta é dada pelo valor de a ao final do processo. Em geral, a técnica de definir uma quantidade invariante, que não se altera de estado para estado, é uma maneira poderosa de se pensar sobre o projeto de algoritmos iterativos.)
Solução: A dica já diz tudo. Vamos ao código:

Veja que a invariante se mantém nas duas chamadas recursivas a fast-expt-iter. Para a primeira, temos a(b²)^n/2 = abⁿ. Já na segunda, temos (ab)b^n-1 = abⁿ.

Exercício 1.17: O algoritmo de exponenciação desta seção é baseado em executar a exponenciação por meio de repetidas multiplicações. De maneira similar, é possível pensar na multiplicação de inteiros por meio de adições repetidas. O seguinte procedure de multiplicação (que assume que nossa linguagem é capaz apenas de realizar adições, e não multiplicações), é análogo ao procedure expt:

Tal algoritmo tem um número de passos linear em b. Agora, suponha que a linguagem inclua, além da adição, as operações double, que dobra um inteiro, e halve, que divide um inteiro (par) por 2. Usando essas operações, projete um procedure análogo a fast-expt, que use um número de passos logaritmico.
Solução: Vamos chamar nosso procedure fast-mult. Vou copiar o código de fast-expt, para que possamos realizar as substituições necessárias.

Para chegar à definição de fast-mult a b, vamos observar as analogias:

	Exponenciação	Multiplicação
Linear em	n	b
Operação repetida	multiplicação	adição
Condição de parada	n = 0	b = 0
Resposta de parada ("elemento neutro")	1	0
Recursão em	bn = (bn/2)2	ab = 2(a(b/2))

Agora, fica fácil ver as analogias. Para chegar de fast-expt a fast-mult, subsituímos b por a, n por b, 1 por 0 (na primeira cláusula do cond), sqr por double e, finalmente, * por +. O resultado é mostrado a seguir:

Para os efeitos desse exercício, halve e double são primitivas. Como elas não o são de fato, tivemos que defini-las.

Exercício 1.18
Usando os resultados dos exercícios 1.16 e 1.17, desenvolva um procedure que gere um processo iterativo para a multiplicação de dois inteiros em termos de adições, multiplicações por 2 (double), e divisões por 2 (halve), e que use um número logarítmico de passos.
Solução: Agora, temos um análogo ao procedure fast-expt-iter, do exercício 1.16. Basta notar que ab = (2a)(b/2). Vamos usar, além de a e b, a variável de estado adicional x. No início, temos x = 0. A invariante que iremos preservar de é x+ab.

Os códigos de fast-mult-iter e fast-expt-iter apresentam, portanto, exatamente a mesma estrutura. Assim, podem ser abstraídos por procedures de ordem superior (tradução livre para higher order procedures). Isso será visto na próxima seção.

Exercício 1.19 Existe um algoritmo inteligente para computar os números de Fibonacci em um número logarítmico de passos. Lembre-se da transformação das variáveis de estado a e b no processo de fib-iter da seção 1.2.2: a ← a + b e b ← a. Denomine T essa transformação, e observe que aplicando-se T repetidamente por n vezes, começando com 1 e 0, produz o par Fib(n+1) e Fib(n). Em outras palavras, os números de Fibonacci são produzidos aplicando-se Tⁿ, a enésima potência da transformação T, começando com o par (1, 0). Agora, considere que T seja caso especial com p=0 e q=1 numa família de transformações T_pq, onde T_pq transforma o par (a, b) de acordo com a ← bq + aq + +ap e b ← bq + aq. Mostre que, se aplicarmos a transformação T_pq duas vezes, o efeito é o mesmo de se usar uma única transformação T_p'q', da mesma família, e compute p' e q' em termos de p e q. Isso nos dá uma maneira explícita de achar o quadrado de transformações dessa família, e assim podemos computar Tⁿ usando uma sucessão de quadraturas, como no procedure fast-expt. Junte isso tudo e complete o seguinte procedure, que roda em um número logarítmico de passos.

Solução: À primeira vista, esse exercício parece difícil, mas na verdade é um dos mais fáceis até agora... Basta entender o enunciado e saber um pouquinho de aritmética. Vamos lá:
Tpq(a, b) = (bq + aq + ap, bp + aq)
Tpq(Tpq(a, b)) = T2pq(a, b) = Tpq(bq + aq + ap, bp + aq) =
  ( (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p,
    (bp + aq)p + (bq + aq + ap)q )

T2pq(a, b) = ( b(2pq + q2) + a(2q2 + 2pq + p2),
               b(p2 + q2) + a(2pq + q2) )

T2pq(a, b) = ( b(2pq + q2) + a(2pq + q2) + a(p2 + q2),
               b(p2 + q2) + a(2pq + q2) )

Se considerarmos p' = p2 + q2 e q' = 2pq + q2, então temos:
T2pq(a, b) = ( bq' + aq' + ap', bp' + aq' ) = Tp'q'(a, b)
Assim, mostramos que "elevar T_pq ao quadrado" significa aplicar T_p'q', com p' = p2 + q2 e q' = 2pq + q2. O código final para fib-iter fica, portanto: