Square roots by hand (and Newton's method)


Na primária aprendemos a fazer somas, subtrações, multiplicações e divisões; o que nunca nos ensinam é a calcular raízes quadradas. Existe um algoritmo (não muito simples) para calcularmos raízes quadradas à mão, mas muitas vezes uma boa aproximação chega-nos. Acontece também que para o caso das raízes quadradas existe um truque muito simples que pode ser explicado com geometria, e esse truque produz aproximações muito boas! O que veremos mais adiante é que esse truque está relacionado com um método mais geral para resolver equações.

Para explicar o truque vamos aplicá-lo diretamente. Vamos tentar encontrar a raíz quadrada de $7373$. A primeira coisa a fazer é arranjar um palpite. Quanto melhor for o palpite inicial, melhores vão ser as aproximações, mas não é preciso um palpite muito bom para que as aproximações sejam satisfatórias! Sei que $80^2 = 6400$ e $90^2 = 8100$ e $7373$ está mais ou menos no meio, portanto posso tomar $85$ como palpite inicial.
Se quisermos ter esse trabalho, podemos começar por procurar qual o inteiro que melhor aproxima $\sqrt{7373}$. De facto, $$\begin{align}83^2 &= (80 + 3)^2 = 6400 + 480 + 9 = 6889\\ 84^2 &= (80 + 4)^2 = 6400 + 640 + 16 = 7056\\ 85^2 &= (80+5)^2 = 6400 + 800 + 25 = 7225\\ 86^2 &= (80+6)^2 = 6400 + 960 + 36 = 7396\end{align}$$ logo $86$ seria a melhor aproximação inteira. Ainda assim, consideremos $85$ como palpite inicial.
Sabemos que $85$ não é a resposta certa. Na verdade, a resposta certa há de ser $85 + x$, onde $x$ é o que nos falta. Desenhemos então um quadrado de lado $85$ dentro de um quadrado de lado $85 + x$:

Ora temos que $(85+x)^2 = 7373 \iff 85^2 + 2\times85 x + x^2 = 7373$. A parcela $85^2$ corresponde à área do quadrado azul, a parcela $2\times85x$ corresponde às áreas dos rectângulos verdes e $x^2$ corresponde à área do quadrado encarnado. Todas juntas, essas áreas dão $7373$, a área do quadrado grande formado pelos rectângulos e quadrados coloridos.
Uma vez que $85^2 + 2\times85x + x^2 = 7373$ temos $170x + x^2 = 148$. Porque $85$ é uma boa aproximação, a área do quadrado vermelho é muito mais pequena que a área dos rectângulos verdes, logo podemos considerar a aproximação $170x \approx 148 \iff x \approx \frac{148}{170} \approx 0.870588$. Tomando essa aproximação para o valor de $x$ vem que $\sqrt{7373} = 85+x \approx 85.870588$ e na verdade $85.870588^2 \approx 7373.757883$, onde os $0.757883$ em excesso são precisamente a parcela $x^2$ que eu ignorei: $(85+x)^2 = 85^2 + 170x + x^2 = 7373 + x^2 = 7373.757883 \iff x^2 = 0.757883$.
Podemos repetir este raciocínio para obter uma aproximação ainda melhor! Desta vez, o palpite inicial é $85.870588$ e a resposta certa será $85.870588 - y$, onde $y$ representa um ajuste que tem de ser feito. Podemos repetir as contas: $$\begin{align}(85.870588 - y)^2 &= 85.870588^2 - 2\times85.870588y + y^2\\ &\approx 85.870588^2 - 2\times85.870588y \\ &= 7373\end{align}$$ Voltámos a ignorar a parcela com o quadrado do ajuste (neste caso $y^2$) porque o quadrado do ajuste vai ser muito mais pequeno que $2\times85.870588y$ e portanto vem $85.870588^2 - 171.741176y = 7373 \iff y \approx 0.0044284$.
Considerando este novo ajuste obtemos a aproximação $\sqrt{7373} = 85.870588 - y \approx 85.870588 - 0.0044284 = 85.8661596$ e se usarmos uma calculadora temos $\sqrt{7373} = 85.8661749...$, o que quer dizer que já temos $4$ casas decimais certas!

Na janela que segue está um pequeno script em Python que aplica este método sucessivamente até o erro ser menor que $0.0000000001 = 10^{-10}$. À frente de $t$ pomos o valor para o qual queremos calcular a raíz quadrada e à frente de $a$ pomos o nosso primeiro palpite. O script vai apresentar a lista de aproximações, juntamente com os seus quadrados, e no fim mostra a nossa aproximação lado a lado com a raíz calculada diretamente, para vermos quantas casas decimais acertámos.



Falta-me relacionar este pequeno truque para raízes quadradas com o método de Newton! Suponhamos que $f(x)$ é uma função bem comportada e que queremos encontrar um zero desta função, i.e. um ponto $z$ tal que $f(z) = 0$. Suponhamos ainda que $a$ é uma boa aproximação de $z$, e portanto $a + \epsilon = z$. Ora $$\begin{align}0 = f(z) &= f(a + \epsilon) \\ &= f(a) + \epsilon f'(a) + \frac{\epsilon^2}{2}f''(\xi)\end{align}$$ pela série de Taylor de $f$. Como $a$ é uma boa aproximação, $\epsilon$ é um valor pequeno e portanto a última parcela, com $\epsilon^2$, é muito pequena; se a ignorarmos ficamos com a aproximação $$0 \approx f(a) + \epsilon f'(a) \iff \epsilon \approx -\frac{f(a)}{f'(a)}$$ Tendo calculado $\epsilon$ podemos calcular um novo palpite $b$, com $$b = a + \epsilon = a - \frac{f(a)}{f'(a)}$$ E podemos repetir este processo. Se eu chamar $a_1$ à primeira aproximação, escrevo $$a_1 = a - \frac{f(a)}{f'(a)}$$ e repetindo as contas acima, considerando que $z = a_1 + \epsilon$, posso chamar $a_2$ a uma segunda aproximação $$a_2 = a_1 - \frac{f(a_1)}{f'(a_1)}$$ e assim sucessivamente, escrevendo sempre $$a_{n+1} = a_n - \frac{f(a_n)}{f'(a_n)}$$ Este método iterativo, chamado método de Newton, não funciona sempre e para qualquer $f$; há que verificar certas condições (por exemplo, parece seguro assumir que pelo menos as duas primeiras derivadas têm de existir, já que derivámos o método através da expansão de Taylor de grau $2$). No entanto, para $c > 0$, posso definir $f(x) = x^2 - c$ (e portanto $f'(x) = 2x$) e neste caso, o zero que estamos à procura é $f(z) = 0 \iff z = \pm\sqrt{c}$. Isto quer dizer que posso aplicar o método de Newton à função $f(x) = x^2 - 7373$ para aproximar a raíz quadrada de $7373$. Em geral, para um $c$ positivo e para um palpite inicial decente, este método funciona sempre: basta pensar na interpretação geométrica dada acima.

Fica à discrição do leitor, mais desconfiado ou meticuloso, verificar que aplicar o método de Newton à função $f(x) = x^2 - 7373$ com palpite inicial $a = 85$ corresponde às contas que fizémos em cima.

Partilhem a vossa opinião na secção de comentários em baixo!
In elementary school they teach us how to sum, subtract, multiply and divide; what they never teach us is how to compute square roots. There is a method (which is not trivial) to compute square roots by hand, but the majority of times a good approximation is all we need. It just so happens that there is a nice geometrical trick that allows one to find really good approximations to square roots. By the end of the post I will also hint at how that trick is related to a more general method to solve equations.

To explain the trick we will apply it directly. Let us try to find the square root of $7373$. The first thing to do is find a good guess. The better the initial guess is, the better the successive approximations will be, but you don't need a really good first guess to produce really decent approximations! I know that $80^2 = 6400$ and $90^2 = 8100$. $7373$ seems to be somewhere in between, so I will take $85$ as my initial guess.
If we want, we can take as initial guess the integer that, when squared, is closer to $7373$. As a matter of fact, $$\begin{align}83^2 &= (80 + 3)^2 = 6400 + 480 + 9 = 6889\\ 84^2 &= (80 + 4)^2 = 6400 + 640 + 16 = 7056\\ 85^2 &= (80+5)^2 = 6400 + 800 + 25 = 7225\\ 86^2 &= (80+6)^2 = 6400 + 960 + 36 = 7396\end{align}$$ therefore $86$ is the integer whose square is closer to $7373$. Nevertheless, let us start with $85$.
We know $85$ isn't the right answer. Actually, the right answer (the square root of $7373$) will be $85 + x$, where $x$ is the bit we are missing. Let us draw a square of side $85$ inside a square of side $85+x$:

We have $(85+x)^2 = 7373 \iff 85^2 + 2\times 85x + x^2 = 7373$. The term $85^2$ corresponds to the area of the blue square, the term $2\times 85x$ to the areas of the green rectangles and $x^2$ to the area of the red square. If we put them all together, those areas sum up to $7373$, the area of the big square formed by the smaller squares and rectangles.
Simplifying $85^2 + 2\times 85x + x^2 = 7373$ we get $170x + x^2 = 148$. Because $85$ was a good first guess, the area of the red square is much smaller than that of the green rectangles, thus we can consider that between the two terms $170x$ and $x^2$, the $170x$ contributes the most to the total of $148$, hence $170x \approx 148 \iff x \approx \frac{148}{170}\approx 0.870588$. If we take that value to be approximately $x$, then $\sqrt{7373} = 85 + x \approx 85.870588$ and actually $85.870588^2 \approx 7373.757883$, where the $0.757883$ in excess come from the $x^2$ we ignored: $(85+x)^2 = 85^2 + 170x + x^2 = 7373 + x^2 = 7373.757883 \iff x^2 = 0.757883$.
We can repeat this whole train of thought to get an even better approximation! This time, the initial guess is $85.870588$ and the actual square root is going to be $85.870588 - y$, where $y$ represents an adjustment to be made. If we repeat the maths: $$\begin{align}(85.870588 - y)^2 &= 85.870588^2 - 2\times85.870588y + y^2\\ &\approx 85.870588^2 - 2\times85.870588y \\ &= 7373\end{align}$$ This time we ignored the $y^2$ which will still represent a small square with negligible area when compared to the $2\times85.870588y$. From this we get $85.870588^2 - 171.741176y = 7373 \iff y \approx 0.0044284$.
Taking this approximate value for $y$ we get $\sqrt{7373} = 85.870588 - y \approx 85.870588 - 0.0044284 = 85.8661596$ and making use of a calculator we see that $\sqrt{7373} = 85.8661749...$, which means we already have $4$ decimal places correct!

The small window below contains a small Python script that applies this method successively until the error is smaller than $0.0000000001 = 10^{-10}$. $t$ holds the number whose square root we want and $a$ holds the value of our first guess. The script will present the list of successive guesses, along with their squares, and in the end shows our final approximation side by side with the actual square root, so we can compare the two.



All that is left for this post is to relate this method to approximate square roots with Newton's method! Suppose $f(x)$ is a well-behaved function and that we want to find a root of this function, i.e. a point $z$ such that $f(z) = 0$. Suppose as well that $a$ is a good approximation of $z$, and thus $a + \epsilon = z$. We have $$\begin{align}0 = f(z) &= f(a + \epsilon) \\ &= f(a) + \epsilon f'(a) + \frac{\epsilon^2}{2}f''(\xi)\end{align}$$ because of the Taylor expansion of $f$. Because $a$ is a good approximation, $\epsilon$ is very small and thus the term with $\epsilon^2$ is very small; if we ignore it we get $$0 \approx f(a) + \epsilon f'(a) \iff \epsilon \approx -\frac{f(a)}{f'(a)}$$ Having found an approximation for $\epsilon$ we can refine the approximation $a$ with a new approximation for $z$: $$b = a + \epsilon = a - \frac{f(a)}{f'(a)}$$ And we can repeat this process. If $a_1$ is the first approximation I can write $$a_1 = a - \frac{f(a)}{f'(a)}$$ and if we repeat the maths above, remembering that $z = a_1 + \epsilon$, I can let $a_2$ be the second approximation with $$a_2 = a_1 - \frac{f(a_1)}{f'(a_1)}$$ and so on and so forth, giving a succession $$a_{n+1} = a_n - \frac{f(a_n)}{f'(a_n)}$$ This iterative method, called Newton's method, doesn't work all the time for any $f$; certain conditions must be met (for example, it seems reasonable to assume that $f$ must have the first two derivatives, given that we derived the method with a Taylor series of order $2$). Even so, for $c > 0$, we can define $f(x) = x^2 - c$ (thus $f'(x) = 2x$) and in this case, the root we are looking for is $f(z) = 0 \iff z = \pm \sqrt{c}$. This means we can apply Newton's method to the function $f(x) = x^2 - 7373$ to find the square root of $7373$. In general, for $c > 0$ and a decent first guess, this method will always work: just consider the geometrical interpretation given above.

We let the more meticulous reader verify that applying Newton's method to the function $f(x) = x^2 - 7373$ with initial guess $a = 85$ corresponds to the maths we did above.

Please leave your thoughts in the comment section below!

  - RGS

Popular posts from this blog

Tutorial on programming a memory card game

Pocket maths: how to compute averages in your head

Markov Decision Processes 02: how the discount factor works