BastterCode semana 11 - 367. Valid Perfect Square
comentada em 19/04/2023 19:38

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        return num ** 0.5 / int(num ** 0.5) == 1

Dart

class Solution
{
  bool isPerfectSquare(int num) {
   int i = 0;
   while((i*i) < num) i++;
   return i*i == num;
  }
}

C#  com Busca Binária

public class Solution {
    public bool IsPerfectSquare(int num) {
        if (num == 1) return true;

        long left = 1;
        long right = num;
        
        while (left <= right) {
          long mid = (right+left) / 2;
          var square = mid*mid;

          if (square == num) return true;
          else if (square < num) left = mid + 1;
          else right = mid - 1;
        }

        return false;
    }
}?

Dando uma pesquisada, achei uma solução para Sqrt usando métodos numéricos para aproximação. 

public class Solution {
    long sqrt(long x) {
        double precision = 10e-8;
        double prev = 0.0;
        double mid = x;
        
        while(Math.Abs(mid - prev ) > precision)
        {
          prev = mid;
          mid = (mid +(x/ mid))/2.0;
        }
        return Convert.ToInt64(mid);
    }

    public bool IsPerfectSquare(int num) {
        if (num == 1) return true;
        var p = sqrt(num);
        return p * p == num;
    }
}

Eu não percebi a princípio quando sugeri, mas esse problema é bem parecido com um outro que eu resolvi lá no leetcode por conta própria, um que pedia para criar uma função raiz quadrada.

Aproveitei o que eu aprendi lá naquele outro problema e passei o início da noite dando uma turbinada na resolução. Ainda não cheguei num ponto ótimo, mas to melhorando devagar. Uma ideia que tive depois foi a de usar o divide and conquer ali no último loop, mas deixei pra analisar isso outro dia.

O código provavelmente não vai ser muito intuitivo, depois vou fazer um tópico explicando.

class Solution {
public:
    bool isPerfectSquare(int num) {
        if ((num & 2) != 0) return false;
        
        int n = 1073741824;
        int aux = 30;
        
        while (n > num) {
            n >>= 2;
            aux -= 2;
        }
        
        aux >>= 1;
        
        int g = 1 << aux;
        int p = (num - n) / g;
        int r = (num - n) % g;
        
        n = 0;
        
        if (p % 2 != 0) n = 1 << (aux/2);
        
        while (p > (n*n - r)/g + 2*n) n++;
    
        if ((g + n)*(g + n) == num) return true;
        
        return false;
    }
};?

O que eu acho legal desse tipo de problema é que existem várias respostas possíveis, com um espaço enorme pra otimização e, consequentemente, pra estudo e prática.

A forma mais direta de resolver é jogar um loop incrementando a variável de um em um até que o quadrado dela iguale ou supere o número informado. Se igualar, o retorno é verdadeiro. Se superar, é falso.

Só que esse método é bem ineficiente, o loop precisa rodar até 46341 vezes para o maior inteiro positivo de 32bits possível, que é 2^31-1.

Pelo que eu já li sobre o assunto, nesse tipo de problema a otimização pode ser de duas formas. A primeira é encontrar um método rápido e de baixo custo computacional para encontrar uma aproximação inicial boa para o número que se deseja (no caso, a raiz do número informado). A segunda é encontrar um algoritmo mais eficiente, que convirja mais rapidamente para a resposta, ou seja, que "pule" vários números a cada laço do loop.

Existem alguns métodos de otimização mais gerais, que são úteis em muitas situações. Um algoritmo muito conhecido para esse tipo de problema é o de Newton, que aproxima a raiz de uma função usando sua derivada. É um método muito simples e que converge muito bem, que pode ser utilizado nas mais diferentes situações (basta mudar a função). Ele tem algumas limitações e normalmente não é O melhor método, mas, como é um método pau pra toda obra, é muito legal de se conhecer.

Eu ainda não cheguei a usar ele, depois vou tentar.

Usando o "divide and conquer" (na verdade, não sei se é esse o nome mesmo, mas é o método padrão que transforma o loop linear num loop logarítmico).

Peguei o método que já tinha usado para encontrar uma aproximação inicial e delimitei os valores mínimo e máximo do intervalo de análise a partir dela, o que em tese deve aumentar bastante a rapidez.

Esse método é muito mais eficiente do que o que eu usei na primeira solução, que é linear. Depois vou ver se posso mesclar ambas, usando a primeira pra reduzir ainda mais o espaço para uma busca logarítmica.

class Solution {
public:
    bool isPerfectSquare(int num) {
        if ((num & 2) != 0) return false;
        
        int n = 1073741824;
        int aux = 30;
        
        while (n > num) {
            n >>= 2;
            aux -= 2;
        }
               
        aux >>= 1;
        int l = 1 << aux;
        int h = 1 << (aux + 1);
        
        while (l <= h) {
            int m = (l + h)/2;
            if (m == num/m && num % m == 0) return true;
            else {
                if (m < num/m) l = m + 1;
                else h = m - 1;
            }  
        }
        
        return false;
    }
};?

Explicando o algoritmo lá de cima.

O primeiro while é pra encontrar uma aproximação inicial. Os operadores >> e << servem para mover bits em um número pelo valor indicado após o operador. Quando eu faço "n >>= 2", estou movendo os bits de n 2 posições para a direita, o que é o mesmo que dividir por 4.

O que o loop faz, portanto, é pegar um n e dividir por 4 até encontrar um número menor ou igual que aquele cuja raiz queremos achar. O n inicial é 2^30, maior potência de 4 (4^15) que cabe em um inteiro de 32 bits. O n final será, então, a maior potência de 4 menor ou igual que num.

Calcular a raiz de uma potência de 4 é bastante fácil, já que 4 é 2^2 e, portanto 4^n é 2^2n. Basta dividir o expoente por 2 e terei 2^n, que é a raiz da potência de 4 em questão. Logo, esse método me permite rapidamente encontrar uma aproximação inicial para a raiz de num.

Além disso, como a potência de 4 imediatamente superior é maior que num, então eu tenho um intervalo para a raiz de num. Se a maior potência de 4 menor que num é 4^n, então a raiz de num está entre 2^n e 2^(n+1).

O método que eu usei originalmente pra calcular a raiz a partir disso surgiu de uma análise que eu comecei a fazer das propriedades que essa raiz deve ter, para ser um número inteiro. Eu parti da premissa que, sabendo a diferença entre num e 4^n, eu poderia estimar aproximadamente a raiz a partir de um incremento x em cima de 2^n.

Consegui chegar a algumas conclusões, que me permitiram reduzir ainda mais o espaço em que a raiz pode estar. Mas não tive muito tempo, vida anda corrida, e acabei fazendo do jeito que deu kkk

As conclusões foram as seguintes, se x é o incremento em cima de 2^n que dá a raiz de num, então:
(2^n + x)^2 = num = 2^2n + z

em que z é a diferença entre num e n, a maior potência de 4 menor que num, que calculamos facilmente a partir do primeiro loop.

Expandindo a expressão, fica:
2^2n + 2*x*2^n + x^2 = 2^2n + z -> z = 2*x*2^n + x^2

Dividindo tudo por 2^n, temos:

z/2^n = 2*x + x^2/2^n

Como x precisa ser inteiro para que a raiz de num seja quadrada perfeita e z é a diferença entre dois números inteiros, então podemos concluir que:

1- z só pode ser menor que 2^n se for 0. Pois, do contrário, z/2^n seria um número racional menor que 1 que é maior que 2*x, um inteiro maior que 1;

2- Como 2*x é um inteiro, então qualquer resto na divisão de z por 2^n deve ser também o resto da divisão de x^2 por 2^n. Do contrário, teremos uma fração menor que 1 de um lado diferente da fração menor que 1 do outro lado, gerando uma desigualdade;

3- Sendo assim, se z for expresso como p*2^n + r, em que r é o resto da divisão (z % 2^n) e p é o inteiro da divisão (z / 2^n), temos que:
(p*2^n + r)/2^n = 2*x + x^2/2^n -> p + r/2^n = 2*x + x^2/2^n -> p = (x^2 - r)/2^n + 2*x

4- Como consequência, eu não preciso procurar o x (a diferença entre a raiz de num e 2^n) em todo o intervalo, basta procurar até superar p, que é a divisão de z por 2^n.

Eu não cheguei, contudo, a analisar se isso é mais eficiente que fazer a procura em todo o intervalo, pois p pode assumir valores maiores. Suspeito que a eficiência seja a mesma, inclusive porque ambos são métodos lineares em que x aumenta de 1 em 1.

Depois quero ver se consigo aprofundar essas investigações aí.

Ah, uma última coisa. Aquele primeiro if lá de cima foi resultado de uma análise que eu fiz quando resolvi o problema da raiz quadrada do leetcode.

Eu percebi que todos os números quadrados perfeitos (ou seja, n^2, sendo n um inteiro positivo) não têm o segundo bit ligado, o que corresponde ao 2. Interessante, né?

Depois eu consegui provar porque isso acontece. Mas não lembro agora, quando lembrar eu coloco aqui.

Na ocasião eu estava tentando encontrar algum padrão geral que me permitisse estimar a raiz de um número inteiro a partir da análise da sua representação binária. Infelizmente, embora tenha encontrado alguns padrões, não achei algo geral e simples.

O que ficou foi só essa regra de que o segundo bit tem que estar desligado e também a regra de que o primeiro bit, que transforma em ímpar, liga e desliga alternadamente. O que faz sentido considerando que n^2 é a soma dos n primeiros números ímpares, que é uma relação bem interessante e famosa.

@FlyCavok

Tava estudando ontem e vi esse método numérico aí que você usou. Ele é o método babilônico. Olha que legal:

@oxe  

Boa, é isso aí que eu achei mesmo. Eu topei até com um artigo na IEEE que fala sobre isso, sobre calcular sqrt de forma eficiente