LeGauss: Como funciona a sua calculadora?

O objetivo desta exposição é mostrar como funciona o algoritmo mais utilizado em calculadoras científicas para calcular, principalmente, funções trigonométricas.

Introdução

Certamente calculadoras científicas utilizam métodos numéricos (algoritmos que obtêm um valor aproximado) para retornar valores de funções como seno, cosseno, exponencial, etc. Você já parou para se perguntar que métodos são esses?

Se você já fez um curso básico de Cálculo, sei que a primeira coisa que passou pela sua cabeça neste momento foi Série de Taylor. Aproximar usando Taylor é realmente muito simples; por exemplo, a série do seno é

$\sin \theta = \theta -\frac{\theta^3}{3!} + \frac{\theta^5}{5!} - \frac{\theta^7}{7!} + \cdots$

Basta então escolher alguma precisão (em casas decimais, por exemplo) e truncar esta série para obter uma expressão finita. Por exemplo, todos sabemos que, para os nossos professores de física, $\inline \sin \theta = \theta$ , que é uma aproximação em Taylor de ordem 1. Você pode escolher qualquer grau e depois calcular o quão boa é esta aproximação, mas isto não nos interessa no momento.

O fato é que sua calculadora provavelmente não usa aproximação em Taylor! Isto pode parecer, sem dúvida, um tanto estranho. Aproximação em Taylor é simples e converge rapidamente. Além do mais, oferece uma expressão polinomial para qualquer uma destas funções. É difícil conceber algo mais simples.

Porém, temos que pensar que o hardware de uma calculadora é muito limitado. Tão limitado que multiplicar dois números pode se tornar uma operação lenta. De fato, multiplicação é uma operação $\inline O(n^2)$ (veja o post sobre Transformada Rápida de Fourier). Isto leva por água a baixo nossa expressão em Taylor, pois temos de realizar muitas multiplicações.

Antes de mais nada, então, é preciso deixar claro que tipo de operação uma calculadora (e, em geral, um computador qualquer) realiza rapidamente.Lembremos que computadores normalmente trabalham com números binários, então vou pensar em notação binária daqui para frente.

As operações mais rápidas que podem ser feitas num computador são:

Adicionar e subtrair números.
Comparação de números (i.e. decidir se é maior ou menor).
Armazenamento e leitura de números na memória.
Multiplicação por $\inline 2^n$ , $\inline n\in \mathbb{Z}$ . Ex.: $\inline 0.0001011 \times 2^2 = 0.0101100$ .

Num computador com pouca capacidade de processamento, o ideal seria obter um algoritmo que utilizasse apenas estas operações. Mas será que isto é possível?

O algoritmo CORDIC

O objetivo agora é apresentar um algoritmo para calcular funções trigonométricas que se utiliza, majoritariamente, das operações rápidas definidas acima. Na verdade, além das operações rápidas, utilizaremos uma única multiplicação! O preço que pagamos pela eficiência é que este algoritmo não possui um formato tão simples quanto uma aproximação em Taylor.

Em 1959, Jack Volder (não consegui descobrir a profissão dele, mas imagino que seja engenheiro) inventou o algoritmo CORDIC. Esta sigla significa COordinate Rotation DIgital Computer.

Assim como boa parte dos algoritmos numéricos, o CORDIC foi desenvolvido por uma razão muito nobre: fins militares. O objetivo era utilizá-lo no sistema de navegação do bombardeiro B-58 Hustler.

Mas chega de história e falemos, de uma vez por todas, de matemática. O mais interessante é que o algoritmo se utiliza apenas de matemática básica (um pouco de matrizes de rotação é necessário) e é geométrico (no sentido em que é possível visualizar o que está acontecendo)!

Como funciona?

Este é meu testemunho pessoal sobre a dedução do algoritmo. Isto significa que vou tentar explicar as coisas do jeito em que eu acho mais natural. Antes de mais nada, vou tentar passar rapidamente a ideia do algoritmo. Mesmo que não fique muito claro agora, volte aqui depois de ler tudo e as coisas ficarão mais claras.

Passos gerais:

Vamos aproximar $\inline \cos\theta$ e $\inline \sin\theta$ ao mesmo tempo.
Podemos considerar o ponto $\inline (\cos\theta,\sin\theta)$ no círculo unitário.
Objetivo: obter uma sequência de pontos em $\inline \mathbb{R}^2$ convergindo para $\inline (\cos\theta,\sin\theta)$ .
Vamos assumir que todos os pontos desta sequência estão no círculo unitário. Por que? Pois é fácil ``mover'' pontos no círculo unitário.

Como movemos pontos no círculo unitário? Com matrizes de rotação. Precisaremos apenas de rotações no plano $\inline \mathbb{R}^2$ .

Vamos denotar

$\begin{align*} R_{\theta}=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right) \end{align*}$

De acordo com os passos gerais acima, suponhamos que queremos aproximar $\inline (\cos x,\sin x)$ . Vamos começar com um ponto no círculo unitário, digamos $\inline (1,0)$ , e tentar obter uma sequência de ângulos $\inline \theta_1,\theta_2,\ldots,\theta_n$ (positivos ou negativos) de maneira esperta tais que

$\begin{align*} \left(\begin{array}{c} \cos x \\ \sin x \end{array}\right) \approx R_{\theta_n}\cdots R_{\theta_{2}}R_{\theta_1} \left(\begin{array}{c} 1 \\ 0 \end{array}\right) \end{align*}$

Ou seja, vamos movendo (girando) o vetor $\inline (1,0)$ até se aproximar do ponto $\inline (\cos x, \sin x)$ .

Talvez você tenha notado algo muito estranho acontecendo aqui. No início havíamos comentado que multiplicar números é uma tarefa penosa para uma calculadora. No entanto, estamos desenvolvendo um algoritmo que tem que multiplicar matrizes! Isto parece muito pior do que antes.

Nem tudo é o que parece. O segredo agora é realizar uma série de truques espertos de forma que esta multiplicação de matrizes fique muito simples. Para isto, comece observando que podemos fatorar $\inline \cos\theta$ :

$R_{\theta}=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)=\cos\theta \left(\begin{array}{cc} 1 & -\tan \theta \\ \tan \theta & 1 \end{array}\right)$

O objetivo desta fatoração é tentar simplificar a forma da matriz. Agora pense: o que sabemos multiplicar rapidamente? Potências de 2! Nada mais natural do que considerar apenas ângulos $\theta$ de forma que $\tan \theta=2^n$ , $n\in \mathbb{Z}$ (esta é a nossa escolha esperta de ângulos).

Definindo $\theta_n=\arctan 1/2^{n}$ , $n\in \mathbb{N}$ , temos

$\begin{align*} R_{\theta_n}\left(\begin{array}{c} a \\ b \end{array}\right)&=\cos\theta_n \left(\begin{array}{cc} 1 & -\tan \theta_n \\ \tan \theta_n & 1 \end{array}\right)\left(\begin{array}{c} a \\ b \end{array}\right)\\ &= \cos\theta_n \left(\begin{array}{cc} 1 & -1/2^n \\ 1/2^n & 1 \end{array}\right) \left(\begin{array}{c} a \\ b \end{array}\right)\\ &=\cos \theta_n\left(\begin{array}{c} a -b/2^n \\ a/2^n + b \end{array}\right) \end{align*}$

Esquecendo o $\inline \cos \theta_n$ por um momento, observe que estamos realizando apenas operações rápidas para multiplicar $\inline R_{\theta}$ por um vetor.

Para utilizar estes ângulos numa calculadora, devemos calculá-los previamente, de outra maneira. Vejamos alguns valores iniciais.

$\begin{align*} \begin{array}{c c} n & \text{Aproximação de } \theta_n \\ 0 & 0.785398 \text{ rad} \\ 1 & 0.463648 \text{ rad} \\ 2 & 0.244979 \text{ rad}\\ 3 & 0.124355 \text{ rad}\\ 4 & 0.062419 \text{ rad} \end{array} \end{align*}$

Observe que, eventualmente, podemos parar de calcular estes valores pois $\inline \tan \theta \approx \theta$ , para $\inline \theta$ pequeno. Por exemplo, para $\inline n=9$ (isto é, $\inline \theta_n=\arctan 1/512$ ), esta aproximação já tem 8 casas decimais de precisão.

Agora expliquemos com um exemplo como que o algoritmo vai funcionar. Suponha que queremos aproximar $\inline (\cos 1, \sin 1)$ . Vamos aproximar o ângulo $\inline 1 \text{ rad}$ , utilizando nossos $\inline \theta_n$ . Assim, obteremos uma sequência $\inline x_n$ convergindo para $\inline x=1$ :

Começamos tomando

$x_0=\theta_0\approx 0.785398$

Muito pequeno, então somamos:

$x_1=\theta_0+\theta_1\approx 1.249046$

Passou, então subtraímos:

$x_2=\theta_0+\theta_1-\theta_2 \approx 1.004067$

Etc.

Em cada passo, o algoritmo deve verificar se a aproximação obtida é maior ou menor (operação rápida) que o número desejado. Ao mesmo tempo em que aproximamos o ângulo, devemos aproximar o cosseno e o seno. Para isto, vamos multiplicando as matrizes correspondentes.

$\begin{align*} \left(\begin{array}{c} \cos x_2 \\ \sin x_2 \end{array}\right)&= R_{-\theta_2}R_{\theta_1}R_{\theta_0}\left(\begin{array}{c} 1 \\ 0 \end{array}\right) \\ &=c\left(\begin{array}{rr} 1 & \frac{1}{4} \\ -\frac{1}{4}& 1 \end{array}\right)\left(\begin{array}{rr} 1 & -\frac{1}{2} \\ \frac{1}{2}& 1 \end{array}\right) \left(\begin{array}{rr} 1 & -1 \\ 1& 1 \end{array}\right)\left(\begin{array}{c} 1 \\ 0 \end{array}\right) \end{align*}$

onde $\inline c=\cos(-\theta_2)\cos\theta_1\cos \theta_0$ . Fazendo apenas 3 passos, temos $\inline \cos x_2\approx 0.5368$ , $\inline \sin x_2 \approx 0.8436$ . Enquanto que $\inline \cos 1 \approx 0.5403$ e $\inline \sin 1 \approx 0.8414$ .

Então, se o algoritmo rodar $\inline n+1$ passos, teríamos algo do tipo

$\begin{align*} \left(\begin{array}{c} \cos x \\ \sin x \end{array}\right)\approx \left(\begin{array}{c} \cos x_n \\ \sin x_n \end{array}\right) = cR_{\pm\theta_n}\cdots R_{\pm\theta_1}R_{\pm\theta_0}\left(\begin{array}{c} 1 \\ 0 \end{array}\right) \end{align*}$

onde $c_n=\cos \theta_n \cdots \cos \theta_1 \cos \theta_0$ .

Em linhas gerais, este é o algoritmo: aproximar o ângulo

somando ou subtraindo ângulos $\theta_n$ e realizar os produtos das matrizes correspondentes. Mas ainda restaram alguns problemas:

Quem garante que o método sempre converge?
Que critério de parada devemos utilizar?
Como lidar com os ?

Todas estes problemas estão intimamente relacionados. Aqui entra o pulo do gato.

Teorema. Utilizando o método descrito anteriormente, temos que

$\begin{align*} \left\{\begin{array}{l} |\cos x - \cos x_{n+1}|<1/2^{n} \\ |\sin x - \sin x_{n+1}|<1/2^{n} \end{array}\right. \end{align*}$

se $-\pi/2 \le x\le \pi/2$ .

Vamos entender como utilizar o teorema acima para resolver todos os nossos problemas em uma tacada só. O teorema acima nos diz de maneira precisa como estimar o erro das aproximações. Por exemplo, se quisermos uma aproximação com 10 casas decimais, poderíamos tomar n+1=40

e parar de aproximar sempre em n=39

, pois

$\frac{1}{2^{39}}\approx 1.8189 \times 10^{-12}\text{.}$

Esta observação resolve tudo. Se fixarmos que vamos parar sempre em n=39

(para qualquer escolha de ângulo), teremos que $c_{39}=c$ será uma constante (pois cosseno independe do sinal [*]). Utilizando qualquer outro método, calculamos

previamente:

$c=\cos \theta_{39} \cdots \cos \theta_1 \cos \theta_0\approx 0.607252935$

Feito isto, podemos implementar esta constante direto no hardware, sem precisar calculá-la durante o método. Logo a única operação não-rápida que estamos fazendo é uma multiplicação por uma constante no final. Observe que, como os $\theta_n$ também já estão pré-definidos, então podemos também implementá-los direto no hardware.

Em nenhum momento eu demonstrei o teorema. Não irei demonstrar aqui pois a demonstração é um pouco técnica e meio chata. No entanto, se você tiver curiosidade, pode clicar aqui. Nada mais além de um primeiro curso de Cálculo é
necessário para compreender esta demonstração.

Observações finais

O mais impressionante é que este mesmo algoritmo pode ser adaptado para calcular qualquer função de uma calculadora científica comum:

Funções hiperbólicas;
exponencial;
logaritmo;
raízes.

Porém, os detalhes são mais técnicos e algumas adaptações são até proprietárias. Vasculhando no Google é possível achar algumas coisas.

Este é um belo exemplo de como utilizar pouca matemática mas muita criatividade para criar um algoritmo extremamente útil. Vi inicialmente no artigo Alan Sultan, CORDIC: How Hand Calculators Calculate, The College Mathematics Journal (MAA), Vol. 40, no 2, 2009, pg. 87-92. No link da Wikipedia você acha algumas outras informações interessantes.

Até.

Notas:

[*] Isto mostra que devíamos ter fatorado exatamente o cosseno, e não o seno.

P.S. Segundo o Gabriel, este post não deveria se enquadrar na seção de matemática, pois não demonstrei nenhum teorema. Peço desculpa aos matemáticos que leram este post. :)

2 comentários:

Gabriel Martins disse...: Legauss o post
De fato o algoritmo é bem criativo, mas o importante mesmo é que se você somar até o infinito você tem o valor EXATO! huahuauha
=P; 29 de julho de 2011 às 20:11
Pamplonafala disse...: ta desculpado; 11 de maio de 2015 às 16:37

Postar um comentário

sexta-feira, 29 de julho de 2011

Como funciona a sua calculadora?

2 comentários: