Double Enganoso

Este texto é uma tradução do artigo original do meu amigo, Maksim Pelevin. Se você está confortável para ler em russo, pode encontrar outros artigos interessantes em seu blog.

Você já sabe disso:

O tipo de dados double não é muito preciso

Vamos reforçar esse entendimento resolvendo um problema no CodeWars.

Declaração do problema

A tarefa descrita no CodeWars é a seguinte:

Sua tarefa é construir um prédio, que será uma pilha de n cubos. O cubo na parte inferior terá um volume de n^3, o cubo acima terá volume de (n-1)^3 e assim por diante até o topo, que terá volume de 1^3.

Você recebe o volume total m do prédio. Recebendo m, você consegue encontrar o número n de cubos que terá que construir?

O parâmetro da função findNb será um inteiro m e você terá que retornar o inteiro n tal que n^3 + (n-1)^3 + … + 1^3 = m se tal n existir, ou -1 se não existe tal n.

Solução ingênua

A solução mais direta usando loops seria algo como:

public static long findNb(long m) {
    long n = 0, totalVolume = 0;
    while (totalVolume < m) {
        totalVolume += ++n * n * n;
    }
    return totalVolume == m ? n : -1;
}

Solução Matemática

Na universidade, aprendi sobre séries matemáticas e os métodos para calcular suas somas, então aqui está a minha tentativa de uma solução matemática.

Eu não me lembro mais das fórmulas, mas, felizmente, Wolfram Alpha está aqui para ajudar. Para obter a fórmula, vamos executar a seguinte consulta: n^3, n = 1 até k.

Os resultados nos dizem que:

Vamos substituir m pelo lado esquerdo da equação, então aplicamos a propriedade de raiz quadrada e multiplicamos os dois lados da equação por dois. Após simplificar, obtemos:

Escreva o código

Aqui está uma solução para a equação acima, escrita em Java:

public static long findNb(long m) {
    double res = Math.sqrt(m);
    double d = 1 + 8 * res;
    double n = (Math.sqrt(d) - 1) / 2;
    return n - Math.floor(n) == 0 ? (long) n : -1;
}

Resultados

Acontece que este código retorna um resultado incorreto para um subconjunto de dados de teste. Essa inconsistência é visível, por exemplo, quando você passa 1646842954019151682L como entrada.

Ao calcular uma raiz quadrada em Java, você pode obter um resultado que não é totalmente preciso. Vamos dar uma olhada:

System.out.println(String.format("%.30f", Math.sqrt(1646842954019151682L)));
// saída 1283293791.000000000000000000000000000000
// correto 1283293791.00000000038962239473657673134031176401122912...

Obviamente, a saída e a resposta correta são diferentes. Fim!

Conclusão

A solução tecnicamente correta e potencialmente mais rápida nem sempre é a melhor a escolher. Isso pode não ser surpresa para um desenvolvedor experiente, mas aqueles novos na programação podem se perguntar sobre a causa do erro por um bom tempo.

Se você está se perguntando como corrigir o problema com a solução matemática, uma abordagem é usar BigDecimal . Este código passa em todos os testes:

public static long findNb(long m) {
    MathContext mc = new MathContext(64);
    BigDecimal res = BigDecimal.valueOf(m).sqrt(mc);
    BigDecimal d = res.multiply(BigDecimal.valueOf(8)).add(BigDecimal.ONE);
    BigDecimal n = d.sqrt(mc).subtract(BigDecimal.ONE).divide(BigDecimal.valueOf(2));
    return Objects.equals(n, n.setScale(0, RoundingMode.FLOOR)) ? n.longValue() : -1;
}

… e um pequeno bônus: você consegue adivinhar qual dos seguintes é true , e qual é false ?

(1646842954019151681L == 1646842954019151682D)

(1646842954019151681L == (long) 1646842954019151682D)

all posts ->