Num post anterior mostrei como podemos aproximar a raíz quadrada de um número através de um processo iterativo que começa com um palpite, seguido de vários ajustes. Neste post vou mostrar qual é o algoritmo mencionado pela Mathgurl no vídeo que ela fez em "parceria" comigo.
O método que vou descrever pode ser usado com qualquer número real, seja quadrado perfeito ou não, seja inteiro ou não, racional ou não. Vou começar por apresentar um raciocínio que mostra como o algoritmo surge. Para quem não estiver interessado, pode saltar diretamente para a explicação final de como funciona.
Para a exposição que se segue, se $a,b$ forem dígitos, então a notação $ab$ representa o número $10a + b$ em vez do número $a\times b$. Começamos por notar que, se quisermos descobrir $\sqrt{N}$ à mão e $\sqrt{N}$ for irracional, então vamos ter de nos contentar com uma aproximação com um número finito de casas decimais. Por outro lado, se $\sqrt{N} = a_0a_1\cdots a_n.b_0\cdots b_m$, então $\sqrt{10^{2m}N} = a_0a_1\cdots a_nb_0\cdots b_m \in \mathbb{Z}$. Isto quer dizer que podemos assumir sempre que vamos procurar uma aproximação inteira para a raíz quadrada. Em termos práticos, isto não impacta em nada o método mas facilita bastante o raciocínio que vamos desenvolver de seguida:
Seja $a_0a_1\cdots a_n = \sqrt{N}$ o número que queremos encontrar, já que queremos descobrir a raíz quadrada de $N$. Note-se que $$\begin{align} N &= (a_0a_1\cdots a_n)^2 \\ &= (a_010^n + a_110^{n-1} + \cdots + a_n)^2 \\ &= (a_010^n)^2 + (2[a_010^n] + a_110^{n-1})a_110^{n-1} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ (2[a_0 10^n + a_1 10^{n-1}] + a_2 10^{n-2})a_2 10^{n-2} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ \cdots + (2[a_010^n + \cdots + a_{n-1}10] + a_n)a_n\end{align}$$ Para os mais desconfiados, a expansão apresentada é válida porque $$\left(\sum_{i=1}^n x_i\right)^2 = \sum_{i=1}^n \left(2\sum_{j=1}^{i-1} a_j + a_i \right)a_i$$ é trivialmente demonstrável por indução.
No nosso caso podemos ver que, da esquerda para a direita, começam por aparecer os dígitos de maior magnitude e, no termo com $(2[x] + a_i10^{n-i})a_i10^{n-i}$, $x$ é uma soma que só depende dos $a_j, j < i$, os dígitos de magnitude maior que $a_i$. Consideremos ainda $$\begin{cases} N_0 = N\\ N_{i+1} = N_{i} - (2[\sum_{j=0}^{i-1} a_j^{n-j}] + a_i10^{n-i})a_i10^{n-i} \end{cases}$$ O que vemos agora é que podemos criar um método iterativo para descobrir quais são os dígitos $a_i$. Note-se que $a_0$ é o maior dígito $d$ tal que $(d10^n)^2 \leq N$. Tendo descoberto $a_0$, podemos construir $N_1$ e vemos que $a_1$ é o maior dígito $d$ tal que $(d10^{n-1})^2 \leq N_1$. Tendo descoberto $a_1$, construímos $N_2$ e vemos que $a_2$ é o maior dígito $d$ tal que $(d10^{n-2})^2 \leq N_2$. Podemos continuar este raciocínio, até concluirmos que $a_n$ é o maior dígito $d$ tal que $a_n^2 \leq N_n$.
Tendo chegado a este ponto, ou temos $N_{n+1} = 0$, o que significa que $a_0a_1\cdots a_n$ é a raíz quadrada exata de $N$. Se $N_{n+1} > 0$, o número que calculámos é uma aproximação por defeito e pode ser melhorada, incluindo mais dígitos, se acrescentarmos zeros à direita de $N$ e continuarmos o nosso raciocínio.
Resumindo e sistematizando, o algoritmo - que não é trivial, quando comparado com os algoritmos usuais para multiplicar ou até para dividir - funciona assim:
Olho para o número para o qual quero calcular a raíz quadrada e, da direita para a esquerda, divido os dígitos em grupos de dois (isto corresponde a, na explicação acima, no passo com $N_i$ eu não querer saber dos dígitos que estão à direita de $a_i$).
Agora desenho as linhas auxiliares, deixando algum espaço em branco se eu quiser algumas casas decimais, e vou trabalhando da esquerda para a direita. Começo com o grupo mais à esquerda, que é só o $7$, e penso qual é o maior número que, ao quadrado, não fica maior que $7$. Bom, $2^2 = 4 < 7$ e $3^2 = 9 > 7$, logo é o $2$. Marco o $2$ como certo e retiro $2^2$ ao $7$. Desço o próximo grupo e continuo: 
Agora vem o passo que se repete sempre, e sempre da mesma maneira: pego em tudo o que já sei que está certo, neste caso o $2$, duplico, que dá $4$, e pergunto-me qual será o maior dígito $d$ tal que $4d \times d \leq 338$? Ou seja, $d$ vai fazer de dígito das unidades no $40$ e depois multiplico por $d$, e tudo isso tem de ser menor ou igual a $338$. Eu gosto de representar esta conta do seguinte modo: 
Esta parte tem de ser feita por tentativa e erro... Se $d=6$, $46 \times 6 = 276$ ainda parece pequeno. $47 \times 7 = 329 < 338$ e $48 \times 8$ já é grande de mais. Logo, $7$ é o dígito que queremos. Marcamos o $7$ como certo, subtraímos $329$ ao $338$, descemos o próximo grupo e repetimos tudo do início. 
Pegamos em tudo o que já sabemos estar certo, neste caso o $27$, duplicamos, para dar $54$, e perguntamo-nos qual é o maior dígito $d$ tal que $54d \times d$ não é maior que $929$. 
Neste caso é fácil de ver que temos de escolher $d = 1$. Marcamos o $1$ como certo, subtraímos $541$ ao $929$, descemos o próximo grupo e repetimos tudo do início. Como já não há mais grupos de dígitos, quer dizer que tudo o que temos até agora, $271$, é a parte inteira da raíz quadrada de $73829$. Se quisermos casas decimais, agora vamos juntando grupos de dois zeros. 
Voltamos a pegar em tudo o que já sabemos estar bem, neste caso o $271$, e duplicamos, para dar $542$, e perguntamo-nos qual é o maior dígito $d$ tal que $542d \times d$ não seja maior que $38800$. 
Ora $5000 \times 7 = 35000$ portanto tentamos $d = 7$, $5427 \times 7 = 37989$ que serve mesmo por pouco. Marcamos o $7$ como certo e subtraímos $37989$ a $38800$. Se quisermos mais casas decimais, voltamos a acrescentar um grupo de dois zeros. 
Como vamos parar por aqui, não precisamos realmente de fazer a subtração. Note-se que todos os dígitos que nós colocamos na região em cima à direita estão certos, logo a raíz quadrada de $73829$ começa com $271.7$.
Este método pode ser continuado enquanto houver papel e paciência e vai-nos dando aproximações por defeito da raíz quadrada que estamos a tentar calcular. Claro que se o número for um quadrado perfeito, este método pára quando chegamos ao último grupo de dois dígitos.
Espero que tenham entendido como o método funciona! Partilhem os vossos pensamentos na seccção dos comentários.
O método que vou descrever pode ser usado com qualquer número real, seja quadrado perfeito ou não, seja inteiro ou não, racional ou não. Vou começar por apresentar um raciocínio que mostra como o algoritmo surge. Para quem não estiver interessado, pode saltar diretamente para a explicação final de como funciona.
Para a exposição que se segue, se $a,b$ forem dígitos, então a notação $ab$ representa o número $10a + b$ em vez do número $a\times b$. Começamos por notar que, se quisermos descobrir $\sqrt{N}$ à mão e $\sqrt{N}$ for irracional, então vamos ter de nos contentar com uma aproximação com um número finito de casas decimais. Por outro lado, se $\sqrt{N} = a_0a_1\cdots a_n.b_0\cdots b_m$, então $\sqrt{10^{2m}N} = a_0a_1\cdots a_nb_0\cdots b_m \in \mathbb{Z}$. Isto quer dizer que podemos assumir sempre que vamos procurar uma aproximação inteira para a raíz quadrada. Em termos práticos, isto não impacta em nada o método mas facilita bastante o raciocínio que vamos desenvolver de seguida:
Seja $a_0a_1\cdots a_n = \sqrt{N}$ o número que queremos encontrar, já que queremos descobrir a raíz quadrada de $N$. Note-se que $$\begin{align} N &= (a_0a_1\cdots a_n)^2 \\ &= (a_010^n + a_110^{n-1} + \cdots + a_n)^2 \\ &= (a_010^n)^2 + (2[a_010^n] + a_110^{n-1})a_110^{n-1} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ (2[a_0 10^n + a_1 10^{n-1}] + a_2 10^{n-2})a_2 10^{n-2} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ \cdots + (2[a_010^n + \cdots + a_{n-1}10] + a_n)a_n\end{align}$$ Para os mais desconfiados, a expansão apresentada é válida porque $$\left(\sum_{i=1}^n x_i\right)^2 = \sum_{i=1}^n \left(2\sum_{j=1}^{i-1} a_j + a_i \right)a_i$$ é trivialmente demonstrável por indução.
No nosso caso podemos ver que, da esquerda para a direita, começam por aparecer os dígitos de maior magnitude e, no termo com $(2[x] + a_i10^{n-i})a_i10^{n-i}$, $x$ é uma soma que só depende dos $a_j, j < i$, os dígitos de magnitude maior que $a_i$. Consideremos ainda $$\begin{cases} N_0 = N\\ N_{i+1} = N_{i} - (2[\sum_{j=0}^{i-1} a_j^{n-j}] + a_i10^{n-i})a_i10^{n-i} \end{cases}$$ O que vemos agora é que podemos criar um método iterativo para descobrir quais são os dígitos $a_i$. Note-se que $a_0$ é o maior dígito $d$ tal que $(d10^n)^2 \leq N$. Tendo descoberto $a_0$, podemos construir $N_1$ e vemos que $a_1$ é o maior dígito $d$ tal que $(d10^{n-1})^2 \leq N_1$. Tendo descoberto $a_1$, construímos $N_2$ e vemos que $a_2$ é o maior dígito $d$ tal que $(d10^{n-2})^2 \leq N_2$. Podemos continuar este raciocínio, até concluirmos que $a_n$ é o maior dígito $d$ tal que $a_n^2 \leq N_n$.
Tendo chegado a este ponto, ou temos $N_{n+1} = 0$, o que significa que $a_0a_1\cdots a_n$ é a raíz quadrada exata de $N$. Se $N_{n+1} > 0$, o número que calculámos é uma aproximação por defeito e pode ser melhorada, incluindo mais dígitos, se acrescentarmos zeros à direita de $N$ e continuarmos o nosso raciocínio.
Resumindo e sistematizando, o algoritmo - que não é trivial, quando comparado com os algoritmos usuais para multiplicar ou até para dividir - funciona assim:
Olho para o número para o qual quero calcular a raíz quadrada e, da direita para a esquerda, divido os dígitos em grupos de dois (isto corresponde a, na explicação acima, no passo com $N_i$ eu não querer saber dos dígitos que estão à direita de $a_i$).
Este método pode ser continuado enquanto houver papel e paciência e vai-nos dando aproximações por defeito da raíz quadrada que estamos a tentar calcular. Claro que se o número for um quadrado perfeito, este método pára quando chegamos ao último grupo de dois dígitos.
Espero que tenham entendido como o método funciona! Partilhem os vossos pensamentos na seccção dos comentários.
In a previous post I showed how to approximate the square root of a number through an iterative process that consisted of a first guess and a sequence of ajustments. In this post I will show an algorithm to find the square root of any number by hand.
The method I am about to describe can be used with any real number, either a perfect square or not, integer or not, rational or not. I will start by exposing a train of thought that shows how the algorithm work and then I will proceed to present the steps that the algorithm consists of. If you are only interested in the final form of the algorithm, you can skip to that part here.
In what follows, if $a, b$ are digits then the notation $ab$ represents the number $10a + b$ instead of the number $a\times b$. We start by noting that, if we are to calculate $\sqrt{N}$ by hand and $\sqrt{N}$ is irrational, we will have to settle for an approximation with a finite number of decimal places. On the other hand, if $\sqrt{N} = a_0a_1\cdots a_n.b_0\cdots b_m$, then $\sqrt{10^{2m}N} = a_0a_1\cdots a_nb_0 \cdots b_m \in \mathbb{Z}$. This means we can assume that the square root we are computing is an integer. This has no practical impact on the algorithm but it does simplify what follows:
Let $a_0a_1\cdots a_n = \sqrt{N}$ be the number we want to find given that we want to compute the square root of $N$. We compute that $$\begin{align} N &= (a_0a_1\cdots a_n)^2 \\ &= (a_010^n + a_110^{n-1} + \cdots + a_n)^2 \\ &= (a_010^n)^2 + (2[a_010^n] + a_110^{n-1})a_110^{n-1} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ (2[a_0 10^n + a_1 10^{n-1}] + a_2 10^{n-2})a_2 10^{n-2} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ \cdots + (2[a_010^n + \cdots + a_{n-1}10] + a_n)a_n\end{align}$$ For the more meticulous, the previous expansion of the square is valid because $$\left(\sum_{i=1}^n x_i\right)^2 = \sum_{i=1}^n \left(2\sum_{j=1}^{i-1} a_j + a_i \right)a_i$$ is trivially provable by induction.
In our case we see that, from left to right, we have the digits of decreasing magnitude and the term with $(2[x] + a_i10^{n-i})a_i10^{n-i}$, where $x$ is a sum that depends only on the $a_j$ with $j < i$, has the digits with magnitude greater than that of $a_i$. We also define $$\begin{cases} N_0 = N\\ N_{i+1} = N_{i} - (2[\sum_{j=0}^{i-1} a_j^{n-j}] + a_i10^{n-i})a_i10^{n-i} \end{cases}$$ What we see now is that we can create an iterative method to find the digits $a_i$. Note that $a_0$ is the largest digit $d$ such that $(d10^n)^2 \leq N$. Having found $a_0$ we can construct $N_1$ and then notice that $a_1$ is the largest digit $d$ such that $(d10^{n-1})^2 \leq N_1$. Having found $a_1$ we can construct $N_2$ and then notice that $a_2$ is the largest digit $d$ such that $(d10^{n-2})^2 \leq N_2$. And so on and so forth, up until the point where $a_n$ was the largest digit $d$ such that $d^2 \leq N_n$.
Having gotten this far, either $N_{n+1} = 0$ - which means $a_0a_1\cdots a_n$ is the exact square root of $N$ - or $N_{n+1} > 0$ and in that case the number we computed is an approximation by defect of $\sqrt{N}$, which we can improve by including more digits, by appending zeroes to the right of $N$.
Summing up, the algorithm - which is far from trivial when compared to the usual algorithms for multiplication or division - goes like this:
We look at the number from which we want to extract the square root and, from right to left, group the digits two by two (this has to do with the fact that, at each point, we are only working with one digit from the square root).Now we draw some auxiliary lines, leaving some space between the number and the vertical line just in case we want to add some decimal places, and start working from left to right. We start with the leftmost group, which is just the $7$, and we try to figure out what is the largest digit that, when squared, isn't greater than $7$. Of course it is $2$, because $2^2 = 4 < 7$ and $3^2 = 9 > 7$. Because we chose $2$, it means $2$ is the first digit of the square root, we mark it as correct and subtract $2^2 = 4$ from the $7$. We bring the next group down and keep going: This is the step that repeats every time, always in the same fashion: we take everything we already got right - only the $2$ in this case - we double it - $2\times 2 = 4$ and then we look for the largest digit $d$ such that $4d \times d \leq 338$ (remember that $4d$ is not $4\times d $ but $40+d$). I like to represent this question in the following manner: Usually this step takes some trial and error... If $d = 6$, $46 \times 6 = 276$ which looks small. $47 \times 7 = 329 < 338$ and $48 \times 8$ is too big, thus $7$ is the right digit. We mark $7$ as correct, subtract $329$ from $338$ and bring the next group of two digits down. Now we rinse and repeat. We take everything we know is correct - the $27$ in this case - double it to get $54$ and then ask for the largest digit $d$ such that $54d \times d \leq 929$. In this case it is straightforward to see that we have to pick $d = 1$, marking it as correct. We do that, subtract $541$ from $929$, bring the next group of two digits down and repeat everything. Only that we are out of two-digit groups, meaning what we have now, $271$, is the integer part of the square root of $73829$. If we want to find some decimal places, we add pairs of zeroes. Having added those two zeroes, we keep doing what we have been doing. Take what we have - which is $271$ - double it to get $542$ and then ask for the largest digit $d$ such that $542d \times d \leq 38800$. Well, $5000 \times 7 = 35000$ so we try $d = 7$, $5427 \times 7 = 37989$ which is good by just a little bit. We mark the $7$ as correct and subtract $37989$ from $38800$. If we want more decimal places, we bring another pair of zeroes down. Because I do not what to keep going, I don't need to bother finishing that subtraction. Notice how every digit we mark is correct, thus our successive approximations are always by defect. In our case, we know that the square root of $73829$ starts with $271.7$.
This method can keep going while there is paper and patience left, giving a sequence of approximations by defect. If the number is a perfect square, the method stops when we reach the last group of two digits.
I hope you understood how the method works! Leave your thoughts below as a comment!
The method I am about to describe can be used with any real number, either a perfect square or not, integer or not, rational or not. I will start by exposing a train of thought that shows how the algorithm work and then I will proceed to present the steps that the algorithm consists of. If you are only interested in the final form of the algorithm, you can skip to that part here.
In what follows, if $a, b$ are digits then the notation $ab$ represents the number $10a + b$ instead of the number $a\times b$. We start by noting that, if we are to calculate $\sqrt{N}$ by hand and $\sqrt{N}$ is irrational, we will have to settle for an approximation with a finite number of decimal places. On the other hand, if $\sqrt{N} = a_0a_1\cdots a_n.b_0\cdots b_m$, then $\sqrt{10^{2m}N} = a_0a_1\cdots a_nb_0 \cdots b_m \in \mathbb{Z}$. This means we can assume that the square root we are computing is an integer. This has no practical impact on the algorithm but it does simplify what follows:
Let $a_0a_1\cdots a_n = \sqrt{N}$ be the number we want to find given that we want to compute the square root of $N$. We compute that $$\begin{align} N &= (a_0a_1\cdots a_n)^2 \\ &= (a_010^n + a_110^{n-1} + \cdots + a_n)^2 \\ &= (a_010^n)^2 + (2[a_010^n] + a_110^{n-1})a_110^{n-1} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ (2[a_0 10^n + a_1 10^{n-1}] + a_2 10^{n-2})a_2 10^{n-2} + \\ &\ \ \ \ \ \ \ \ \ \ \ \ +\ \cdots + (2[a_010^n + \cdots + a_{n-1}10] + a_n)a_n\end{align}$$ For the more meticulous, the previous expansion of the square is valid because $$\left(\sum_{i=1}^n x_i\right)^2 = \sum_{i=1}^n \left(2\sum_{j=1}^{i-1} a_j + a_i \right)a_i$$ is trivially provable by induction.
In our case we see that, from left to right, we have the digits of decreasing magnitude and the term with $(2[x] + a_i10^{n-i})a_i10^{n-i}$, where $x$ is a sum that depends only on the $a_j$ with $j < i$, has the digits with magnitude greater than that of $a_i$. We also define $$\begin{cases} N_0 = N\\ N_{i+1} = N_{i} - (2[\sum_{j=0}^{i-1} a_j^{n-j}] + a_i10^{n-i})a_i10^{n-i} \end{cases}$$ What we see now is that we can create an iterative method to find the digits $a_i$. Note that $a_0$ is the largest digit $d$ such that $(d10^n)^2 \leq N$. Having found $a_0$ we can construct $N_1$ and then notice that $a_1$ is the largest digit $d$ such that $(d10^{n-1})^2 \leq N_1$. Having found $a_1$ we can construct $N_2$ and then notice that $a_2$ is the largest digit $d$ such that $(d10^{n-2})^2 \leq N_2$. And so on and so forth, up until the point where $a_n$ was the largest digit $d$ such that $d^2 \leq N_n$.
Having gotten this far, either $N_{n+1} = 0$ - which means $a_0a_1\cdots a_n$ is the exact square root of $N$ - or $N_{n+1} > 0$ and in that case the number we computed is an approximation by defect of $\sqrt{N}$, which we can improve by including more digits, by appending zeroes to the right of $N$.
Summing up, the algorithm - which is far from trivial when compared to the usual algorithms for multiplication or division - goes like this:
We look at the number from which we want to extract the square root and, from right to left, group the digits two by two (this has to do with the fact that, at each point, we are only working with one digit from the square root).
This method can keep going while there is paper and patience left, giving a sequence of approximations by defect. If the number is a perfect square, the method stops when we reach the last group of two digits.
I hope you understood how the method works! Leave your thoughts below as a comment!
- RGS
How to compute any square root by hand
Reviewed by Unknown
on
May 25, 2018
Rating:
Reviewed by Unknown
on
May 25, 2018
Rating:
No comments: