1.1.7 Exemplo: Raiz Quadrada pelo Método de Newton

Funções, como introduzidas acima, são muito parecidas com funções matemáticas ordinárias. Elas especificam um valor que é determinado por um ou mais parâmetros. Mas há uma diferença importante entre funções matemáticas e funções de computador. Funções de computador devem ser efetivas.

Como exemplo, considere o problema de calcular raízes quadradas. Podemos definir a função raiz quadrada como:

$$\sqrt{x}\ =\text{ o }y\text{ tal que }y \geq 0\text{ e } y^2\ =\ x$$

Isso descreve uma função matemática perfeitamente legítima. Poderíamos usá-la para reconhecer se um número é a raiz quadrada de outro, ou para derivar fatos sobre raízes quadradas em geral. Por outro lado, a definição não descreve uma função de computador. De fato, ela nos diz quase nada sobre como realmente encontrar a raiz quadrada de um número dado. Não ajudará reformular esta definição em pseudo-JavaScript:

function sqrt(x) {
    return the y with y >= 0 && square(y) === x;
}

Isso apenas evita a questão.

O contraste entre função matemática e função de computador é um reflexo da distinção geral entre descrever propriedades das coisas e descrever como fazer as coisas, ou, como às vezes é referido, a distinção entre conhecimento declarativo e conhecimento imperativo. Em matemática, geralmente estamos preocupados com descrições declarativas (o que é), enquanto em ciência da computação geralmente estamos preocupados com descrições imperativas (como fazer).¹

Como se calcula raízes quadradas? A maneira mais comum é usar o método de Newton de aproximações sucessivas, que diz que sempre que temos um palpite y para o valor da raiz quadrada de um número x, podemos realizar uma manipulação simples para obter um palpite melhor (mais próximo da raiz quadrada real) fazendo a média de y com x/y.² Por exemplo, podemos calcular a raiz quadrada de 2 da seguinte forma. Suponha que nosso palpite inicial seja 1:

$$\begin{array}{lll} \textrm{Palpite} & \textrm{Quociente} & \textrm{Média}\\[1em] 1 & {\displaystyle \frac{2}{1} = 2} & {\displaystyle \frac{(2+1)}{2} = 1.5} \\[1em] 1.5 & {\displaystyle \frac{2}{1.5} = 1.3333} & {\displaystyle \frac{(1.3333+1.5)}{2} = 1.4167} \\[1em] 1.4167 & {\displaystyle \frac{2}{1.4167} = 1.4118} & {\displaystyle \frac{(1.4167+1.4118)}{2} = 1.4142} \\[1em] 1.4142 & \ldots & \ldots \end{array}$$

Continuando este processo, obtemos aproximações cada vez melhores da raiz quadrada.

Agora vamos formalizar o processo em termos de funções. Começamos com um valor para o radicando (o número cuja raiz quadrada estamos tentando calcular) e um valor para o palpite. Se o palpite é bom o suficiente para nossos propósitos, terminamos; se não, devemos repetir o processo com um palpite melhorado. Escrevemos esta estratégia básica como uma função:

Carregando playground de código...

Um palpite é melhorado fazendo a média dele com o quociente do radicando e o palpite antigo:

Carregando playground de código...

onde

Carregando playground de código...

Também temos que dizer o que queremos dizer com "bom o suficiente". O seguinte servirá para ilustração, mas não é realmente um teste muito bom. (Veja o exercício 1.7.) A ideia é melhorar a resposta até que ela esteja próxima o suficiente de modo que seu quadrado difira do radicando por menos do que uma tolerância predeterminada (aqui 0.001):³

Carregando playground de código...

Finalmente, precisamos de uma maneira de começar. Por exemplo, podemos sempre supor que a raiz quadrada de qualquer número é 1:

Carregando playground de código...

Se digitarmos essas declarações no interpretador, podemos usar sqrt assim como podemos usar qualquer função:

Carregando playground de código...

3.00009155413138

Carregando playground de código...

11.704699917758145

Carregando playground de código...

1.7739279023207892

Carregando playground de código...

1000.000369924366

O programa sqrt também ilustra que a linguagem funcional simples que introduzimos até agora é suficiente para escrever qualquer programa puramente numérico que se poderia escrever em, digamos, C ou Pascal. Isso pode parecer surpreendente, já que não incluímos em nossa linguagem nenhum construto iterativo (de loop) que direcione o computador a fazer algo repetidamente. A função sqrt_iter, por outro lado, demonstra como a iteração pode ser realizada sem usar nenhum construto especial além da capacidade ordinária de chamar uma função.⁴

---

Exercícios

Exercício 1.6

Alyssa P. Hacker não gosta da sintaxe de expressões condicionais, envolvendo os caracteres ? e :. "Por que não posso simplesmente declarar uma função condicional ordinária cuja aplicação funciona como expressões condicionais?" ela pergunta.⁵ A amiga de Alyssa, Eva Lu Ator, afirma que isso pode de fato ser feito, e ela declara uma função conditional da seguinte forma:

Carregando playground de código...

Eva demonstra o programa para Alyssa:

Carregando playground de código...

5

Carregando playground de código...

0

Encantada, Alyssa usa conditional para reescrever o programa de raiz quadrada:

Carregando playground de código...

O que acontece quando Alyssa tenta usar isso para calcular raízes quadradas? Explique.

Resposta: Qualquer chamada de sqrt_iter leva imediatamente a um loop infinito. A razão para isso é nossa avaliação de ordem aplicativa. A avaliação da expressão de retorno de sqrt_iter precisa avaliar seus argumentos primeiro, incluindo a chamada recursiva de sqrt_iter, independentemente de o predicado avaliar para verdadeiro ou falso. O mesmo acontece com a chamada recursiva, e assim a função conditional nunca é realmente aplicada.

Exercício 1.7

O teste is_good_enough usado no cálculo de raízes quadradas não será muito eficaz para encontrar as raízes quadradas de números muito pequenos. Além disso, em computadores reais, operações aritméticas são quase sempre realizadas com precisão limitada. Isso torna nosso teste inadequado para números muito grandes. Explique essas afirmações, com exemplos mostrando como o teste falha para números pequenos e grandes. Uma estratégia alternativa para implementar is_good_enough é observar como guess muda de uma iteração para a próxima e parar quando a mudança for uma fração muito pequena do palpite. Projete uma função de raiz quadrada que usa esse tipo de teste final. Isso funciona melhor para números pequenos e grandes?

Resposta: A tolerância absoluta de 0.001 é muito grande ao calcular a raiz quadrada de um valor pequeno. Por exemplo, sqrt(0.0001) resulta em 0.03230844833048122 em vez do valor esperado 0.01, um erro de mais de 200%.

Por outro lado, para valores muito grandes, erros de arredondamento podem fazer com que o algoritmo nunca chegue próximo o suficiente da raiz quadrada, caso em que não terminará.

O programa a seguir alivia o problema substituindo uma tolerância absoluta por uma tolerância relativa:

Carregando playground de código...

Exercício 1.8

O método de Newton para raízes cúbicas é baseado no fato de que se y é uma aproximação para a raiz cúbica de x, então uma aproximação melhor é dada pelo valor:

$$\dfrac{x/y^{2}+2y}{3}$$

Use esta fórmula para implementar uma função de raiz cúbica análoga à função de raiz quadrada. (Na seção 1.3.4 veremos como implementar o método de Newton em geral como uma abstração dessas funções de raiz quadrada e raiz cúbica.)

Resposta:

Carregando playground de código...

---

[1] Descrições declarativas e imperativas estão intimamente relacionadas, como de fato estão a matemática e a ciência da computação. Por exemplo, dizer que a resposta produzida por um programa é "correta" é fazer uma declaração declarativa sobre o programa. Há uma grande quantidade de pesquisa voltada para estabelecer técnicas para provar que programas estão corretos, e muito da dificuldade técnica deste assunto tem a ver com a negociação da transição entre declarações imperativas (das quais os programas são construídos) e declarações declarativas (que podem ser usadas para deduzir coisas). De forma relacionada, designers de linguagens de programação exploraram as chamadas linguagens de muito alto nível, nas quais realmente se programa em termos de declarações declarativas. A ideia é tornar os interpretadores sofisticados o suficiente para que, dado o conhecimento "o que é" especificado pelo programador, eles possam gerar conhecimento "como fazer" automaticamente. Isso não pode ser feito em geral, mas há áreas importantes onde o progresso foi feito. Revisitaremos esta ideia no capítulo 4.

[2] Este algoritmo de raiz quadrada é na verdade um caso especial do método de Newton, que é uma técnica geral para encontrar raízes de equações. O próprio algoritmo de raiz quadrada foi desenvolvido por Heron de Alexandria no primeiro século EC. Veremos como expressar o método geral de Newton como uma função JavaScript na seção 1.3.4.

[3] Geralmente daremos nomes de predicados começando com is_, para nos ajudar a lembrar que são predicados.

[4] Leitores que estão preocupados com as questões de eficiência envolvidas no uso de chamadas de função para implementar iteração devem observar as observações sobre "recursão de cauda" na seção 1.2.1.

[5] Como uma hacker de Lisp do original Structure and Interpretation of Computer Programs, Alyssa prefere uma sintaxe mais simples e uniforme.

📝 Encontrou algo errado nesta página?

Sua ajuda é muito importante para melhorar a qualidade da tradução!

🐛 Encontrou um erro?

Se você encontrou:

• Erro de tradução (palavra incorreta, termo técnico errado)
• Erro de ortografia ou gramática
• Link quebrado
• Código de exemplo que não funciona
• Problema de formatação

Reporte um bug →

❓ Tem uma dúvida?

Se você tem:

• Dúvida sobre o conteúdo desta seção
• Pergunta sobre um conceito do SICP
• Dificuldade em entender algum exemplo
• Questão sobre a tradução de algum termo

Inicie uma discussão →

💡 Tem uma sugestão de melhoria?

Se você quer sugerir:

• Melhoria na explicação
• Exemplo adicional
• Recurso visual (diagrama, ilustração)
• Qualquer outra ideia

Sugira uma melhoria →

🌍 Quer discutir a tradução?

Se você quer debater:

• Escolha de tradução de algum termo
• Consistência de terminologia
• Nuances do português

Discussão de tradução →

Obrigado por ajudar a melhorar o SICP.js PT-BR! ✨