1.2 Procedimentos e os Processos que Eles Geram

Agora consideramos os elementos da programação: usamos operações aritméticas primitivas, combinamos essas operações e abstraímos essas operações compostas definindo-as como procedimentos compostos. Mas isso não é suficiente para nos permitir dizer que sabemos programar. Nossa situação é análoga à de alguém que aprendeu as regras de como as peças se movem no xadrez, mas não sabe nada sobre aberturas típicas, táticas ou estratégias. Como o jogador iniciante de xadrez, ainda não conhecemos os padrões comuns de uso no domínio. Falta-nos o conhecimento de quais movimentos valem a pena fazer (quais procedimentos valem a pena definir). Falta-nos a experiência para prever as consequências de fazer um movimento (executar um procedimento).

A capacidade de visualizar as consequências das ações em consideração é crucial para se tornar um programador especialista, assim como é em qualquer atividade criativa e sintética. Para se tornar um fotógrafo especialista, por exemplo, é preciso aprender a olhar para uma cena e saber quão escura cada região aparecerá em uma impressão para cada possível escolha de exposição e condições de desenvolvimento. Somente então podemos raciocinar de trás para frente, planejando o enquadramento, a iluminação, a exposição e o desenvolvimento para obter os efeitos desejados. O mesmo acontece com a programação, onde estamos planejando o curso de ação a ser tomado por um processo e onde controlamos o processo por meio de um programa. Para nos tornarmos especialistas, devemos aprender a visualizar os processos gerados por vários tipos de procedimentos. Somente depois de desenvolver essa habilidade podemos aprender a construir programas que exibam o comportamento desejado de forma confiável.

Um procedimento é um padrão para a evolução local de um processo computacional. Ele especifica como cada estágio do processo é construído sobre o estágio anterior. Gostaríamos de ser capazes de fazer afirmações sobre o comportamento global de um processo cuja evolução local foi especificada por um procedimento. Isso é muito difícil de fazer em geral, mas podemos pelo menos tentar descrever alguns padrões típicos de evolução de processos.

Nesta seção, examinaremos algumas "formas" comuns para processos gerados por procedimentos simples. Também investigaremos as taxas nas quais esses processos consomem os importantes recursos computacionais de tempo e espaço. Os procedimentos que consideraremos são muito simples. Seu papel é semelhante ao desempenhado por padrões de teste em fotografia: como padrões prototípicos super simplificados, em vez de exemplos práticos por si só.

1.2.1 Recursão Linear e Iteração

Começamos considerando a função fatorial, definida por $$n!=n\cdot (n-1)\cdot (n-2)\cdots 3\cdot 2\cdot 1.$$ Existem muitas maneiras de calcular fatoriais. Uma delas é usar a observação de que $n!$ é igual a $n$ vezes $(n-1)!$ para qualquer inteiro positivo $n$: $$n!=n\cdot [(n-1)\cdot (n-2)\cdots 3\cdot 2\cdot 1]=n\cdot (n-1)!.$$ Assim, podemos calcular $n!$ calculando $(n-1)!$ e multiplicando o resultado por $n$. Se adicionarmos a estipulação de que 1! é igual a 1, essa observação se traduz diretamente em um procedimento:

(define (factorial n)
  (if (= n 1) 
      1 
      (* n (factorial (- n 1)))))
        

Podemos usar o modelo de substituição de 1.1.5 para observar esse procedimento em ação calculando 6!, como mostrado em Figura 1.3.

Agora, vamos adotar uma perspectiva diferente sobre o cálculo de fatoriais. Poderíamos descrever uma regra para calcular $n!$ especificando que primeiro multiplicamos 1 por 2, depois multiplicamos o resultado por 3, depois por 4, e assim por diante até atingirmos $n$. Mais formalmente, mantemos um produto acumulado, juntamente com um contador que conta de 1 até $n$. Podemos descrever a computação dizendo que o contador e o produto mudam simultaneamente de um passo para o próximo de acordo com a regra

produto $\leftarrow$ contador * produto
contador $\leftarrow$ contador + 1

e estipulando que $n!$ é o valor do produto quando o contador excede $n$.

Mais uma vez, podemos reformular nossa descrição como um procedimento para calcular fatoriais:²⁹

(define (factorial n) 
  (fact-iter 1 1 n))

(define (fact-iter produto contador max-contador)
  (if (> contador max-contador)
      produto
      (fact-iter (* contador produto)
                  (+ contador 1)
                  max-contador)))
        

Como antes, podemos usar o modelo de substituição para visualizar o processo de cálculo de 6!, como mostrado em Figura 1.4.

Compare os dois processos. De um ponto de vista, eles parecem quase iguais. Ambos calculam a mesma função matemática no mesmo domínio, e cada um requer um número de passos proporcional a $n$ para calcular $n!$. De fato, ambos os processos até realizam a mesma sequência de multiplicações, obtendo a mesma sequência de produtos parciais. Por outro lado, quando consideramos as "formas" dos dois processos, descobrimos que eles evoluem de maneira bastante diferente.

Considere o primeiro processo. O modelo de substituição revela uma forma de expansão seguida de contração, indicada pela seta em Figura 1.3. A expansão ocorre à medida que o processo constrói uma cadeia de operações adiadas (neste caso, uma cadeia de multiplicações). A contração ocorre quando as operações são realmente realizadas. Esse tipo de processo, caracterizado por uma cadeia de operações adiadas, é chamado de processo recursivo. A execução desse processo exige que o interpretador mantenha o controle das operações a serem realizadas posteriormente. No cálculo de $n!$, o comprimento da cadeia de multiplicações adiadas, e, portanto, a quantidade de informações necessárias para mantê-la, cresce linearmente com $n$ (é proporcional a $n$), assim como o número de passos. Esse processo é chamado de processo recursivo linear.

Em contraste, o segundo processo não cresce e diminui. A cada passo, tudo o que precisamos manter, para qualquer $n$, são os valores atuais das variáveis produto, contador e max-contador. Chamamos isso de processo iterativo. Em geral, um processo iterativo é aquele cujo estado pode ser resumido por um número fixo de variáveis de estado, juntamente com uma regra fixa que descreve como as variáveis de estado devem ser atualizadas à medida que o processo passa de um estado para outro e um teste de fim (opcional) que especifica as condições sob as quais o processo deve terminar. No cálculo de $n!$, o número de passos necessários cresce linearmente com $n$. Esse processo é chamado de processo iterativo linear.

O contraste entre os dois processos pode ser visto de outra maneira. No caso iterativo, as variáveis do programa fornecem uma descrição completa do estado do processo em qualquer ponto. Se pararmos a computação entre os passos, tudo o que precisamos fazer para retomar a computação é fornecer ao interpretador os valores das três variáveis do programa. Isso não acontece com o processo recursivo. Nesse caso, há algumas informações "ocultas" adicionais, mantidas pelo interpretador e não contidas nas variáveis do programa, que indicam "onde o processo está" na negociação da cadeia de operações adiadas. Quanto mais longa a cadeia, mais informações devem ser mantidas.³⁰

Ao contrastar iteração e recursão, devemos ter cuidado para não confundir a noção de um processo recursivo com a noção de um procedimento recursivo. Quando descrevemos um procedimento como recursivo, estamos nos referindo ao fato sintático de que a definição do procedimento se refere (direta ou indiretamente) ao próprio procedimento. Mas quando descrevemos um processo como seguindo um padrão que é, digamos, linearmente recursivo, estamos falando sobre como o processo evolui, não sobre a sintaxe de como um procedimento é escrito. Pode parecer perturbador que nos refiramos a um procedimento recursivo como fact-iter como gerando um processo iterativo. No entanto, o processo realmente é iterativo: seu estado é completamente capturado por suas três variáveis de estado, e um interpretador precisa manter o controle de apenas três variáveis para executar o processo.

Uma razão pela qual a distinção entre processo e procedimento pode ser confusa é que a maioria das implementações de linguagens comuns (incluindo Ada, Pascal e C) é projetada de tal forma que a interpretação de qualquer procedimento recursivo consome uma quantidade de memória que cresce com o número de chamadas de procedimento, mesmo quando o processo descrito é, em princípio, iterativo. Como consequência, essas linguagens podem descrever processos iterativos apenas recorrendo a construções especiais de "looping", como do, repeat, until, for e while. A implementação de Scheme que consideraremos em Capítulo 5 não compartilha essa deficiência. Ela executará um processo iterativo em espaço constante, mesmo se o processo iterativo for descrito por um procedimento recursivo. Uma implementação com essa propriedade é chamada recursão de cauda. Com uma implementação de recursão de cauda, a iteração pode ser expressa usando o mecanismo comum de chamada de procedimento, de modo que construções especiais de iteração são úteis apenas como açúcar sintático.³¹

Exercício 1.9: Cada um dos seguintes dois procedimentos define um método para adicionar dois inteiros positivos em termos dos procedimentos inc, que incrementa seu argumento em 1, e dec, que decrementa seu argumento em 1.

(define (+ a b)
  (if (= a 0) 
      b 
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0) 
      b 
      (+ (dec a) (inc b))))
            

Usando o modelo de substituição, ilustre o processo gerado por cada procedimento ao avaliar (+ 4 5). Esses processos são iterativos ou recursivos?

Exercício 1.10: O seguinte procedimento calcula uma função matemática chamada função de Ackermann.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))
            

Quais são os valores das seguintes expressões?

(A 1 10)
(A 2 4)
(A 3 3)
            

Considere os seguintes procedimentos, onde A é o procedimento definido acima:

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))
            

Dê definições matemáticas concisas para as funções computadas pelos procedimentos f, g e h para valores inteiros positivos de $n$. Por exemplo, (k n) computa $5n^2$.

1.2.2 Recursão em Árvore

Outro padrão comum de computação é chamado recursão em árvore. Como exemplo, considere o cálculo da sequência de números de Fibonacci, em que cada número é a soma dos dois anteriores:

Em geral, os números de Fibonacci podem ser definidos pela regra $$\text{Fib}(n)=\{\begin{array}{ll}0& \text{se}n=0,\\ 1& \text{se}n=1,\\ \text{Fib}(n-1)+\text{Fib}(n-2)& \text{caso contrário}.\end{array}$$ Podemos traduzir imediatamente essa definição em um procedimento recursivo para calcular números de Fibonacci:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))
        

Considere o padrão dessa computação. Para calcular (fib 5), calculamos (fib 4) e (fib 3). Para calcular (fib 4), calculamos (fib 3) e (fib 2). Em geral, o processo evoluído se parece com uma árvore, como mostrado em Figura 1.5. Observe que os ramos se dividem em dois a cada nível (exceto na base); isso reflete o fato de que o procedimento fib chama a si mesmo duas vezes cada vez que é invocado.

Esse procedimento é instrutivo como um protótipo de recursão em árvore, mas é uma maneira terrível de calcular números de Fibonacci porque faz muita computação redundante. Observe em Figura 1.5 que toda a computação de (fib 3)—quase metade do trabalho—é duplicada. De fato, não é difícil mostrar que o número de vezes que o procedimento calculará (fib 1) ou (fib 0) (o número de folhas na árvore acima, em geral) é precisamente $\text{Fib}(n+1)$. Para ter uma ideia de quão ruim isso é, pode-se mostrar que o valor de $\text{Fib}(n)$ cresce exponencialmente com $n$. Mais precisamente (veja Exercício 1.13), $\text{Fib}(n)$ é o inteiro mais próximo de ${\phi }^n/\sqrt{5}$, onde $$\phi =\frac{1+\sqrt{5}}{2}\approx 1.6180$$ é a razão áurea, que satisfaz a equação $${\phi }^2=\phi +1.$$ Assim, o processo usa um número de passos que cresce exponencialmente com a entrada. Por outro lado, o espaço necessário cresce apenas linearmente com a entrada, porque precisamos manter o controle apenas de quais nós estão acima de nós na árvore em qualquer ponto da computação. Em geral, o número de passos necessários para um processo recursivo em árvore será proporcional ao número de nós na árvore, enquanto o espaço necessário será proporcional à profundidade máxima da árvore.

Também podemos formular um processo iterativo para calcular os números de Fibonacci. A ideia é usar um par de inteiros $a$ e $b$, inicializados para $\text{Fib(1) = 1}$ e $\text{Fib(0) = 0}$, e aplicar repetidamente as transformações simultâneas

Não é difícil mostrar que, após aplicar essa transformação $n$ vezes, $a$ e $b$ serão iguais, respectivamente, a $\text{Fib}(n+1)$ e $\text{Fib}(n)$. Assim, podemos calcular os números de Fibonacci iterativamente usando o procedimento

(define (fib n) 
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))
        

Este segundo método para calcular $\text{Fib}(n)$ é uma iteração linear. A diferença no número de passos necessários pelos dois métodos—um linear em $n$, outro crescendo tão rápido quanto $\text{Fib}(n)$ —é enorme, mesmo para entradas pequenas.

Não se deve concluir disso que os processos recursivos em árvore são inúteis. Quando consideramos processos que operam em dados hierarquicamente estruturados em vez de números, descobrimos que a recursão em árvore é uma ferramenta natural e poderosa.³² Mas mesmo em operações numéricas, os processos recursivos em árvore podem ser úteis para nos ajudar a entender e projetar programas. Por exemplo, embora o primeiro procedimento fib seja muito menos eficiente que o segundo, ele é mais direto, sendo pouco mais do que uma tradução para Lisp da definição da sequência de Fibonacci. Para formular o algoritmo iterativo, foi necessário perceber que a computação poderia ser reformulada como uma iteração com três variáveis de estado.

Exemplo: Contando troco

É preciso apenas um pouco de engenhosidade para chegar ao algoritmo iterativo de Fibonacci. Em contraste, considere o seguinte problema: De quantas maneiras diferentes podemos fazer o troco de $1,00, usando meio-dólar, quartos, moedas de dez centavos, moedas de cinco centavos e moedas de um centavo? Mais geralmente, podemos escrever um procedimento para calcular o número de maneiras de trocar qualquer quantia de dinheiro?

Esse problema tem uma solução simples como um procedimento recursivo. Suponha que pensemos nos tipos de moedas disponíveis como dispostos em alguma ordem. Então, a seguinte relação é válida:

O número de maneiras de trocar a quantia $a$ usando $n$ tipos de moedas é igual a

• o número de maneiras de trocar a quantia $a$ usando todos, exceto o primeiro tipo de moeda, mais
• o número de maneiras de trocar a quantia $a-d$ usando todos os $n$ tipos de moedas, onde $d$ é a denominação do primeiro tipo de moeda.

Para ver por que isso é verdade, observe que as maneiras de fazer o troco podem ser divididas em dois grupos: aquelas que não usam nenhuma moeda do primeiro tipo e aquelas que usam. Portanto, o número total de maneiras de fazer o troco para uma quantia é igual ao número de maneiras de fazer o troco sem usar nenhuma moeda do primeiro tipo, mais o número de maneiras de fazer o troco assumindo que usamos uma moeda do primeiro tipo. Mas este último número é igual ao número de maneiras de fazer o troco para a quantia que resta após usar uma moeda do primeiro tipo.

Assim, podemos reduzir recursivamente o problema de trocar uma quantia dada ao problema de trocar quantias menores usando menos tipos de moedas. Considere essa regra de redução cuidadosamente e convença-se de que podemos usá-la para descrever um algoritmo se especificarmos os seguintes casos degenerados:³³

• Se $a$ for exatamente 0, devemos contar isso como 1 maneira de fazer o troco.
• Se $a$ for menor que 0, devemos contar isso como 0 maneiras de fazer o troco.
• Se $n$ for 0, devemos contar isso como 0 maneiras de fazer o troco.

Podemos facilmente traduzir essa descrição em um procedimento recursivo:

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) 
             (= kinds-of-coins 0)) 
         0)
        (else 
         (+ (cc amount (- kinds-of-coins 1))
            (cc (- amount (first-denomination 
                           kinds-of-coins))
                kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))
        

(O procedimento first-denomination recebe como entrada o número de tipos de moedas disponíveis e retorna a denominação do primeiro tipo. Aqui estamos pensando nas moedas como dispostas em ordem do maior para o menor, mas qualquer ordem serviria.) Podemos agora responder à nossa pergunta original sobre trocar um dólar:

(count-change 100)
292
        

Count-change gera um processo recursivo em árvore com redundâncias semelhantes às da nossa primeira implementação de fib. (Vai demorar bastante para que 292 seja computado.) Por outro lado, não é óbvio como projetar um algoritmo melhor para computar o resultado, e deixamos esse problema como um desafio. A observação de que um processo recursivo em árvore pode ser altamente ineficiente, mas muitas vezes fácil de especificar e entender, levou as pessoas a propor que se poderia obter o melhor dos dois mundos projetando um "compilador inteligente" que pudesse transformar procedimentos recursivos em árvore em procedimentos mais eficientes que computam o mesmo resultado.³⁴

Exercício 1.11: Uma função $f$ é definida pela regra que $f(n)=n$ se $n<3$ e $f(n)=f(n-1)+2f(n-2)+3f(n-3)$ se $n\ge 3$. Escreva um procedimento que computa $f$ por meio de um processo recursivo. Escreva um procedimento que computa $f$ por meio de um processo iterativo.

Exercício 1.12: O seguinte padrão de números é chamado Triângulo de Pascal.

         1
       1   1
     1   2   1
   1   3   3   1
 1   4   6   4   1
       . . .

Os números nas bordas do triângulo são todos 1, e cada número dentro do triângulo é a soma dos dois números acima dele.³⁵ Escreva um procedimento que computa elementos do Triângulo de Pascal por meio de um processo recursivo.

Exercício 1.13: Prove que $\text{Fib}(n)$ é o inteiro mais próximo de ${\phi }^n/\sqrt{5}$, onde $\phi =(1+\sqrt{5})/2$. Dica: Seja $\psi =(1-\sqrt{5})/2$. Use indução e a definição dos números de Fibonacci (veja 1.2.2) para provar que $\text{Fib}(n)=({\phi }^n-{\psi }^n)/\sqrt{5}$.

1.2.3Ordens de Crescimento

Os exemplos anteriores ilustram que os processos podem diferir consideravelmente nas taxas em que consomem recursos computacionais. Uma maneira conveniente de descrever essa diferença é usar a noção de ordem de crescimento para obter uma medida grosseira dos recursos necessários para um processo à medida que as entradas aumentam.

Seja $n$ um parâmetro que mede o tamanho do problema, e seja $R(n)$ a quantidade de recursos que o processo requer para um problema de tamanho $n$. Em nossos exemplos anteriores, tomamos $n$ como o número para o qual uma determinada função deve ser calculada, mas há outras possibilidades. Por exemplo, se nosso objetivo é calcular uma aproximação para a raiz quadrada de um número, podemos tomar $n$ como o número de dígitos de precisão necessários. Para a multiplicação de matrizes, podemos tomar $n$ como o número de linhas nas matrizes. Em geral, há várias propriedades do problema em relação às quais será desejável analisar um determinado processo. Da mesma forma, $R(n)$ pode medir o número de registros de armazenamento interno usados, o número de operações elementares da máquina realizadas, e assim por diante. Em computadores que realizam apenas um número fixo de operações por vez, o tempo necessário será proporcional ao número de operações elementares da máquina realizadas.

Dizemos que $R(n)$ tem ordem de crescimento $\mathrm{\Theta <!--\; \Theta \; -->}(f(n))$, escrito $R(n)=\mathrm{\Theta <!--\; \Theta \; -->}(f(n))$ (pronunciado “teta de $f(n)$”), se existirem constantes positivas $k_1$ e $k_2$ independentes de $n$ tais que $k_{1}f(n)\le <!--\; \le \; -->R(n)\le <!--\; \le \; -->k_{2}f(n)$ para qualquer valor suficientemente grande de $n$. (Em outras palavras, para valores grandes de $n$, o valor $R(n)$ está "sanduichado" entre $k_{1}f(n)$ e $k_{2}f(n)$.)

Por exemplo, com o processo recursivo linear para calcular o fatorial descrito em 1.2.1, o número de passos cresce proporcionalmente à entrada $n$. Assim, os passos necessários para esse processo crescem como $\mathrm{\Theta <!--\; \Theta \; -->}(n)$. Também vimos que o espaço necessário cresce como $\mathrm{\Theta <!--\; \Theta \; -->}(n)$. Para o fatorial iterativo, o número de passos ainda é $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ mas o espaço é $\mathrm{\Theta <!--\; \Theta \; -->}(1)$—ou seja, constante.³⁶ A computação recursiva em árvore de Fibonacci requer $\mathrm{\Theta <!--\; \Theta \; -->}({\mathrm{\phi <!--\; \phi \; -->}}^n)$ passos e espaço $\mathrm{\Theta <!--\; \Theta \; -->}(n)$, onde $\mathrm{\phi <!--\; \phi \; -->}$ é a razão áurea descrita em 1.2.2.

As ordens de crescimento fornecem apenas uma descrição grosseira do comportamento de um processo. Por exemplo, um processo que requer $n^2$ passos e um processo que requer $1000n^2$ passos e um processo que requer $3n^2+10n+17$ passos todos têm $\mathrm{\Theta <!--\; \Theta \; -->}(n^2)$ como ordem de crescimento. Por outro lado, a ordem de crescimento fornece uma indicação útil de como podemos esperar que o comportamento do processo mude à medida que alteramos o tamanho do problema. Para um processo $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ (linear), dobrar o tamanho do problema aproximadamente dobrará a quantidade de recursos usados. Para um processo exponencial, cada incremento no tamanho do problema multiplicará a utilização de recursos por um fator constante. No restante de 1.2, examinaremos dois algoritmos cuja ordem de crescimento é logarítmica, de modo que dobrar o tamanho do problema aumenta a necessidade de recursos por uma quantidade constante.

Exercício 1.14: Desenhe a árvore que ilustra o processo gerado pelo procedimento count-change de 1.2.2 ao fazer o troco para 11 centavos. Quais são as ordens de crescimento do espaço e do número de passos usados por esse processo à medida que a quantidade a ser trocada aumenta?

Exercício 1.15: O seno de um ângulo (especificado em radianos) pode ser calculado usando a aproximação $\sin <!--\; \; -->x\approx <!--\; \approx \; -->x$ se $x$ for suficientemente pequeno, e a identidade trigonométrica $$\sin <!--\; \; -->x=3\sin <!--\; \; -->\frac{x}{3}-<!--\; -\; -->4{\sin }^3<!--\; \; -->\frac{x}{3}$$ para reduzir o tamanho do argumento de sin. (Para os propósitos deste exercício, um ângulo é considerado “suficientemente pequeno” se sua magnitude não for maior que 0,1 radianos.) Essas ideias são incorporadas nos seguintes procedimentos:

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

1. Quantas vezes o procedimento p é aplicado quando (sine 12.15) é avaliado?
2. Qual é a ordem de crescimento em espaço e número de passos (como uma função de $a$) usados pelo processo gerado pelo procedimento sine quando (sine a) é avaliado?

1.2.4Exponenciação

Considere o problema de calcular a exponencial de um número dado. Gostaríamos de um procedimento que receba como argumentos uma base $b$ e um expoente inteiro positivo $n$ e calcule $b^n$. Uma maneira de fazer isso é via a definição recursiva $$\begin{array}{l}{b}^n=b\cdot <!--\; \cdot \; -->b^{n-<!--\; -\; -->1},\\ b^0=1,\end{array}$$ que se traduz facilmente no procedimento

(define (expt b n)
  (if (= n 0) 
      1 
      (* b (expt b (- n 1)))))
              

Este é um processo recursivo linear, que requer $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ passos e $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ espaço. Assim como com o fatorial, podemos facilmente formular uma iteração linear equivalente:

(define (expt b n) 
  (expt-iter b n 1))
  
(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product))))
              

Esta versão requer $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ passos e $\mathrm{\Theta <!--\; \Theta \; -->}(1)$ espaço.

Podemos calcular exponenciais em menos passos usando quadrados sucessivos. Por exemplo, em vez de calcular $b^8$ como $$b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->b)))))),$$ podemos calculá-lo usando três multiplicações: $$\begin{array}{l}{b}^2=b\cdot <!--\; \cdot \; -->b,\\ b^4=b^2\cdot <!--\; \cdot \; -->b^2,\\ b^8=b^4\cdot <!--\; \cdot \; -->b^4.\end{array}$$ Este método funciona bem para expoentes que são potências de 2. Também podemos aproveitar os quadrados sucessivos para calcular exponenciais em geral, se usarmos a regra $$\begin{array}{ll}{b}^n=(b^{n/2}{)}^2& \text{se}n\text{for par},\\ b^n=b\cdot <!--\; \cdot \; -->b^{n-<!--\; -\; -->1}& \text{se}n\text{for ímpar}.\end{array}$$ Podemos expressar esse método como um procedimento:

(define (fast-expt b n)
  (cond ((= n 0) 
          1)
        ((even? n) 
          (square (fast-expt b (/ n 2))))
        (else 
          (* b (fast-expt b (- n 1))))))
              

onde o predicado para testar se um inteiro é par é definido em termos do procedimento primitivo remainder por

(define (even? n)
  (= (remainder n 2) 0))
              

O processo evoluído por fast-expt cresce logaritmicamente com $n$ tanto em espaço quanto em número de passos. Para ver isso, observe que calcular $b^{2n}$ usando fast-expt requer apenas uma multiplicação a mais do que calcular $b^n$. O tamanho do expoente que podemos calcular, portanto, dobra (aproximadamente) a cada nova multiplicação permitida. Assim, o número de multiplicações necessárias para um expoente de $n$ cresce aproximadamente tão rápido quanto o logaritmo de $n$ na base 2. O processo tem $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ de crescimento.³⁷

A diferença entre $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ de crescimento e $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ de crescimento torna-se impressionante à medida que $n$ aumenta. Por exemplo, fast-expt para $n$ = 1000 requer apenas 14 multiplicações.³⁸ Também é possível usar a ideia de quadrados sucessivos para criar um algoritmo iterativo que calcula exponenciais com um número logarítmico de passos (veja Exercício 1.16), embora, como é comum com algoritmos iterativos, isso não seja tão direto quanto o algoritmo recursivo.³⁹

Exercício 1.16: Projete um procedimento que evolua um processo de exponenciação iterativa que use quadrados sucessivos e um número logarítmico de passos, como o fast-expt. (Dica: Usando a observação de que $(b^{n/2}{)}^2=(b^2{)}^{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 forma que o produto $a{b}^n$ permaneça inalterado de estado para estado. No início do processo, $a$ é tomado como 1, e a resposta é dada pelo valor de $a$ no final do processo. Em geral, a técnica de definir uma quantidade invariante que permanece inalterada de estado para estado é uma maneira poderosa de pensar sobre o projeto de algoritmos iterativos.)

Exercício 1.17: Os algoritmos de exponenciação nesta seção são baseados na realização de exponenciação por meio de multiplicação repetida. De maneira semelhante, pode-se realizar a multiplicação de inteiros por meio de adição repetida. O seguinte procedimento de multiplicação (no qual se assume que nossa linguagem só pode somar, não multiplicar) é análogo ao procedimento expt:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))
                

Este algoritmo leva um número de passos que é linear em b. Agora suponha que incluamos, junto com a adição, operações double, que dobra um inteiro, e halve, que divide um inteiro (par) por 2. Usando essas operações, projete um procedimento de multiplicação análogo ao fast-expt que use um número logarítmico de passos.

Exercício 1.18: Usando os resultados de Exercício 1.16 e Exercício 1.17, crie um procedimento que gere um processo iterativo para multiplicar dois inteiros em termos de adição, dobra e divisão por dois, e use um número logarítmico de passos.⁴⁰

Exercício 1.19: Existe um algoritmo inteligente para calcular 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 fib-iter de 1.2.2: $a\leftarrow <!--\; \leftarrow \; -->a+b$ e $b\leftarrow <!--\; \leftarrow \; -->a$. Chame essa transformação de $T$, e observe que aplicar $T$ repetidamente $n$ vezes, começando com 1 e 0, produz o par $\text{Fib}(n+1)$ e $\text{Fib}(n)$. Em outras palavras, os números de Fibonacci são produzidos aplicando $T^n$, a $n^{\text{ésima}}$ potência da transformação $T$, começando com o par (1, 0). Agora considere $T$ como o caso especial de $p=0$ e $q=1$ em uma família de transformações $T_{pq}$, onde $T_{pq}$ transforma o par $(a,b)$ de acordo com $a\leftarrow <!--\; \leftarrow \; -->bq+aq+ap$ e $b\leftarrow <!--\; \leftarrow \; -->bp+aq$. Mostre que, se aplicarmos tal transformação $T_{pq}$ duas vezes, o efeito é o mesmo que usar uma única transformação $T_{p^{\prime }{q}^{\prime }}$ da mesma forma, e calcule $p^{\prime }$ e $q^{\prime }$ em termos de $p$ e $q$. Isso nos dá uma maneira explícita de elevar essas transformações ao quadrado, e assim podemos calcular $T^n$ usando quadrados sucessivos, como no procedimento fast-expt. Junte tudo isso para completar o seguinte procedimento, que é executado em um número logarítmico de passos:⁴¹

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) 
          b)
        ((even? count)
          (fib-iter a
                    b
                    ⟨??⟩  ;compute p'
                    ⟨??⟩  ;compute q'
                    (/ count 2)))
        (else 
          (fib-iter (+ (* b q) 
                      (* a q) 
                      (* a p))
                    (+ (* b p) 
                      (* a q))
                    p
                    q
                    (- count 1)))))
                

1.2.5Máximo Divisor Comum

O máximo divisor comum (MDC) de dois inteiros $a$ e $b$ é definido como o maior inteiro que divide ambos $a$ e $b$ sem deixar resto. Por exemplo, o MDC de 16 e 28 é 4. Em Capítulo 2, quando investigarmos como implementar a aritmética de números racionais, precisaremos ser capazes de calcular MDCs para reduzir números racionais à sua forma mais simples. (Para reduzir um número racional à sua forma mais simples, devemos dividir tanto o numerador quanto o denominador pelo seu MDC. Por exemplo, 16/28 reduz-se a 4/7.) Uma maneira de encontrar o MDC de dois inteiros é fatorá-los e procurar por fatores comuns, mas existe um algoritmo famoso que é muito mais eficiente.

A ideia do algoritmo é baseada na observação de que, se $r$ é o resto quando $a$ é dividido por $b$, então os divisores comuns de $a$ e $b$ são exatamente os mesmos que os divisores comuns de $b$ e $r$. Assim, podemos usar a equação

        MDC(a,b) = MDC(b,r)
        

para reduzir sucessivamente o problema de calcular um MDC ao problema de calcular o MDC de pares de inteiros cada vez menores. Por exemplo,

        MDC(206,40) = MDC(40,6)
                    = MDC(6,4)
                    = MDC(4,2)
                    = MDC(2,0) = 2
        

reduz MDC(206, 40) a MDC(2, 0), que é 2. É possível mostrar que, começando com quaisquer dois inteiros positivos e realizando reduções repetidas, sempre se chegará eventualmente a um par onde o segundo número é 0. Então, o MDC é o outro número no par. Esse método para calcular o MDC é conhecido como Algoritmo de Euclides.⁴²

É fácil expressar o Algoritmo de Euclides como um procedimento:

(define (gcd a b)
  (if (= b 0)
    a
    (gcd b (remainder a b))))
              

Isso gera um processo iterativo, cujo número de passos cresce como o logaritmo dos números envolvidos.

O fato de que o número de passos necessários para o Algoritmo de Euclides ter crescimento logarítmico tem uma relação interessante com os números de Fibonacci:

Teorema de Lamé: Se o Algoritmo de Euclides requer $k$ passos para calcular o MDC de algum par, então o menor número no par deve ser maior ou igual ao $k^{\text{ésimo}}$ número de Fibonacci.⁴³

Podemos usar esse teorema para obter uma estimativa da ordem de crescimento do Algoritmo de Euclides. Seja $n$ o menor dos dois números de entrada para o procedimento. Se o processo leva $k$ passos, então devemos ter $n\ge <!--\; \ge \; -->\text{Fib}(k)\approx <!--\; \approx \; -->{\mathrm{\phi <!--\; \phi \; -->}}^k/\sqrt{5}$. Portanto, o número de passos $k$ cresce como o logaritmo (na base $\mathrm{\phi <!--\; \phi \; -->}$) de $n$. Assim, a ordem de crescimento é $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$.

Exercício 1.20: O processo que um procedimento gera é, é claro, dependente das regras usadas pelo interpretador. Como exemplo, considere o procedimento iterativo gcd dado acima. Suponha que interpretássemos esse procedimento usando avaliação de ordem normal, como discutido em 1.1.5. (A regra de avaliação de ordem normal para if é descrita em Exercício 1.5.) Usando o método de substituição (para ordem normal), ilustre o processo gerado na avaliação de (gcd 206 40) e indique as operações remainder que são realmente realizadas. Quantas operações remainder são realmente realizadas na avaliação de ordem normal de (gcd 206 40)? E na avaliação de ordem aplicativa?

1.2.6Exemplo: Teste de Primalidade

Esta seção descreve dois métodos para verificar a primalidade de um inteiro $n$, um com ordem de crescimento $\mathrm{\Theta <!--\; \Theta \; -->}(\sqrt{n})$, e um algoritmo “probabilístico” com ordem de crescimento $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$. Os exercícios no final desta seção sugerem projetos de programação baseados nesses algoritmos.

Buscando por divisores

Desde os tempos antigos, os matemáticos têm sido fascinados por problemas relacionados a números primos, e muitas pessoas trabalharam no problema de determinar maneiras de testar se números são primos. Uma maneira de testar se um número é primo é encontrar os divisores do número. O seguinte programa encontra o menor divisor inteiro (maior que 1) de um número dado $n$. Ele faz isso de maneira direta, testando $n$ para divisibilidade por inteiros sucessivos começando com 2.

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) 
        n)
      ((divides? test-divisor n) 
        test-divisor)
      (else (find-divisor 
              n 
              (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))
              

Podemos testar se um número é primo da seguinte forma: $n$ é primo se e somente se $n$ for seu próprio menor divisor.

(define (prime? n)
  (= n (smallest-divisor n)))
              

O teste final para find-divisor é baseado no fato de que, se $n$ não for primo, ele deve ter um divisor menor ou igual a $\sqrt{n}$.⁴⁴ Isso significa que o algoritmo precisa testar apenas divisores entre 1 e $\sqrt{n}$. Consequentemente, o número de passos necessários para identificar $n$ como primo terá ordem de crescimento $\mathrm{\Theta <!--\; \Theta \; -->}(\sqrt{n})$.

O teste de Fermat

O teste de primalidade com ordem de crescimento $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ é baseado em um resultado da teoria dos números conhecido como o Pequeno Teorema de Fermat.⁴⁵

Pequeno Teorema de Fermat: Se $n$ é um número primo e $a$ é qualquer inteiro positivo menor que $n$, então $a$ elevado à $n^{\text{ésima}}$ potência é congruente a $a$ módulo $n$.

(Dois números são ditos congruentes módulo $n$ se ambos têm o mesmo resto quando divididos por $n$. O resto de um número $a$ quando dividido por $n$ também é referido como o resto de $a$ módulo $n$, ou simplesmente como $a$ módulo $n$.)

Se $n$ não for primo, então, em geral, a maioria dos números $a<n$ não satisfará a relação acima. Isso leva ao seguinte algoritmo para testar primalidade: Dado um número $n$, escolha um número aleatório $a<n$ e calcule o resto de $a^n$ módulo $n$. Se o resultado não for igual a $a$, então $n$ certamente não é primo. Se for $a$, então as chances são boas de que $n$ seja primo. Agora escolha outro número aleatório $a$ e teste-o com o mesmo método. Se ele também satisfizer a equação, então podemos ter ainda mais confiança de que $n$ é primo. Ao tentar mais e mais valores de $a$, podemos aumentar nossa confiança no resultado. Esse algoritmo é conhecido como o teste de Fermat.

Para implementar o teste de Fermat, precisamos de um procedimento que calcule a exponencial de um número módulo outro número:

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
          (remainder 
          (square (expmod base (/ exp 2) m))
          m))
        (else
          (remainder 
          (* base (expmod base (- exp 1) m))
          m))))
              

Isso é muito semelhante ao procedimento fast-expt de 1.2.4. Ele usa quadrados sucessivos, de modo que o número de passos cresce logaritmicamente com o expoente.⁴⁶

O teste de Fermat é realizado escolhendo aleatoriamente um número $a$ entre 1 e $n-<!--\; -\; -->1$ inclusive e verificando se o resto módulo $n$ da $n^{\text{ésima}}$ potência de $a$ é igual a $a$. O número aleatório $a$ é escolhido usando o procedimento random, que assumimos estar incluído como primitivo no Scheme. Random retorna um inteiro não negativo menor que sua entrada inteira. Portanto, para obter um número aleatório entre 1 e $n-<!--\; -\; -->1$, chamamos random com uma entrada de $n-<!--\; -\; -->1$ e adicionamos 1 ao resultado:

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))
              

O seguinte procedimento executa o teste um número determinado de vezes, como especificado por um parâmetro. Seu valor é verdadeiro se o teste for bem-sucedido todas as vezes, e falso caso contrário.

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) 
          (fast-prime? n (- times 1)))
        (else false)))
              

Métodos probabilísticos

O teste de Fermat difere em caráter da maioria dos algoritmos familiares, nos quais se calcula uma resposta que é garantidamente correta. Aqui, a resposta obtida é apenas provavelmente correta. Mais precisamente, se $n$ falhar no teste de Fermat, podemos ter certeza de que $n$ não é primo. Mas o fato de $n$ passar no teste, embora seja uma indicação extremamente forte, ainda não é uma garantia de que $n$ seja primo. O que gostaríamos de dizer é que, para qualquer número $n$, se realizarmos o teste suficientes vezes e descobrirmos que $n$ sempre passa no teste, então a probabilidade de erro em nosso teste de primalidade pode ser tão pequena quanto desejarmos.

Infelizmente, essa afirmação não é totalmente correta. Existem números que enganam o teste de Fermat: números $n$ que não são primos e ainda têm a propriedade de que $a^n$ é congruente a $a$ módulo $n$ para todos os inteiros $a<n$. Tais números são extremamente raros, então o teste de Fermat é bastante confiável na prática.⁴⁷

Existem variações do teste de Fermat que não podem ser enganadas. Nesses testes, assim como no método de Fermat, testa-se a primalidade de um inteiro $n$ escolhendo um inteiro aleatório $a<n$ e verificando alguma condição que depende de $n$ e $a$. (Veja Exercício 1.28 para um exemplo de tal teste.) Por outro lado, em contraste com o teste de Fermat, pode-se provar que, para qualquer $n$, a condição não se mantém para a maioria dos inteiros $a<n$ a menos que $n$ seja primo. Assim, se $n$ passar no teste para alguma escolha aleatória de $a$, as chances são melhores do que 50% de que $n$ seja primo. Se $n$ passar no teste para duas escolhas aleatórias de $a$, as chances são melhores do que 75% de que $n$ seja primo. Ao executar o teste com mais e mais valores escolhidos aleatoriamente de $a$, podemos tornar a probabilidade de erro tão pequena quanto desejarmos.

A existência de testes para os quais se pode provar que a chance de erro se torna arbitrariamente pequena despertou interesse em algoritmos desse tipo, que passaram a ser conhecidos como algoritmos probabilísticos. Há muita atividade de pesquisa nessa área, e algoritmos probabilísticos têm sido aplicados com sucesso em muitos campos.⁴⁸

Exercício 1.21: Use o procedimento smallest-divisor para encontrar o menor divisor de cada um dos seguintes números: 199, 1999, 19999.

Exercício 1.22: A maioria das implementações de Lisp inclui uma primitiva chamada runtime que retorna um inteiro que especifica a quantidade de tempo que o sistema está em execução (medido, por exemplo, em microssegundos). O seguinte procedimento timed-prime-test, quando chamado com um inteiro $n$, imprime $n$ e verifica se $n$ é primo. Se $n$ for primo, o procedimento imprime três asteriscos seguidos pela quantidade de tempo usada para realizar o teste.

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) 
                        start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))
                

Usando esse procedimento, escreva um procedimento search-for-primes que verifique a primalidade de números ímpares consecutivos em um intervalo especificado. Use seu procedimento para encontrar os três menores primos maiores que 1000; maiores que 10.000; maiores que 100.000; maiores que 1.000.000. Observe o tempo necessário para testar cada primo. Como o algoritmo de teste tem ordem de crescimento de $\mathrm{\Theta <!--\; \Theta \; -->}(\sqrt{n})$, você deve esperar que o teste para primos próximos de 10.000 leve cerca de $\sqrt{10}$ vezes mais tempo do que o teste para primos próximos de 1000. Seus dados de tempo confirmam isso? Quão bem os dados para 100.000 e 1.000.000 suportam a previsão de $\mathrm{\Theta <!--\; \Theta \; -->}(\sqrt{n})$ ? Seu resultado é compatível com a noção de que os programas em sua máquina são executados em tempo proporcional ao número de passos necessários para a computação?

Exercício 1.23: O procedimento smallest-divisor mostrado no início desta seção faz muitos testes desnecessários: depois de verificar se o número é divisível por 2, não há sentido em verificar se ele é divisível por qualquer número par maior. Isso sugere que os valores usados para test-divisor não devem ser 2, 3, 4, 5, 6, …, mas sim 2, 3, 5, 7, 9, …. Para implementar essa mudança, defina um procedimento next que retorne 3 se sua entrada for igual a 2 e, caso contrário, retorne sua entrada mais 2. Modifique o procedimento smallest-divisor para usar (next test-divisor) em vez de (+ test-divisor 1). Com timed-prime-test incorporando essa versão modificada de smallest-divisor, execute o teste para cada um dos 12 primos encontrados em Exercício 1.22. Como essa modificação reduz o número de passos de teste pela metade, você deve esperar que ele execute cerca de duas vezes mais rápido. Essa expectativa é confirmada? Se não, qual é a razão observada entre as velocidades dos dois algoritmos, e como você explica o fato de que ela é diferente de 2?

Exercício 1.24: Modifique o procedimento timed-prime-test de Exercício 1.22 para usar fast-prime? (o método de Fermat) e teste cada um dos 12 primos que você encontrou naquele exercício. Como o teste de Fermat tem ordem de crescimento $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ , como você esperaria que o tempo para testar primos próximos de 1.000.000 se comparasse ao tempo necessário para testar primos próximos de 1000? Seus dados confirmam isso? Você consegue explicar qualquer discrepância que encontrar?

Exercício 1.25: Alyssa P. Hacker reclama que fizemos muito trabalho extra ao escrever expmod. Afinal, ela diz, já sabemos como calcular exponenciais, então poderíamos simplesmente ter escrito

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))
                

Ela está correta? Esse procedimento serviria tão bem para nosso teste de primalidade rápido? Explique.

Exercício 1.26: Louis Reasoner está tendo grande dificuldade em fazer Exercício 1.24. Seu teste fast-prime? parece ser mais lento que o teste prime?. Louis chama sua amiga Eva Lu Ator para ajudar. Quando eles examinam o código de Louis, descobrem que ele reescreveu o procedimento expmod para usar uma multiplicação explícita, em vez de chamar square:

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
          (remainder 
          (* (expmod base (/ exp 2) m)
              (expmod base (/ exp 2) m))
          m))
        (else
          (remainder 
          (* base 
              (expmod base (- exp 1) m))
          m))))
                

“Eu não vejo que diferença isso faz,” diz Louis. “Eu vejo,” diz Eva. “Ao escrever o procedimento dessa forma, você transformou o processo de $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ em um processo de $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ .” Explique.

Exercício 1.27: Demonstre que os números de Carmichael listados em Nota de rodapé 47 realmente enganam o teste de Fermat. Ou seja, escreva um procedimento que receba um inteiro $n$ e teste se $a^n$ é congruente a $a$ módulo $n$ para todo $a<n$, e tente seu procedimento nos números de Carmichael fornecidos.

Exercício 1.28: Uma variante do teste de Fermat que não pode ser enganada é chamada de teste de Miller-Rabin (Miller 1976; Rabin 1980). Ele começa a partir de uma forma alternativa do Pequeno Teorema de Fermat, que afirma que, se $n$ é um número primo e $a$ é qualquer inteiro positivo menor que $n$, então $a$ elevado à $(n-<!--\; -\; -->1)$-ésima potência é congruente a 1 módulo $n$. Para testar a primalidade de um número $n$ pelo teste de Miller-Rabin, escolhemos um número aleatório $a<n$ e elevamos $a$ à $(n-<!--\; -\; -->1)$-ésima potência módulo $n$ usando o procedimento expmod. No entanto, sempre que realizamos o passo de elevar ao quadrado em expmod, verificamos se descobrimos uma “raiz quadrada não trivial de 1 módulo $n$,” ou seja, um número diferente de 1 ou $n-<!--\; -\; -->1$ cujo quadrado é igual a 1 módulo $n$. É possível provar que, se tal raiz quadrada não trivial de 1 existir, então $n$ não é primo. Também é possível provar que, se $n$ for um número ímpar que não é primo, então, para pelo menos metade dos números $a<n$, calcular $a^{n-<!--\; -\; -->1}$ dessa maneira revelará uma raiz quadrada não trivial de 1 módulo $n$. (É por isso que o teste de Miller-Rabin não pode ser enganado.) Modifique o procedimento expmod para sinalizar se ele descobre uma raiz quadrada não trivial de 1, e use isso para implementar o teste de Miller-Rabin com um procedimento análogo a fermat-test. Verifique seu procedimento testando vários primos e não primos conhecidos. Dica: Uma maneira conveniente de fazer expmod sinalizar é fazê-lo retornar 0.

        (define (factorial n)
          (define (iter product counter)
            (if (> counter n)
                product
                (iter (* counter product)
                      (+ counter 1))))
          (iter 1 1))