Raiz quadrada por restauração

Como o nome já diz, esse algoritmo pode ser usado para calcular a parte inteira da raiz quadrada de um número inteiro. Funciona de forma similar à divisão por restauração, de modo iterativo, onde cada iteração nos deixa mais próximos do resultado final. Mas como e por quê esse algoritmo funciona?

Essa é a pergunta que vamos responder hoje, especificamente para base 2 (binário). De uma forma bem peculiar, talvez.

P.S. A versão em inglês dessa página tem alguns links para páginas com mais explicações.

Descrição

Dado um número $𝑋$ representado em binário, podemos adicionar um zero à esquerda se necessário, de modo que esse número tenha $2 𝑘$ dígitos, para algum inteiro $𝑘$ . Após fazer isso, podemos considerar $𝑄$ e $𝑅$ que satisfaçam $𝑋 = 𝑄^{2} + 𝑅$ , de modo que $𝑅 \geq 0$ e $𝑄$ seja maximizado (essa é uma forma de definir a raiz quadrada para inteiros). $𝑄$ terá $𝑘$ dígitos:

𝑋 é no máximo 2^{2 𝑘} - 1 < 2^{2 𝑘} = {(2^{𝑘})}^{2}

Assim, $𝑞 + (𝑘 - 1)$ é o bit mais significativo (MSB) na representação de binária de $𝑄$ , e $𝑞_{0}$ é o menos significativo (LSB). O primeiro passo do algoritmo é dividir $𝑋$ em pares de bits. Começamos do par mais significativo e subtraimos 1. Se o resultado for maior ou igual a $0$ , então $𝑞_{𝑘 - 1} = 1$ , caso contrário, $𝑞_{𝑘 - 1} = 0$ e o valor anterior desse par é restaurado.

Daí, o resultado obtido é concatenado com o próximo par e tentamos subtrair $⟨ 0 𝑞_{𝑘 - 1} 01 ⟩$ (essa notação foi usada para representar concatenação). O resultado irá determinar $⟨ 𝑞_{𝑘 - 2} ⟩$ . O próximo passo seria agrupar novamente com o próximo par e subtrair $⟨ 00 𝑞_{𝑘 - 1} 𝑞_{𝑘 - 2} 01 ⟩$ , encontrando $𝑞_{𝑘 - 3}$ etc. Esse processo é repetido até que não haja mais pares. O resto da última subtração corresponde a $𝑅$ .

Uma possível solução

Um fato curioso: todos os números quadrados podem ser expressos como uma soma de números ímpares consecutivos, começando do 1.

\sum_{𝑛 = 1}^{𝑝} (2 𝑛 - 1) = 𝑝^{2}

Isso permite implementar uma solução bem simples, que consiste em subtrair ímpares de $𝑋$ sucessivamente, mantendo uma contagem de quantos ímpares foram subtraídos e do valor de $𝑋$ . Ao final, quando não for mais possível subtrair, a quantidade de ímpares subtraídos será $𝑄$ e o resto será $𝑅$ . Mas esse processo é bem ineficiente. Dá pra melhorar bastante, e é isso que esse algoritmo faz: subtrai vários números ímpares, em vez de apenas um, por vez.

Uma demonstração

Vamos tentar entender o que está acontecendo em cada iteração. Assumindo que estamos em uma determinada iteração e todos os bits de $𝑄$ determinados até então são $0$ , podemos concluir que o valor subtraído na iteração atual é uma potência de 4. No caso base ( $𝑘 = 1$ ), subtraímos $1$ . Quando $𝑘$ é incrementado, o valor sendo subtraído na primeira iteração é deslocado para a esquerda em duas unidades, que é o mesmo que multiplicar por $2^{2} = 4$ . E como $4^{𝑛} = 2^{2 𝑛} = {(2^{𝑛})}^{2}$ , o valor sendo subtraído nesse caso é uma soma de números ímpares consecutivos, começando em $1$ (com $2^{𝑛}$ termos).

Ou seja, isso nos mostra que a quantidade de números ímpares que compõem essa soma é reduzida pela metade a cada iteração. Mas e se algum bit de $𝑄$ for diferente de $0$ ? Isso implica que foi possível subtrair uma certa quantidade de números ímpares, logo, devemos avançar na sequência de alguma forma (não começar mais no $1$ ), para que esses números não sejam subtraídos novamente. Podemos mostrar que adicionar os bits de $𝑄$ ao subtraendo serve exatamente para resolver esse problema.

Considerando que estamos na $𝑖$ -ésima iteração (onde a primeira seria $0$ e a última $𝑘 - 1$ ), o valor sendo subtraído nessa iteração, que iremos chamar de $𝑠$ , será dado por:

𝑠 = 2^{2 𝑘 - 2 𝑖 - 2} + \sum_{𝑚 = 0}^{𝑖 - 1} 𝑞_{𝑘 - 𝑚 - 1} \cdot 2^{2 𝑘 - 𝑖 - 𝑚 - 1}

O primeiro termo corresponde à constante $1$ , enquanto o segundo corresponde aos bits de $𝑄$ de iterações anteriores. A ilustração a seguir mostra a representação binária de $𝑠$ :

Vamos denotar por $𝐷 (𝑛, 𝑚)$ o conjunto ou subsequência de números ímpares começando no enésimo número com $𝑚$ entradas. Para cada bit de $𝑄$ que for $1$ , temos que pular metade da quantidade de números ímpares subtraída na iteração correspondente. Podemos deduzir, então, que o índice inicial $𝑛_{𝑖}$ (começando em $1$ , pois usaremos números ímpares da forma $2 𝑛 - 1$ ) será:

𝑛_{𝑖} = \sum_{𝑚 = 0}^{𝑖 - 1} 𝑞_{𝑘 - 𝑚 - 1} \cdot 2^{𝑘 - 𝑚 - 1} + 1

E se assumirmos, por enquanto, que a quantidade de números ímpares subtraídos sempre for reduzida pela metade a cada iteração, independentemente dos bits anteriores de $𝑄$ , então o valor subtraído na $𝑖$ -ésima iteração será dado por:

𝑠 = \sum 𝐷 (𝑛_{𝑖}, 2^{𝑘 - 𝑖 - 1})

Podemos mostrar que vale a recíproca, ou seja, partindo de $\sum 𝐷$ , chegaremos a $𝑠$ , na forma que foi definido anteriormente:

\begin{aligned} \sum 𝐷 & = \sum_{𝑡 = 1}^{2^{𝑘 - 𝑖 - 1}} (2 (𝑛_{𝑖} + 𝑡 - 1) - 1) \\ = 2 \cdot 2^{𝑘 - 𝑖 - 1} \cdot 𝑛_{𝑖} + 2^{𝑘 - 𝑖 - 1} (2^{𝑘 - 𝑖 - 1} + 1) - 3 \cdot 2^{𝑘 - 𝑖 - 1} \\ = 2^{2 𝑘 - 2 𝑖 - 2} + 2^{𝑘 - 𝑖} \cdot 𝑛_{𝑖} - 2^{𝑘 - 𝑖} \\ = 2^{2 𝑘 - 2 𝑖 - 2} + 2^{𝑘 - 𝑖} (\sum_{𝑚 = 0}^{𝑖 - 1} 𝑞_{𝑘 - 𝑚 - 1} \cdot 2^{𝑘 - 𝑚 - 1} + 1) - 2^{𝑘 - 𝑖} \\ = 𝑠 \end{aligned}

Mas por quê o algoritmo tem essa estrutura? Por que usamos binário? Embora outras bases possam ser usadas, essa base deixa o algoritmo mais simples e é muito útil, ao permitir seu uso em computadores. Note que $| 𝐷 |$ é uma função exponencial de $𝑖$ : podemos interpretar que esse algoritmo faz uma busca binária no espaço de valores possíveis para $𝑄$ , que pode assumir $2^{𝑘}$ valores distintos, e cada um deles deve ser possível de se alcançar partindo do ponto inicial. Dessa forma, a complexidade desse algoritmo é $𝑂 (𝑘)$ .

Curiosidade
Como cada bit na representação binária de $𝑄$ é atribuído uma única vez, esse algoritmo pode ser implementado usando apenas circuitos combinacionais (que foi como eu descobri esse algoritmo originalmente)

O diagrama a seguir mostra uma árvore de decisão binária representando todas as escolhas que o algoritmo pode tomar para $𝑘 = 3$ , partindo do ponto inicial. Cada nível é uma iteração. Uma linha pontilhada indica que a subtração resultou em um valor negativo e o valor anterior foi restaurado. Cada nó mostra o valor subtraído naquela iteração, como uma soma de ímpares consecutivos. Note que as folhas não são mostradas; seria possível estender esse diagrama. Além disso, cada caminho da raiz até uma folha corresponde a um valor diferente para $𝑄$ .