Algoritmo para calcular a raiz quadrada de um número

Quando precisamos localizar um determinado item dentro de estruturas de dados ordenadas, a busca binária desponta como uma das soluções de pesquisa mais eficientes. Diferente da convencional busca linear, esse algoritmo desempenha em complexidade logarítmica de tempo, proporcionando ganhos expressivos de performance, sobretudo a medida que o input processado cresce de tamanho.

Entretanto, muitos programadores não sabem que a busca binária possui várias outras aplicações relevantes, que se distanciam do seu propósito original. Uma dessas finalidades alternativas, que será apresentada no decorrer da publicação, consiste no cálculo da raiz quadrada de números inteiros.

Entendendo o problema

Ao recorrer à literatura matemática, afirmamos que a raiz quadrada de x deriva em um número y que, multiplicado por si próprio, iguala-se a x. Logo, seguindo esse raciocínio, a raiz quadrada de dezesseis é quatro, enquanto a raiz quadrada de cem é dez, e assim por diante.

Considerando o contexto específico deste problema, o número x que não detiver uma raiz quadrada perfeita, terá o seu resultado arredondado para baixo. Por exemplo, a raiz quadrada de onze corresponde aproximadamente a 3,3166247903554. Isto posto, a resposta final do desafio, ou melhor dizendo, o número y, seria três.

Usando complexidade em raiz quadrada de tempo para resolver o problema

Antes de analisar o uso da busca binária na resolução do problema, cabe discorrer um pouco a respeito do algoritmo trivial que obtém o retorno almejado. Essa maneira diferenciada testa todos os números a partir de um, incrementando a sua contagem até que a raiz quadrada supere o número x.

A atualização do valor da variável resultado levando em conta a multiplicação de i por i faz com que o algoritmo execute em complexidade de tempo de raiz quadrada de x. Ou seja, no pior cenário possível de processamento, a função consumiria o equivalente à √x. 

1. O procedimento verifica se o input x é igual a zero ou um, que são os corner cases deste algoritmo. Em caso positivo, retorna-se o próprio número x. 
2. As variáveis i e resultado são declaradas e inicializadas com o valor de um. Ao passo que i armazena a raiz quadrada de x, resultado armazena o produto da multiplicação de i vezes i.
3. Enquanto o valor de resultado não for maior do que x, isto quer dizer, até a raiz quadrada de x ser calculada, incrementa-se i em um, e resultado tem o seu valor modificado pela multiplicação de i por i. Dessa forma, um novo número é checado a cada iteração na procura da raiz quadrada de x.
4. Enfim, a função retorna o valor da variável i subtraído de um, representando portanto a raiz quadrada de x. O motivo por trás da subtração de i está no fato que o loop while executa uma iteração adicional após a raiz quadrada ter sido encontrada. 

Usando complexidade logarítmica de tempo para resolver o problema

A solução anterior possui um bom desempenho quando o valor de x está em patamares não tão elevados. Contudo, o mesmo não pode ser dito em situações que x reproduz números de maior ordem de grandeza.

Tendo isso em vista, o algoritmo para calcular a raiz quadrada de um número com base no método da busca binária emerge como uma possibilidade mais efetiva. Dado que a complexidade de tempo desse mecanismo de pesquisa atinge o nível logarítmico, a computação de inputs maiores não demonstra ser um empecilho.

Nitidamente, embora a essência da busca binária esteja presente no código acima, é perceptível que algumas modificações foram realizadas no algoritmo com o intuito de adaptá-lo ao problema em questão.

1. A função checa se o input x é igual a zero ou um, que conforme dito, são os chamados corner cases. Em caso positivo, retorna-se o próprio número x.
2. A variável inicio é declarada com o valor do número um, demarcando o começo do intervalo da busca pela raiz quadrada.
3. A variável fim é declarada com o valor da metade do número x, demarcando o término do intervalo da busca pela raiz quadrada. Matematicamente falando, a raiz quadrada de qualquer número (se arredondarmos para baixo) nunca supera a sua própria metade.
4. A variável resposta é declarada para armazenar o resultado calculado pelo método.
5. Enquanto o intervalo final de pesquisa for maior do que o intervalo inicial, a função executa um loop while que possui uma série de operações. A princípio, seguindo o padrão da busca binária, a variável metade é declarada, reduzindo a janela de pesquisa ao meio. Na sequência, a variável quadrado computa justamente o quadrado do valor de metade. Se esse número for igual a x, significa que a raiz quadrada perfeita foi encontrada pela variável metade. Senão, caso x supere o valor de quadrado, a variável inicio tem o seu valor atribuído para metade + 1, reajustando assim o intervalo de busca para números maiores. Por fim, se x for inferior, a variável fim tem o seu valor atribuído para metade - 1, reajustando desta forma o intervalo de busca para números menores.
6. Na hipótese de x não possuir uma raiz quadrada perfeita, o procedimento retorna o valor da variável resposta.

Analisando a complexidade das soluções

Objetivando evidenciar a diferença de complexidade de tempo entre os algoritmos analisados até então, o quadro a seguir, gerado pela biblioteca BenchmarkDotNet, detalha diversos cenários de processamento, nos quais o valor do input aumenta a cada simulação. Cabe ressaltar que o espaço auxiliar de memória usado pelas duas funções é constante, afinal de contas não há chamadas recursivas ou a declaração de estruturas de dados auxiliares que variem de acordo com o input em nenhum dos métodos.

Método	Input	Média de tempo	Espaço alocado
MétodoComplexidadeRaizQuadrada	Input100	Média de tempo3.742 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	Input100	Média de tempo6.782 ns	Espaço alocado-
MétodoComplexidadeRaizQuadrada	Input500	Média de tempo6.615 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	Input500	Média de tempo11.563 ns	Espaço alocado-
MétodoComplexidadeRaizQuadrada	Input1000	Média de tempo9.633 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	Input1000	Média de tempo10.572 ns	Espaço alocado-
MétodoComplexidadeRaizQuadrada	Input5000	Média de tempo20.407 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	Input5000	Média de tempo14.836 ns	Espaço alocado-
MétodoComplexidadeRaizQuadrada	Input1000000	Média de tempo246.772 ns	Espaço alocado-
MétodoComplexidadeLogaritmica	Input1000000	Média de tempo27.472 ns	Espaço alocado-

Durante o hiato em que o input oscilou entre cem e mil, o algoritmo baseado na busca binária executou com uma velocidade menor se comparado ao MétodoComplexidadeRaizQuadrada. Todavia, à proporção que o input alcançou valores expressivos, na casa dos cinco mil e um milhão, o MétodoComplexidadeLogaritmica comprovou ser muito mais eficaz, obtendo uma margem de quase dez vezes em relação ao seu par.

O código-fonte completo dos algoritmos e os detalhes extras acerca do desempenho de cada um deles estão disponíveis no meu repositório do Github.