Descobrindo a Raiz Quadrada

Essa semana eu fui apresentado a um desafio particular: escreva um código que descubra a raiz quadrada de um número real N, sem usar nenhuma biblioteca matemática.

A solução que me veio em mente é simples e elegante, e utiliza um algoritmo/paradigma bem conhecido pelos cientistas da computação.

Após tenta resolver por conta, clique no link abaixo para ver a solução.

Variação

Se N fosse um inteiro, e nos fosse garantido que ele era um quadrado perfeito (um número inteiro que tem uma raiz quadrada inteira), um algoritmo trivial seria testar todas as possibilidades entre 1 e N:

int raiz_quadrada(int n) {
    for(int i=1; i<=n; i++) {
        if(i*i == n)
            return i;
    }
    return 0;
}

Desafio

O desafio aparece, porém, quando o nosso N é um número real, e não necessariamente tem uma raiz quadrada inteira. Testar todas as possibilidades é uma missão impossível, pois há infinitos números reais entre 1 e N, tal como 1.01, 1.001, 1.0001, 1.00001, 1.000001, …, 1.000000000000000…0000000001, etc.

O que fazer então? Por onde começar?

Busca Binária

Pra quem não sabe, busca binária é um algoritmo de busca muito elegante. Sua utilização mais popular é procurar por um determinado valor dentro de uma sequência de valores, dado que tal sequência está de alguma maneira ordenada.
Para mais informações: [link]

A busca binária tira vantagem do fato do vetor estar ordenado, e aqui está a ligação com o nosso problema.

Elaborando

Se não podemos chutar os valores de maneira trivial, só nos resta chutar os valores de maneira inteligente.

Vamos ver, digamos que o nosso N é 64 (pra facilitar).

Vamos chutar. Mas em vez de chutar 1, 1.1, 1.01, vamos chutar algo mais provável. Que tal N/2?

Bom, 32*32 é muito alto. Logo, 32 não é a raiz quadrada de 64, e, o melhor, nenhum valor maior que 32 é a raiz quadrada de 64 🙂

Vamos abaixar um pouco então. Que tal 32/2.

16*16 também é muito alto, logo nenhum número maior ou igual que 16 é a raiz quadrada de 64. Percebam que já eliminamos infinitos números (duas vezes)!

Abaixando mais um pouco chegamos a nossa solução. 16/2 é igual a 8, e 8*8 é igual a 64, para nossa alegria.

Veja só, em vez de infinitas tentativas, só precisamos de 3.

Não se iludam, porém. 64 é um quadrado perfeito, e escolhido propositalmente por ser fácil. Alguns números não vão ser tão fácil, e talvez até levem milhares de tentativas para ser descoberto. A maioria dos algoritmos pára após um número limitado de tentativas, trocando tempo por precisão. O ponto aqui é: milhares < infinito. Logo, nosso algoritmo é eficiente.

Solução

Elaborando um pouco o nosso algoritmo, e seguindo o modelo da busca binária, temos o seguinte algoritmo:

double raiz_quadrada(double n) {
    double ini = 0, meio, fim = n;
    
    for(int i=0; i<100; i++) { // faremos no máximo 100 tentativas
         meio = (ini+fim)/2.0;
         
         if(meio*meio == n) return meio;
         else if(meio*meio > n) fim = meio;
         else ini = meio;
    }
    
    return meio;
}

2 comentários em “Descobrindo a Raiz Quadrada”

  1. Bom raciocínio, também teria feito a mesma coisa se tivessem me perguntado isso.

    Algumas questões interessantes: Se o resultado da iteração i for igual a da iteração i-1 já não podemos parar o algoritmo? E caso for requisitado que o resultado tenha uma precisão de 10^(-X)? Tem como fazer de forma mais eficiente?

    Isso sempre é legal de saber, tentei encontrar como é feito o sqrt do math.h, mas não tive sucesso na procura.

    Aqui teve um cara que comparou vários métodos: http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi. Existe até métodos com constantes mágicas, legal não?

    Pelo que li, provavelmente é usado o método de Newton-Raphson para calcular a raiz quadrada, fiz um post comentando sobre ele aqui: https://meitcher.wordpress.com/2015/02/03/achando-a-raiz-quadrada-de-um-numero-real-positivo/

    Valeu por apresentar o problema aí Cristhian, deu para se divertir bastante xD!

  2. Christian, ja viu o método babilônico para encontrar as raízes?
    É bem simples! Ele faz o seguinte:
    Supondo que desejamos calcular a raiz quadrada de n, pode-se escolher um numero qualquer x, depois obtem-se n/x, que seria basicamente o outro lado de um retângulo de área n. O próximo passo é fazer a média aritmetica entre x e n/x(esse será o pŕoximo valor de x).
    Repetindo-se os passos, o retângulo vai se aproximando a um quadrado.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.