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 dígitos, para algum inteiro . Após fazer isso, podemos considerar e que satisfaçam , de modo que e seja maximizado (essa é uma forma de definir a raiz quadrada para inteiros). terá dígitos:

Assim, é o bit mais significativo (MSB) na representação de binária de , e é 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 , então , caso contrário, e o valor anterior desse par é restaurado.

Daí, o resultado obtido é concatenado com o próximo par e tentamos subtrair (a barra representa concatenação). O resultado irá determinar . O próximo passo seria agrupar novamente com o próximo par e subtrair , encontrando 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.

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 , podemos concluir que o valor subtraído na iteração atual é uma potência de 4. No caso base (), subtraímos . Quando é incrementado, o valor sendo subtraído na primeira iteração é deslocado para a esquerda em duas unidades, que é o mesmo que multiplicar por . E como , o valor sendo subtraído nesse caso é uma soma de números ímpares consecutivos, começando em (com 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 ? 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 ), 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 e a última ), o valor sendo subtraído nessa iteração, que iremos chamar de , será dado por:

O primeiro termo corresponde à constante , 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 , 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 , pois usaremos números ímpares da forma ) será:

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:

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

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 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 , 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 .